- 标签:位运算、队列、数组、前缀和、滑动窗口
- 难度:困难
描述:给定一个仅包含
要求:返回所需的
说明:
- 子数组:数组的连续部分。
-
$1 <= nums.length <= 105$ 。 -
$1 <= 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]
每次需要翻转的起始位置肯定是遇到第一个元素为
同时我们还可以发现:
- 如果某个元素反转次数为奇数次,元素会由
$0 \rightarrow 1$ ,$1 \rightarrow 0$。 - 如果某个元素反转次数为偶数次,元素不会发生变化。
每个第
同时如果我们知道了前面
我们使用
- 如果前面第
$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:
。
因为 nums[i] = 2
。这样在遍历到第
整个算法的具体步骤如下:
- 使用
$res$ 记录最小翻转次数。使用$flip\underline{\hspace{0.5em}}count$ 记录窗口内前 $k - 1 $ 位元素的翻转次数。 - 遍历数组
$nums$ ,对于第$i$ 位元素:- 如果
$i - k >= 0$ ,并且$nums[i - k] == 2$ ,需要缩小窗口,将翻转次数减一。(此时窗口范围为$[i - k + 1, i - 1]$ )。 - 如果
$(flip\underline{\hspace{0.5em}}count + nums[i]) \mod 2 == 0$ ,则说明$nums[i]$ 还需要再翻转一次,将$nums[i]$ 标记为$2$ ,同时更新窗口内翻转次数$flip\underline{\hspace{0.5em}}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
-
时间复杂度:$O(n)$,其中
$n$ 为数组$nums$ 的长度。 - 空间复杂度:$O(1)$。