題目網址：https://leetcode.cn/problems/minimum-number-of-k-consecutive-bit-flips/

題意：給一 binary array nums 和一整數 k。

k-bit flip 指的是從 nums 中選擇一長度為 k 的 subarray, 並把 subarray 中的每一個 bit 進行反轉。

返回 nums 中不存在 0 所需的最小 k-bit flip 次數。若不可能, 則返回 -1。

subarray 指的是 array 的連續部分。

Solution 1：（TLE 無法通過）

想法：利用 Greedy, 因為對於每個位置而言, 只有初始狀態和 flip 次數決定了自己最終的狀態。每一個長度為 k 的區間, 最多只會被 flip 一次, 因為 flip 兩次對最終結果沒有影響。

  • 因此, 我們由左向右遍歷 nums, 一旦 nums[i] 為 0, 則將其做為 sliding window 的開頭往後取 k - 1 個元素進行 flip
  • 若 i + k - 1 ≥ n, 代表無法將最後幾個 0 反轉, 故返回 1
class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        const int n = nums.size();
        int res = 0;

        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                if (i + k - 1 < n) {
                    ++res;
                    for (int j = i; j <= i + k - 1; ++j) {
                        nums[j] = 1 - nums[j]; // flip
                    }
                } else {
                    return -1;
                }
            }
        }

        return res;
    }
};
  • time：$O(n \cdot k)$ ➔ worse case：每一個元素 i 都要往後檢查 k 個
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：改進 Solution 1, 我們發現：

  • 當 flip 次數為奇數次, 元素會反轉。而當 flip 次數為偶數次, 元素不變
  • 當前位置 i 受到前 k - 1 個元素是否 flip 的影響, 因此我們只需要知道前 k - 1 個元素 flip 的次數
  • 用 queue 來模擬 sliding window, 其中 queue 紀錄當前位置 i 之前的 k - 1 個數中, 哪些位置為首的子區間進行了 flip
    • 其中 q.size() 代表 idx = i 之前, 區間 [i - k + 1, i] 中有幾個數進行了 flip
class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        const int n = nums.size();
        int res = 0;
        queue<int> q;

        for (int i = 0; i < n; ++i) {
            // 若 q.front() 不在 [i - k + 1, i] 的 sliding window 中, 則其 flip 次數應刪除
            while (!q.empty() && q.front() < i - k + 1) {
                q.pop();
            }

            const int flips = q.size(); // 當前元素 nums[i] 的 flip 次數(前 k - 1 個數所造成的)
            const int cur = (nums[i] + flips) % 2; // 當前元素進行 flip 之後的值

            // 若當前元素進行 flip 之後的值為 0, 代表要 flip
            if (cur == 0) {
                // 後面的數不夠, cur 無法作為開頭組成新的 sliding window 來反轉自己成 1
                if (i + k - 1 >= n) {
                    return -1;
                }

                // nums[i] 做為進行 flip 的 sliding window 開頭加到 queue 中
                ++res;
                q.emplace(i);
            }
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(k)$ ➔ q 中元素不超過 k - 1 個

Solution 3：

想法：改進 Solution 2, 利用 Sliding Window, 紀錄總共 flip 的次數, 隨著 window 右移, 左側超出 window 且有 flip 的元素, 應被扣除。

  • 用 flip 來記錄所有元素 flip 的總數
  • 每次 sliding window 右移時, 當前區間為 [i - k + 1, i], 要檢查被移出 sliding window 的元素 i - k 是否有 flip
  • 當前 flip 總數 - 左側超出 window 且有 flip 的元素個數 = 當前元素 flip 的次數
class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        const int n = nums.size();
        int flips = 0, res = 0;

        for (int i = 0; i < n; ++i) {
            // 左側超出 window 且有 flip 的元素要扣除（有 flip 的元素, 會被標記成 > 1）
            if (i >= k && nums[i - k] > 1) {
                --flips;
                nums[i - k] -= 2;
            }

            // 若當前元素進行 flip 之後的值為 0, 代表要 flip
            if ((nums[i] + flips) % 2 == 0) {
                if (i + k - 1 >= n) {
                    return -1;
                }

                ++flips;
                ++res;
                nums[i] += 2; // 將有 flip 的元素, 標記成 > 1 的值
            }
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(1)$ ➔ 只需常數空間