今天什么死妈题目
题目 :
给你一串010101010的bit
你每次都可以一次翻转k个bit
请问最少要几次翻转才能让所有bit变成1
范例 :
00010110 然后k=3
翻转三次在不同位子
11110110
11111000
11111111
所以答案是三次
思路 :
首先要知道
每一次翻转都是一次性的
同样位子的翻转是没有用的
同时 也就是说你的翻转顺序没差
然后
你如果每次都以最左边的bit为基准
一次向右翻转k个bit
那么就会变成sliding window
但是这题的len 跟 k 非常大
所以sliding window 里面你要怎么翻转
是第二个难点
然后我发现
可以用now的0或1来检测当前的翻转状况
然后加上我去提示偷看的prefix sum
可以想到
用另一个阵列来记录翻转k个的长度的位子
意思是
我在i处翻转我的now
那么我在i+k处就必须再次翻转我的now
并且观察我的now当前的bit的那个
然后
那个那个
那个那个
屁眼
干你娘机掰
```cpp
class Solution {
public:
int minKBitFlips(vector<int>& nums, int k)
{
int len = nums.size();
vector<int> paper(len+1 ,0);
int l = 0 ;
int r = k-1;
int now = 1;
int res = 0;
while(r < len)
{
if(paper[l])now = 1-now;
if(nums[l] != now)
{
paper[l] = 1-paper[l];
paper[r+1] = 1-paper[r+1];
now = 1-now;
res ++;
}
l++;
r++;
}
for(int i = l ; i < len ; i ++)
{
if(paper[i])now = 1-now;
if(nums[i] != now)return -1;
}
return res;
}
};
```
好想打手枪