题目描述

房间中有 n 个灯泡，编号从 0 到 n-1，自左向右排成一行。最开始的时候，所有的灯泡都是 关 着的。

你的任务是使得灯泡的开关状态和 target 描述的状态一致，其中 target[i] 等于 1 意味着第 i 个灯泡是开着的，等于 0 意味着第 i 个灯是关着的。

有一个开关可以用于翻转灯泡的状态，翻转操作定义如下：

• 选择当前配置下的任意一个灯泡（下标为 i ）
• 翻转下标从 i 到 n-1 的每个灯泡

翻转时，如果灯泡的状态为 0 就变为 1，为 1 就变为 0。

返回达成 target 描述的状态所需的 最少 翻转次数。

样例

输入：target = "10111"
输出：3
解释：初始配置 "00000".
从第 3 个灯泡（下标为 2）开始翻转 "00000" -> "00111"
从第 1 个灯泡（下标为 0）开始翻转 "00111" -> "11000"
从第 2 个灯泡（下标为 1）开始翻转 "11000" -> "10111"
至少需要翻转 3 次才能达成 target 描述的状态

输入：target = "101"
输出：3
解释："000" -> "111" -> "100" -> "101".

输入：target = "00000"
输出：0

输入：target = "001011101"
输出：5

限制

• 1 <= target.length <= 10^5
• target[i] == '0' 或者 target[i] == '1'

算法

(贪心) $O(n)$

1. 我们知道，越靠前的灯泡越是需要先关注的。实际上，由于灯泡开关两次等于没做，所以这个问题仅有一种最优解法。
2. 我们肯定从第一个灯泡开始动开关，如果第一个为开，则我们无论如何都必须让第一个灯泡打开，同时后边所有的灯泡都跟着变化。第一个灯泡操作结束后，可以忽略第一个灯泡，将第二个灯泡变为第一个灯泡进行考虑。这里需要一个布尔变量来统计之前灯泡的开关情况。

时间复杂度

• 遍历一次数组，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minFlips(string target) {
        const int n = target.size();
        bool s = false;
        int ans = 0;

        for (int i = 0; i < n; i++)
            if (target[i] == '0') {
                if (s) {
                    ans++;
                    s = false;
                }
            } else {
                if (!s) {
                    ans++;
                    s = true;
                }
            }

        return ans;
    }
};