0995. K 连续位的最小翻转次数 #
- 标签:位运算、队列、数组、前缀和、滑动窗口
- 难度:困难
题目大意 #
给定一个仅包含 0
和 1
的数组 nums
,再给定一个整数 k
。进行一次 k
位翻转包括选择一个长度为 k
的(连续)子数组,同时将子数组中的每个 0
更改为 1
,而每个 1
更改为 0
。
要求:返回所需的 k
位翻转的最小次数,以便数组没有值为 0
的元素。如果不可能,返回 -1
。
解题思路 #
每次需要翻转的起始位置肯定是遇到第一个元素为 0
的位置开始反转,如果能够使得整个数组不存在 0
,即返回 ans
作为反转次数。
同时我们还可以发现:
- 如果某个元素反转次数为奇数次,元素会由
0 -> 1
,1 -> 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
,所以我们可以用 0
和 1
以外的数,比如 2
来标记第 i
个元素发生了翻转,即 nums[i] = 2
。这样在遍历到第 i
个元素时,如果有 nums[i - k] == 2
,则说明 nums[i - k]
发生了翻转。同时根据 flip_count
和 nums[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
。
代码 #
|
|