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
ton-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'
ortarget[i] == '1'
Solution: XOR
Flip from left to right, since flipping the a bulb won’t affect anything in the left.
We count how many times flipped so far, and that % 2 will be the state for all the bulb to the right.
If the current bulb’s state != target, we have to flip once.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { public: int minFlips(string target) { int ans = 0; int cur = 0; for (char c : target) { if (c - '0' != cur) { cur ^= 1; ++ans; } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment