写点什么

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

发布于: 2021 年 02 月 19 日
你真的了解什么是「暴力解法」吗 ...

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

题目描述


这是 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)$ 的,数据范围是 3w(数量级为 $10^4$),极限数据下单秒的运算量在 $10^8$ 以上,会有超时风险。


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(1)$


贪心 + 差分解法


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


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


同时我们又不希望是通过「遍历记 arrk 位进行 +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)$


证明


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


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


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


补充知识


为什么说 $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 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode


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


发布于: 2021 年 02 月 19 日阅读数: 17
用户头像

算法爱好者,退役 OIer 2020.03.07 加入

公众号「宫水三叶的刷题日记 」。每天十分钟,快乐学算法 ~

评论

发布
暂无评论
你真的了解什么是「暴力解法」吗 ...