跳至主要內容

0995. K 连续位的最小翻转次数

ITCharge大约 3 分钟

0995. K 连续位的最小翻转次数open in new window

  • 标签:位运算、队列、数组、前缀和、滑动窗口
  • 难度:困难

题目大意

给定一个仅包含 01 的数组 nums,再给定一个整数 k。进行一次 k 位翻转包括选择一个长度为 k 的(连续)子数组,同时将子数组中的每个 0 更改为 1,而每个 1 更改为 0

要求:返回所需的 k 位翻转的最小次数,以便数组没有值为 0 的元素。如果不可能,返回 -1

解题思路

每次需要翻转的起始位置肯定是遇到第一个元素为 0 的位置开始反转,如果能够使得整个数组不存在 0,即返回 ans 作为反转次数。

同时我们还可以发现:

  • 如果某个元素反转次数为奇数次,元素会由 0 -> 11 -> 0
  • 如果某个元素反转次数为偶数次,元素不会发生变化。

每个第 i 位置上的元素只会被前面 [i - k + 1, i - 1] 的元素影响。所以我们只需要知道前面 k - 1 个元素翻转次数的奇偶性就可以了。

同时如果我们知道了前面 k - 1 个元素的翻转次数就可以直接修改 nums[i] 了。

我们使用 flip_count 记录第 i 个元素之前 k - 1 个位置总共被反转了多少次,或者 flip_count 是大小为 k - 1 的滑动窗口。

  • 如果前面第 k - 1 个元素翻转了奇数次,则如果 nums[i] == 1,则 nums[i] 也被翻转成了 0,需要再翻转 1 次。
  • 如果前面第 k - 1 个元素翻转了偶数次,则如果 nums[i] == 0,则 nums[i] 也被翻转成为了 0,需要再翻转 1 次。

这两句写成判断语句可以写为:if (flip_count + nums[i]) % 2 == 0:

因为 0 <= nums[i] <= 1,所以我们可以用 01 以外的数,比如 2 来标记第 i 个元素发生了翻转,即 nums[i] = 2。这样在遍历到第 i 个元素时,如果有 nums[i - k] == 2,则说明 nums[i - k] 发生了翻转。同时根据 flip_countnums[i] 来判断第 i 位是否需要进行翻转。

整个算法的具体步骤如下:

  • 使用 res 记录最小翻转次数。使用 flip_count 记录窗口内前 k - 1 位元素的翻转次数。
  • 遍历数组 nums,对于第 i 位元素:
    • 如果 i - k >= 0,并且 nums[i - k] == 2,需要缩小窗口,将翻转次数减一。(此时窗口范围为 [i - k + 1, i - 1])。
    • 如果 (flip_count + nums[i]) % 2 == 0,则说明 nums[i] 还需要再翻转一次,将 nums[i] 标记为 2,同时更新窗口内翻转次数 flip_count 和答案最小翻转次数 ans
  • 遍历完之后,返回 res

代码

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