1529. Minimum number of suffix flips

Address ：

Power button https://leetcode-cn.com/problems/minimum-suffix-flips/

subject ：

Give you a length of n 、 Subscript from 0 Starting binary string target . You have another length of n Binary string of s , At first, everyone was 0 . You want to make s and target equal .

In one step , You can choose the subscript i（0 <= i < n） And flip on Closed interval [i, n - 1] All bits in . Flipping means '0' Turn into '1' , and '1' Turn into '0' .

Return to make s And target Equal the minimum number of flips required .

Example 1：

Input ：target = "10111" Output ：3 explain ： first ,s = "00000" . Select subscript i = 2: "00000" -> "00111" Select subscript i = 0: "00111" -> "11000" Select subscript i = 1: "11000" -> "10111" To achieve the goal , You need at least 3 Time flip .

Example 2：

Input ：target = "101" Output ：3 explain ： first ,s = "000" . Select subscript i = 0: "000" -> "111" Select subscript i = 1: "111" -> "100" Select subscript i = 2: "100" -> "101" To achieve the goal , You need at least 3 Time flip .

Example 3：

Input ：target = "00000" Output ：0 explain ： because s Already equal to the goal , So no operation is required

Tips ：

n == target.length 1 <= n <= 105 target[i] by '0' or '1'

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/minimum-suffix-flips
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

First of all, flip the figure under the hand animation , Finding the law

such as ：10111

00000

00111

01000

10111

If you can't see clearly for the time being , On the contrary, you can see clearly , Change the topic to how to change a string into 0 The number of times

Then from left to right , We saw 1, You have to do a flip , Then next , It happens to be in reverse order

But how to implement the code ？ A little bit of a problem

Then watch , If the intermediate element is adjacent and of the same type , Such as fellow 1, Or both 0

When we flip, we actually flip together , Then we can regard these same types as only one

such as ：1010001, Let's reverse the order

1010001	0101110
0101110	0010001
0010001	0001110
0001110	0000001
0000001	0000000

After optimization, it is ：10101 Flip of

The exact number of flips is Of this string 1 Starting length ,

If it is 0 Opening remarks ：00110, In fact, it is seen as 10, The length is 2 

If you don't believe it, you can try

When such a rule is found, it is much easier to implement the code

Method 1 、 Count the number of strings

int minFlips(char * target){
	char *s = target;
	int cnt = 0;
	
	int i =0;
	char prev = '0';
	while(s[i])
	{
		if(s[i] != prev)
		{
			cnt++;
			prev = s[i];
		}
		
		i++;
	}
	
	return cnt;
}

See more brush notes