跳至主要內容

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

ITCharge大约 3 分钟

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

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

题目链接

题目大意

描述:给定一个仅包含 0011 的数组 numsnums,再给定一个整数 kk。进行一次 kk 位翻转包括选择一个长度为 kk 的(连续)子数组,同时将子数组中的每个 00 更改为 11,而每个 11 更改为 00

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

说明

  • 子数组:数组的连续部分。
  • 1<=nums.length<=1051 <= nums.length <= 105
  • 1<=k<=nums.length1 <= k <= nums.length

示例

  • 示例 1:
输入:nums = [0,1,0], K = 1
输出:2
解释:先翻转 A[0],然后翻转 A[2]
  • 示例 2:
输入: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:滑动窗口

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

同时我们还可以发现:

  • 如果某个元素反转次数为奇数次,元素会由 010 \rightarrow 1101 \rightarrow 0
  • 如果某个元素反转次数为偶数次,元素不会发生变化。

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

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

我们使用 flipcountflip\underline{}count 记录第 ii 个元素之前 k1k - 1 个位置总共被反转了多少次,或者 flipcountflip\underline{}count 是大小为 k1k - 1 的滑动窗口。

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

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

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

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

  • 使用 resres 记录最小翻转次数。使用 flipcountflip\underline{}count 记录窗口内前 $k - 1 $ 位元素的翻转次数。
  • 遍历数组 numsnums,对于第 ii 位元素:
    • 如果 ik>=0i - k >= 0,并且 nums[ik]==2nums[i - k] == 2,需要缩小窗口,将翻转次数减一。(此时窗口范围为 [ik+1,i1][i - k + 1, i - 1])。
    • 如果 (flipcount+nums[i])mod2==0(flip\underline{}count + nums[i]) \mod 2 == 0,则说明 nums[i]nums[i] 还需要再翻转一次,将 nums[i]nums[i] 标记为 22,同时更新窗口内翻转次数 flipcountflip\underline{}count 和答案最小翻转次数 ansans
  • 遍历完之后,返回 resres

思路 1:代码

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

思路 1:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 为数组 numsnums 的长度。
  • 空间复杂度O(1)O(1)