Hard

题目描述

给你一个二进制数组 nums 和一个整数 k。

k位翻转 就是从 nums 中选择一个长度为 k 的（连续）子数组，同时把子数组中的每个 0 都改成 1，每个 1 都改成 0。

返回数组中不存在 0 时所需的最小 k位翻转 次数。如果无法实现，返回 -1。

子数组 是数组的连续部分。

示例 1：

输入：nums = [0,1,0], k = 1
输出：2
解释：先翻转 nums[0]，然后翻转 nums[2]。

示例 2：

输入：nums = [1,1,0], k = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：

输入：nums = [0,0,0,1,0,1,1,0], k = 3
输出：3
解释：
翻转 nums[0],nums[1],nums[2]: nums 变成 [1,1,1,1,0,1,1,0]
翻转 nums[4],nums[5],nums[6]: nums 变成 [1,1,1,1,1,0,0,0] 
翻转 nums[5],nums[6],nums[7]: nums 变成 [1,1,1,1,1,1,1,1]

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= k <= nums.length

解题思路

这道题的核心思想是贪心算法：当遇到0时，必须立即翻转，且翻转的起始位置就是当前0的位置。

基本思路： 从左到右遍历数组，当遇到0时，必须从当前位置开始进行k位翻转。关键观察：如果在位置i遇到0，那么最优策略就是从位置i开始翻转k位，因为这是能够翻转当前0的最左边的翻转方案。

优化思路： 直接模拟翻转会导致时间复杂度过高。我们可以使用差分数组的思想来优化：

  1. 用一个变量记录当前位置受到的翻转次数（翻转次数为奇数时，当前位相对于原值被翻转）
  2. 用队列或标记数组记录每次翻转的结束位置
  3. 当到达翻转结束位置时，减少翻转计数

实现要点：

  • 遍历到位置i时，先处理之前翻转操作对当前位置的影响
  • 计算当前位置的实际值：(原值 + 翻转次数) % 2
  • 如果当前值为0，必须进行翻转；如果i+k超出数组范围，返回-1
  • 记录翻转操作的结束位置，用于后续更新翻转计数

时间复杂度O(n)，空间复杂度O(n)，这是该问题的最优解法。

代码实现

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> diff(n + 1, 0);
        int flips = 0;
        int flipCount = 0;
        
        for (int i = 0; i < n; i++) {
            flipCount += diff[i];
            int currentVal = (nums[i] + flipCount) % 2;
            
            if (currentVal == 0) {
                if (i + k > n) {
                    return -1;
                }
                flips++;
                flipCount++;
                diff[i + k] = -1;
            }
        }
        
        return flips;
    }
};

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        flip_count = 0
        flips = 0
        flip_ends = [0] * (n + k)
        
        for i in range(n):
            flip_count += flip_ends[i]
            current_val = (nums[i] + flip_count) % 2
            
            if current_val == 0:
                if i + k > n:
                    return -1
                flips += 1
                flip_count += 1
                flip_ends[i + k] = -1
                
        return flips

public class Solution {
    public int MinKBitFlips(int[] nums, int k) {
        int n = nums.Length;
        int[] diff = new int[n + 1];
        int flips = 0;
        int flipCount = 0;
        
        for (int i = 0; i < n; i++) {
            flipCount += diff[i];
            int currentVal = (nums[i] + flipCount) % 2;
            
            if (currentVal == 0) {
                if (i + k > n) {
                    return -1;
                }
                flips++;
                flipCount++;
                diff[i + k] = -1;
            }
        }
        
        return flips;
    }
}

var minKBitFlips = function(nums, k) {
    const n = nums.length;
    let flips = 0;
    let flipCount = 0;
    const isFlipped = new Array(n).fill(false);
    
    for (let i = 0; i < n; i++) {
        if (i >= k && isFlipped[i - k]) {
            flipCount--;
        }
        
        const currentBit = flipCount % 2 === 0 ? nums[i] : 1 - nums[i];
        
        if (currentBit === 0) {
            if (i + k > n) {
                return -1;
            }
            
            isFlipped[i] = true;
            flipCount++;
            flips++;
        }
    }
    
    return flips;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

相关题目