[Leetcode 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 <= A.length <= 30000
1 <= K <= A.length

解题思路

先从数组的最左元素开始，因为要改变最左元素的状态，只能以这个元素为起始点。

如果这个元素是1，那么不需要kBitFlip操作；如果这个元素是0，那么需要进行一次kBitFlip操作， kBitFlip的操作次数 ++ans。当元素值变为1之后，进入下一个元素判断。

这样的操作最多进行A.size() - K + 1次。这样能保证index从0到A.size() - K的值都是1，只需要对剩下的元素进行检查。如果有0，return -1；否则return kBitFlip的操作次数ans。

示例代码 (cpp)

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        if (K > A.size()) {
            for (auto i = 0; i < A.size(); ++i) {
                if (A[i] == 0)
                    return -1;
            }
            return 0;
        } 
        int ans = 0;
        for (auto i = 0; i < A.size() - K + 1; ++i) {
            if (A[i] == 0) {
                kBitFlip(A, K, i);
                ++ans;
            }
        }
        for (auto j = A.size() - K; j < A.size(); ++j) {
            if (A[j] == 0) {
                return -1;
            }
        }
        return ans;
    }
    void kBitFlip(vector<int>& A, const int K, const int loc) {
        for (auto i = loc; i < loc + K; ++i) {
            A[i] = (A[i]==1) ? 0 : 1;
        }
    }
};

复杂度分析

时间复杂度: O(N * K)
空间复杂度: O(1)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！