5473. Bulb Switcher IV

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

• Choose any bulb (index i) of your current configuration.
• Flip each bulb from index i to n-1.

When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".

Example 3:

Input: target = "00000"
Output: 0

Example 4:

Input: target = "001011101"
Output: 5

Constraints:

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

---

给一排灯泡，初始时都是灭的，每次可以选第i个灯泡，然后把第i个到最后的所有灯泡的状态翻转。问最少需要多少次操作才能得到目标状态序列。

很有意思的题，观察数据发现数据规模在1e5，数据量比较大，估计只有O(n)算法能过。接着，观察样例，不要被样例的解答给迷惑了。比如第一个例子10111，除了样例的解法，还可以谈心的做，序列变化如下：

0. 00000
1. 11111
2. 10000
3. 10111

即每次从左往右，把第一个不符合target状态的灯及往后的灯都flip，这种方法已经是最优的了。所以对于任意一个灯泡，它至少被翻转的次数就是它前面有多少种连续不同状态的灯泡。比如对于10111的后三个111，它前面有1和0，因为最原始是00，要变成10，则在满足第一个灯泡时有个0->1的翻转，导致第2个灯泡也变了；第二个灯泡也要flip一次；等到111时，它需要翻转的次数就是前面10共有2种特异状态。

所以问题转换为求字符串中有多少个连续相同状态的片段，所有片段数就是需要翻转的次数。另外要注意如果开头是0的话，则开头可以少翻转一次。代码如下：

class Solution {
public:
	int minFlips(string target) {
		int n = target.size();
		int ans = 0;
		int  i = 0;
		while (i < n) {
			int j = i + 1;
			while (j < n&&target[j] == target[i])++j;
			++ans;
			i = j;
		}
		if (target[0] == '0')return ans - 1;
		else return ans;
	}
};

本代码提交AC。