题目解析

给一个包含0、1的数组，每次能反转K个元素(0->1, 1->0)，输出需要翻转多少次。

1
2
3
4
5
6
输入: A = [0,0,0,1,0,1,1,0], K = 3
输出: 3
解释：
翻转 A[0],A[1],A[2]: A 变为 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A 变为 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A 变为 [1,1,1,1,1,1,1,1]

方法一 贪心

贪心的策略是对于每个0位都将其作为K位的第一位来翻转，最后的k-1位因为不够k位不能进行翻转，所以它们能不能变1全靠前面的翻转，所以在翻转结束后判断后面几位是否变成1即可判断是否成功。
时间复杂度O(n*k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int result = 0;
        for (int i = 0; i < A.size(); i++) {
            if (A[i] == 1) continue;
            for (int j = 0; j < K && i + K - 1 < A.size(); j++) {
                A[i+j] ^= 1;  // 使用异或来执行翻转操作
            }
            result++;
        }
        for (int i = A.size() - K; i < A.size(); i++) {
            if (A[i] == 0) return -1;
        }
        return result;
    }
};

方法二 贪心

翻转有以下规律：

  1. A[i]翻转奇数次，A[i]被翻转了
  2. A[i]翻转偶数次，相当于没有被翻转
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
    public:
        int minKBitFlips(vector<int>& A, int K) {
            vector<int> isFlips(A.size(), 0);
            int flipped = 0;
            int ans = 0;
            for (int i = 0; i < A.size(); i++) {
                flipped ^= isFlips[i]; // 判断当前元素之前K位内是不是已经翻转
                // 如果翻转了1次，则：
                //  1.当A[i]为1，而flipped为1时需要翻转
                //  2.当A[i]为0，而flipped为0时需要翻转
                // 这两种情况都是异或为0
                if (A[i] ^ flipped == 0) {
                    if (i+K < A.size()) {
                        isFlips[i+K] = 1; // 
                    }
                    if (i+K > A.size()) return -1; // 因为这种情况下，i处于A.size()-K~A.size()这一范围内，难以完成翻转（不够K个）
                    flipped ^= 1; // 翻转一次
                    ans++;
                }
            }
            
            return ans;
        }
    };