今天什麼死媽題目
題目 :
給你一串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;
}
};
```
好想打手槍