你真的了解什么是「暴力解法」吗 ...

点击 这里 可以查看更多算法面试相关内容~

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：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)O(nk)O(nk) 的，数据范围是 3w（数量级为 10410^4104），极限数据下单秒的运算量在 10810^8108 以上，会有超时风险。

PS. 测试了 C++、Python 和 Java 三门语言，只有 Java 能过。

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(nk)O(nk)
• 空间复杂度：O(1)O(1)O(1)

贪心 + 差分解法

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

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

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

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

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)O(n)
• 空间复杂度：O(n)O(n)O(n)

证明

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

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

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

补充知识

为什么说 O(nk)O(nk)O(nk) 的解法是「贪心解法」，而不是「暴力解法」？

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

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

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

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

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

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

然后对三种方案得到的最终解进行检查，找出符合结果全是 1 的方案。

这种通过「穷举」方案检查合法性的解法才是「暴力解法」。

最后

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

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

由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。

为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：github.com/SharingSour…

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