K 连续位的最小翻转次数

标签: 位运算 队列 数组 前缀和 滑动窗口

难度: Hard

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

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

返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。

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

示例 1：

输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[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
解释：
翻转 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]

提示：

  • 1 <= nums.length <= 105
  • 1 <= k <= nums.length

Submission

运行时间: 85 ms

内存: 19.4 MB

from typing import List

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        flip, res = 0, 0
        is_flipped = [0] * n

        # Use a sliding window approach to flip the bits
        for i in range(n):
            # If we have reached the point of flipping
            if i >= k:
                flip ^= is_flipped[i - k]
            # Determine if we need to flip at the current position
            if nums[i] == flip:
                if i + k > n: # If there isn't enough space to flip
                    return -1
                is_flipped[i] = 1 # Mark this index as flipped
                flip ^= 1
                res += 1

        return res

Explain

该题解采用了滑动窗口的思路。通过一个额外的数组 `is_flipped` 来记录每个位置是否进行了翻转。变量 `flip` 用于记录当前位置的翻转状态（0或1，表示无翻转或有翻转）。在遍历数组 `nums` 时，如果当前位置 i 大于或等于 k，根据 `is_flipped` 数组更新 `flip` 的状态。如果 `nums[i]` 与 `flip` 相同，说明需要进行翻转，此时检查是否有足够的空间进行翻转（即 i + k 是否超过数组长度），如果不够则返回 -1，否则在 `is_flipped` 标记此位置，并更新翻转次数 `res` 和翻转状态 `flip`。最终返回翻转次数 `res`。

时间复杂度: O(n)

空间复杂度: O(n)

from typing import List

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        flip, res = 0, 0
        is_flipped = [0] * n  # 记录每个位置是否进行了翻转

        # 使用滑动窗口的方法进行位翻转
        for i in range(n):
            # 如果已处理的长度达到k，则更新flip状态
            if i >= k:
                flip ^= is_flipped[i - k]
            # 判断当前位置是否需要翻转
            if nums[i] == flip:
                if i + k > n: # 检查是否有足够的空间进行翻转
                    return -1
                is_flipped[i] = 1 # 标记此位置已翻转
                flip ^= 1
                res += 1 # 增加翻转次数

        return res

Explore

使用`is_flipped`数组的优势在于它保持了原数组`nums`的不变性，这样原始数据可以在算法执行后仍然可用于其他目的。此外，直接修改`nums`可能会使原始数据丢失，增加错误翻转或重复翻转的风险。`is_flipped`数组仅记录翻转操作而不改变原数组，使得操作更清晰、逻辑更容易理解和维护。

检查`nums[i]`与`flip`是否相同是为了确定当前位置的实际值是否符合目标值（即0变为1，1变为0）。`flip`变量记录了当前位置由于之前的翻转操作导致的值变化。如果`nums[i]`与`flip`相同，表示当前位的值未达到目标状态，需要翻转。这两者会不同的情况出现在之前的翻转操作使得当前位的实际值已经是期望值，此时无需再次翻转。

如果`i + k > n`，意味着从当前位置开始的k位翻转将超出数组边界，无法形成一个完整的k长度的翻转区间。这样的部分翻转将无法保证每个元素都被正确处理，从而无法达到题目要求所有元素满足条件的目标。因此，当无法进行完整的k位翻转时，返回`-1`表示无法通过翻转达到要求的状态。

`flip`变量是一个关键的状态指示器，用于跟踪到当前位置为止的累积翻转影响。在遍历数组时，`flip`会根据`is_flipped`数组的值进行更新。每当处理到一个新的位置时，如果该位置之前的距离为k的位置被翻转过（即`is_flipped[i - k] == 1`），则`flip`的值会改变（0变1，1变0），以反映该翻转操作对当前位置及后续位置的影响。这样，每个位置的`flip`值都会准确表示由于之前所有翻转操作导致的当前位置的实际值变化。