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

题目描述

这是 LeetCode 上的 995. K 连续位的最小翻转次数 ，难度为 困难。

在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。

返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

示例 1：

1
2
3
输入：A = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：
1
2
3
输入：A = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：
1
2
3
4
5
6
输入：A = [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 <= A.length <= 30000
  • 1 <= K <= A.length

贪心解法

目标是将数组的每一位都变为 1 ，因此对于每一位 0 都需要翻转。

我们可以从前往后处理，遇到 0 则对后面的 k 位进行翻转。

这样我们的算法复杂度是 $O(nk)$ 的，数据范围是 3w（数量级为 $10^4$），极限数据下单秒的运算量在 $10^8$ 以上，会有超时风险。

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (i + k > n) return -1;
                for (int j = i; j < i + k; j++) nums[j] ^= 1;
                ans++;
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(nk)$
  • 空间复杂度：$O(1)$

补充

评论有同学提出了一些有价值的疑问，我觉得挺有代表性的，因此补充到题解：

  1. 为什么这样的解法是「贪心解法」，而不是「暴力解法」？

首先「暴力解法」必然是对所有可能出现的翻转方案进行枚举，然后检查每一个方案得到的结果是否符合全是 1 的要求。

这样的解法，才是暴力解法，它的本质是通过「穷举」找答案。复杂度是指数级别的。

而我们的「朴素贪心解法」只是执行了众多翻转方案中的一种。

举个 🌰，对于 nums = [0,0,1,1] 并且 k = 2 的数据：

暴力解法应该是「枚举」以下三种方案：

  1. 只翻转以第一个 0 开头的子数组（长度固定为 2）
  2. 只翻转以第二个 0 开头的子数组（长度固定为 2）
  3. 同时翻转第一个 0 开头和第二个 0 开头的子数组（长度固定为 2，只不过这时候第一个 0 被翻转了一次，第二个 0 被翻转了两次）

然后对三种方案得到的最终解进行检查，找出符合结果全是 1 的方案。这种通过「穷举」方案检查合法性的解法才是「暴力」解法。

  1. 为什么我采用了与「朴素贪心」解法相似的做法，超时了？

结果测试 C++、Python 超时，只有 Java 能过。

同样是 97 号样例数据，提交给 LeetCode 执行。Java 运行 200 ms 以内，而 C++ 运行 600 ms。

贪心 + 差分解法

由于我们总是对连续的一段进行「相同」的操作，同时只有「奇数」次数的翻转才会真正改变当前位置上的值。

自然而然，我们会想到使用数组 arr 来记录每一位的翻转次数。

同时我们又不希望是通过「遍历记 arr 的 k 位进行 +1」来完成统计。

因此可以使用差分数组来进行优化：当需要对某一段 [l,r] 进行 +1 的时候，只需要 arr[l]++ 和 arr[r + 1]-- 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        int[] arr = new int[n + 1];
        for (int i = 0, cnt = 0; i < n; i++) {
            cnt += arr[i];
            if ((nums[i] + cnt) % 2 == 0) {
                if (i + k > n) return -1;
                arr[i + 1]++;
                arr[i + k]--;
                ans++;
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

证明

为什么「一遇到 0 就马上进行翻转」这样的做法得到的是最优解？

这道题的贪心证明思路和 765. 情侣牵手 是一样的。

本质上是在证明当我在处理第 k 个位置的 0 的时候，前面 k - 1 个位置不存在 0，接下来要如何进行操作，可使得总的翻转次数最小。

如果你上次真正理解了我的证明过程的话，那么你会很容易就能证明出本题的贪心思路。

所以这次将这个证明过程留给大家思考 ~

为什么要「证明」或「理解证明」？

证明的意义在于，你知道为什么这样做是对的。

带来的好处是：

  1. 一道「贪心」题目能搞清楚证明，那么同类的「贪心」题目你就都会做了。否则就会停留在“我知道这道题可以这样贪心，别的题我不确定是否也能这样做”。

  2. 在「面试」阶段，你可以很清晰讲解你的思路。让面试官从你的「思维方式」上喜欢上你

更多与证明/分析相关的题解：

561. 数组拆分 I : 反证法证明贪心算法的正确性

765. 情侣牵手 : 为什么交换任意一个都是对的？：两种 100% 的解法：并查集 & 贪心

1579. 保证图可完全遍历 : 为什么先处理公共边是对的？含贪心证明 + 数组模板 ~

1631. 最小体力消耗路径 : 反证法证明思路的合法性

11. 盛最多水的容器 : 双指针+贪心解法【含证明】

最后

这是我们「刷穿 LeetCode」系列文章的第 No.995 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

贪心 差分

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！