第六章 - 高频考题(困难)
0995. K 连续位的最小翻转次数

题目地址(995. K 连续位的最小翻转次数)

题目描述

1
在仅包含 0 和 1 的数组 A 中,一次 K 位翻转包括选择一个长度为 K 的(连续)子数组,同时将子数组中的每个 0 更改为 1,而每个 1 更改为 0。
2
3
返回所需的 K 位翻转的最小次数,以便数组没有值为 0 的元素。如果不可能,返回 -1。
4
5
6
7
示例 1:
8
9
输入:A = [0,1,0], K = 1
10
输出:2
11
解释:先翻转 A[0],然后翻转 A[2]。
12
13
14
示例 2:
15
16
输入:A = [1,1,0], K = 2
17
输出:-1
18
解释:无论我们怎样翻转大小为 2 的子数组,我们都不能使数组变为 [1,1,1]。
19
20
21
示例 3:
22
23
输入:A = [0,0,0,1,0,1,1,0], K = 3
24
输出:3
25
解释:
26
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
27
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
28
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]
29
30
31
32
33
提示:
34
35
1 <= A.length <= 30000
36
1 <= K <= A.length
Copied!

前置知识

  • 连续子数组优化

公司

  • 暂无

暴力解

思路

首先考虑暴力的解法。暴力的思路可以是从左到右遍历数组,如果碰到一个 0,我们以其为左端进行翻转。翻转的长度自然是以其开始长度为 K 的子数组了。由于是以其为左端进行翻转,因此如果遇到一个 0 ,我们必须执行翻转,否则就无法得到全 1 数组。由于翻转的顺序不影响最终结果,即如果最终答案是翻转以 i, j , k 为起点的子数组,那么先翻转谁后翻转谁都是一样的。因此采用从左往右遍历的方式是可以的。
概括一下:暴力的思路可以是从左到右遍历数组,如果碰到一个 0,我们以其为左端进行翻转,并修改当前位置开始的长度为 k 的子数组,同时计数器 + 1,最终如果数组不全为 0 则返回 -1 ,否则返回计数器的值。

代码

  • 语言支持:Python3
Python3 Code:
1
class Solution:
2
def minKBitFlips(self, A, K):
3
N = len(A)
4
ans = 0
5
for i in range(N - K + 1):
6
if A[i] == 1:
7
continue
8
for j in range(K):
9
A[i + j] ^= 1
10
ans += 1
11
for i in range(N):
12
if A[i] == 0:
13
return -1
14
return ans
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n * k)$
  • 空间复杂度:$O(1)$

连续子数组优化

思路

对于这种连续子数组的题目。一般优化思路就那么几种。我们来枚举一下:
这三种技巧我都写过文章,如果不了解可以先看下。
对于这道题来说,我们可使用差分数组或者双端队列来优化。不管采用哪种,基本思路都差不多,你也可以对比下方代码看一下他们思路的一致性。 简单来说,他们的思路差不多,差别只是解决问题的使用的数据结构不同,因此 api 不同罢了。因此我并没有将二者作为两个解法。
对于差分数组来说,上面暴力解法内层有一个次数为 k 的循环。而如果使用差分数组只修改端点的值,就可轻松将时间复杂度优化到 $O(n)$。
对于双端队列来说,如果当前位置需要翻转,那么就将其入队。那如何判断当前位置的数字是多少呢?(可能由于前面数字的翻转,当前位置翻转了若干次,可能不是以前的数字了)。由于被翻转偶数次等于没有翻转,被翻转奇数次效果一样,因此只需要记录被翻转次数的奇偶性即可。而这其实就是队列长度的奇偶性。因为此时队列的长度就是当前数字被翻转的次数。当然这要求你将长度已经大于 k 的从队列中移除。

关键点

  • 连续子数组优化技巧

代码

  • 语言支持:Python3
Python3 Code:
差分数组:
1
class Solution:
2
def minKBitFlips(self, A: List[int], K: int) -> int:
3
n = len(A)
4
diff = [0] * (n + 1)
5
ans, cur = 0, 0
6
for i in range(n):
7
cur += diff[i]
8
if cur % 2 == A[i]:
9
if i + K > n:
10
return -1
11
ans += 1
12
cur += 1
13
diff[i + K] -= 1
14
return ans
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$
双端队列:
1
class Solution:
2
def minKBitFlips(self, A, K):
3
N = len(A)
4
q = collections.deque()
5
ans = 0
6
for i in range(N):
7
if q and i >= q[0] + K:
8
q.popleft()
9
if len(q) % 2 == A[i]:
10
if i + K > N:
11
return -1
12
q.append(i)
13
ans += 1
14
return ans
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(k)$

空间复杂度为 O(1) 的算法

思路

不管是使用差分数组和还是双端队列,其实都没有必要使用额外的数据结构,而是使用原来的数组 A,也就是原地修改
比如,我们可以只记录双端队列的长度,要判断一个数字是否在队列里,只需要将其映射到题目数据范围内的另外一个数字即可。由于题目数据范围是 [0,1] 因此我们可以将其映射到 2。

关键点

  • 原地修改

代码

  • 语言支持:Python3
Python3 Code:
1
class Solution:
2
def minKBitFlips(self, A, K):
3
flips = ans = 0
4
for i in range(len(A)):
5
if i >= K and A[i - K] - 2 == 0:
6
flips -= 1
7
if (flips % 2) == A[i]:
8
if i + K > len(A):
9
return -1
10
A[i] = 2
11
flips += 1
12
ans += 1
13
return ans
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。