LeetCode 1529. 灯泡开关 IV
原题链接
中等
作者:
Ccc1Z
,
2020-07-31 15:08:53
,
所有人可见
,
阅读 369
思路:
- 关于翻转问题的两个特点(参考Zerotrac)
- 1.结果与你的翻转顺序无关
- 2.每个位置至多被翻转1次(翻转2次等于没有翻转,3次又等于只翻转了一次)
- 设置一个标志位,当当前位置不等于标志位时翻转,同时把标志位异或1(代表翻转了一次要找的状态发生改变)再去跟下一位进行比较
- 1101 -> 0000
- 1.标志位为0 第一位为1 翻转一次 变成0010 此时标志位变成1 ans = 1
- 2.标志位为1 第二位为1 不翻转 此时标志位任然为1
- 3.标志位为1 第三位为0 翻转一次 变成0001 此时标志位变为0 ans = 2
- 4.标志位为0 第四位为1 翻转一次 变成0000 此时结束 ans = 3
class Solution {
public int minFlips(String target) {
int status = 0;
int ans = 0;
for(int i = 0 ; i < target.length() ; i++){
char c = target.charAt(i);
if(status != c - '0'){
ans++;
status ^= 1;
}
}
return ans;
}
}