題目

題目大意

給一個元素皆為 0 或 1 的陣列 A 和一個數字 K，今天可以選擇將連續 K 個數字做反轉 (0 變 1、1 變 0)，問至少幾次操作可以將陣列 A 的元素全部變為 1，如果無法做到，回傳 -1。

想法

看到的時候蠻直覺可以 greedy 的，考慮前 i 個數字皆為 1，在自己要變成 １ 的情況，就只會有原本為 1 或是把自己和後面 K-1 個數字都反轉兩個情況。
反轉後面的數字這件事情可能有點難，但如果把問題轉為「自己被反轉幾次」，就瞬間變簡單。我們可以利用一個 queue 去紀錄「反轉」的時間，假如今天 K = 3，在 index =０和 1 都做了反轉，那到 index = 2 的時候他會發現 queue 裡面還有兩個沒有過期的反轉，所以 2 知道自己會被反轉兩次，而 index = 3 的時候因為 0 + 3 >= 3，在 index = 0 時做的反轉操作會過期，故 index = 3 的反轉操作次數為 1 + ( index = 2 時是否有反轉)。
至於反轉後的值，可以用 % 2 取得，這部分不多贅述。
時間複雜度 Ｏ(A.length())，空間複雜度 O(K)

Code(C++)

int minKBitFlips(vector<int> A, int K) {
   int n = A.size(), cnt = 0;
   queue<int>q;
   for(int i=0; i<n; i++) {
       if (!q.empty() && q.front() <= i) q.pop();
       if ((A[i] + q.size()) % 2 == 0) {
       	if (i + K > n) return -1;
           cnt++;
           q.push(i+K);
       }
   }
   return cnt;
}

心得

第一天就 hard 有點嚇到，實際上難度應該只有 medium。