各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 25 天。今天力扣上的每日一题是「995. K 连续位的最小翻转次数」。

解题思路

题目大意：每次翻转长度为 K 的子数组，求最少的翻转次数使数组中所有的 0 都更改为 1。如果不能实现，则返回 -1.

  • 结论 1：后面区间的翻转，不会影响前面的元素。因此可以使用贪心策略，从左到右遍历，遇到每个 0 都把它和后面的 K 个数进行翻转。
    - 结论 2：$A[i]$ 翻转偶数次的结果是 $A[i]$；翻转奇数次的结果是 $A[i] ^ 1$。

方法一：模拟翻转（超时）

一个直观的思路是，从左到右遍历一遍，遇到数字为 0，那么翻转以该数字为起始的 K 个数字。

代码如下：

  1. class Solution(object):
  2.     def minKBitFlips(self, A, K):
  3.         """
  4.         :type A: List[int]
  5.         :type K: int
  6.         :rtype: int
  7.         """
  8.         N = len(A)
  9.         res = 0
  10.         for i in range(N - K + 1):
  11.             if A[i] == 1:
  12.                 continue
  13.             for j in range(K):
  14.                 A[i + j] ^= 1
  15.             res += 1
  16.         for i in range(N):
  17.             if A[i] == 0:
  18.                 return -1
  19.         return res
  • 时间复杂度：$O(N * K + N)$，超时。
    - 空间复杂度：$O(1)$。

方法二：滑动窗口

上面方法超时的主要原因是我们真实地进行了翻转。根据结论二，位置 i 现在的状态，和它被前面 K - 1 个元素翻转的次数（奇偶性）有关。

我们使用队列模拟滑动窗口，该滑动窗口的含义是前面 K - 1 个元素中，以哪些位置起始的窗口进行了翻转。该滑动窗口从左向右滑动，如果当前位置 i 需要翻转，则把该位置存储到队列中。遍历到新位置 j (j < i + K)时，队列中元素的个数代表了 i 被前面 K - 1 个元素翻转的次数。

  • 当 i 位置被翻转了偶数次，如果 $A[i]$ 为 0，那么翻转后仍是 0，当前元素需要翻转；
    - 当 i 位置被翻转了奇数次，如果 $A[i]$ 为 1，那么翻转后是 0，当前元素需要翻转。

综合上面两点，我们得到一个结论，如果 $len(que) % 2 == A[i]$ 时，当前元素需要翻转。

  1. class Solution(object):
  2.     def minKBitFlips(self, A, K):
  3.         """
  4.         :type A: List[int]
  5.         :type K: int
  6.         :rtype: int
  7.         """
  8.         N = len(A)
  9.         que = collections.deque()
  10.         res = 0
  11.         for i in range(N):
  12.             if que and i >= que[0] + K:
  13.                 que.popleft()
  14.             if len(que) % 2 == A[i]:
  15.                 if i +  K > N: return -1
  16.                 que.append(i)
  17.                 res += 1
  18.         return res

刷题心得

今天的题目理解着比较困难，主要是语言很难说明白，其实理解之后没有那么难。

参考资料：
1. Grandyang
2. 官方题解：K 连续位的最小翻转次数
3. 官方答案太难懂啦，滑动窗口通俗易懂。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！