995. Minimum Number of K Consecutive Bit Flips

In an array A containing only 0s and 1s, a *K-bit flip *consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array.  If it is not possible, return -1.

Example 1:

Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].

Example 2:

Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].

Example 3:

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

Note:

  1. 1 <= A.length <= 30000
  2. 1 <= K <= A.length

这道题博主最先在某家公司的 OA 上看到过(OA 出 Hard 题,也真是给跪了~),给了一个只有0和1的数组,又给了一个数字K,说是每次可以翻转任意连续K个位置的数字,问我们多少步可以把所有的0都翻转为1。这是道挺有意思的题目,背景可以随便换,比如什么烙煎饼啊,翻煎鸡蛋啊,都是一样的问题。注意我们翻转的时候,一旦选定了起始点,那么只能翻连着的K个位置,由于无法影响到前面的0的,所以需要在遇到0的时候,就进行翻转,这就是明显的贪婪算法的特征,这要一遇到0,就立马翻连续K个位置,比如对于数组 [0,1,0],K = 2,遇到位置0上的0,翻转,变为 [1,0,0],此时遇到位置1上的0,翻转,变为 [1,1,1],操作完成。想法有了,于是就吭哧吭哧的写好了代码,交给 OJ 大人审阅,结果被驳回,Time Limit Exceeded,什么鬼?那么仔细想一下吧,上面的这种解法到底哪里最费时,当然是翻转K个位置了,若K非常大,而且若需要翻转的位置很多的话,将非常的不高效。所以当务之急就是想办法代替真实的翻转,最简单的方法就是记录起始翻转的位置,我们使用一个长度相同的数组 isFlipped,其中 isFlipped[i] 表示在原数组i位置上进行了K个连续翻转。现在虽然知道了其实翻转的位置,但是由于是连续翻转K个,之后的位置也被翻转,比如 [0,1,0] 在位置0翻转后,变为了 [1,0,0],那么位置1就从之前的1变为0了,此时位置1也需要翻转了,那么我们怎么知道非起始翻转位置的数字当前是0还是1呢,这时就要引入另一个变量 curFlipped 了,表示当前位置的数字跟原数组相比是否被翻转了。所以一旦决定对当前位置进行翻转,那么需要将 isFlipped[i] 标记为1,并且翻转 curFlipped,方法是’异或’上1,举个例子来说对于数组 [0,1,0,1], K=3 来说,当对位置0进行翻转,数组变为 [1,0,1,0],那么在位置1的时候,curFlipped 是1,表示此时0相对于原来的1是翻转了,若我们在为1时再次进行翻转,数组变为 [1,1,0,1],此时 curFlipped 变为0了,表明位置2上的0对于原数组的位置2上的0来说没有翻转(虽然实际上翻转了两次),那么我们怎么知道某个位置应不应该翻转呢?需要根据 curFlipped 的值和原数组 A[i] 的值进行比较来判断,此时有两种情况:

  • 当 curFlipped 为0,表示没有翻转,且原数组 A[i] 为0,此时就需要翻转i位置。

  • 当 curFlipped 为1,表示翻转过了,而原数组 A[i] 为1,表示虽然原来是1,但是当前位置受之前翻转的影响变成了0,此时就需要翻转回来。

仔细观察上面两种情况可以发现 curFlipped 和 A[i] 同奇同偶的时候就需要翻转,那么两种情况可以合成一个表达式,curFlipped%2 等于 A[i] 时翻转。还需要弄清楚当什么时候就无法翻转了,当 i+K 大于n的时候,比如 [1,1,0,1], k=3 时,在位置2的时候 i+k>n(2+3>4)了,表示无法翻转了,直接返回 -1 即可。最后需要注意的是,curFlipped 受影响的位置只有在大小为K的窗口中,一旦超过了,是需要还原 curFlipped 的状态的。比如 [0,0,0,1], K=2 时,在位置0翻转后变为 [1,1,0,1],那么到位置2的时候,由于已经不受位置0翻转的影响了,此时的 curFlipped 应该变回0,所以只要’异或’上 isFlipped[0] 进行翻转,所以我们在循环开始前,首先检测 i>=K 是否成立,成立的话就让 curFlipped ‘异或’上 isFlipped[i-K] 进行状态还原,即便是位置 i-K 未进行过翻转,’异或’上0也不会改变 curFLipped 的状态,参见代码如下:

解法一:

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int res = 0, n = A.size(), curFlipped = 0;
        vector<int> isFlipped(n);
        for (int i = 0; i < n; ++i) {
            if (i >= K) curFlipped ^= isFlipped[i - K];
            if (curFlipped % 2 == A[i]) {
                if (i + K > n) return -1;
                isFlipped[i] = 1;
                curFlipped ^= 1;
                ++res;
            }
        }
        return res;
    }
};

根据上面的分析,对于每个位置i,我们其实只关心 i-K 位置是否是起始翻转的位置,之前什么情况并不 care,那么就没必要用整个数组来保存所有的起始翻转位置,只需要维护一个大小为K的窗口,将在此窗口内的起始翻转位置保存即可,超出范围的就扔掉。可以使用一个 queue 来保存窗口内的起始位置,在遍历的过程中,首先检测队首元素是否超出了范围,是的话就扔掉,否则就接着判断当前位置是否需要翻转,判断的方法是看此窗口中起始翻转的个数是否跟 A[i] 同奇同偶,推导方式跟上面解法中类似,这里就不过多讲解了,之后就判断所剩位置是否还有K个,没有就返回 -1。然后将当前位置加入队列,结果 res 自增1即可,参见代码如下:

解法二:

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

我们还可以进一步的优化空间,连队列 queue 都不需要,直接在原数组上修改,从而达到标记的目的,在解法一中,我们是新建了一个数组,对于起始翻转位置标记为1,其余为0。这里由于原数组已经使用了0和1,可以对于起始位置,将 A[i] 加上2,这样起始翻转位置的值就成了2或者3,跟原来的0和1就区分开了,那么只要将 A[i] 除以2,根据商是1还是0,就可以知道该位置是否是起始翻转位置,其余的地方基本相同,不过这里的 flipped 更新并没有用异或,而是直接用的加减,为了 diversity 也是拼了,参见代码如下:

解法三:

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int res = 0, n = A.size(), flipped = 0;
        for (int i = 0; i < n; ++i) {
            if (i >= K) flipped -= A[i - K] / 2;
            if (flipped % 2 == A[i]) {
                if (i + K > n) return -1;
                A[i] += 2;
                ++flipped;
                ++res;
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/995

类似题目:

Bulb Switcher

参考资料:

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/239284/C%2B%2B-greedy-stack-and-O(1)-memory

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/239117/Java-O(n)-Sliding-Window-Solution-using-Queue

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/238609/JavaC%2B%2BPython-One-Pass-and-O(1)-Space

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation