安陆做网站多少钱,快速排名网站,设计建筑的软件,阿里巴巴开通诚信通后网站怎么做基础知识#xff1a;
题目分类大纲如下#xff1a; #算法公开课
《代码随想录》算法视频公开课(opens new window)#xff1a;贪心算法理论基础#xff01;(opens new window),相信结合视频再看本篇题解#xff0c;更有助于大家对本题的理解。
#什么是贪心
贪心的本质…基础知识
题目分类大纲如下 #算法公开课
《代码随想录》算法视频公开课(opens new window)贪心算法理论基础(opens new window),相信结合视频再看本篇题解更有助于大家对本题的理解。
#什么是贪心
贪心的本质是选择每一阶段的局部最优从而达到全局最优。
这么说有点抽象来举一个例子
例如有一堆钞票你可以拿走十张如果想达到最大的金额你要怎么拿
指定每次拿最大的最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子你有一个背包体积为n如何把背包尽可能装满如果还每次选最大的盒子就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
#贪心的套路什么时候用贪心
很多同学做贪心的题目的时候想不出来是贪心想知道有没有什么套路可以一看就看出来是贪心。
说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优推出整体最优。
那么如何能看出局部最优是否能推出整体最优呢有没有什么固定策略或者套路呢
不好意思也没有 靠自己手动模拟如果模拟可行就可以试一试贪心策略如果不可行可能需要动态规划。
有同学问了如何验证可不可以用贪心算法呢
最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。
可有有同学认为手动模拟举例子得出的结论不靠谱想要严格的数学证明。
一般数学证明有如下两种方法
数学归纳法反证法
看教课书上讲解贪心可以是一堆公式估计大家连看都不想看所以数学证明就不在我要讲解的范围内了大家感兴趣可以自行查找资料。
面试中基本不会让面试者现场证明贪心的合理性代码写出来跑过测试用例即可或者自己能自圆其说理由就行了。
举一个不太恰当的例子我要用一下11 2但我要先证明11 为什么等于2。严谨是严谨了但没必要。
虽然这个例子很极端但可以表达这么个意思刷题或者面试的时候手动模拟一下感觉可以局部最优推出整体最优而且想不到反例那么就试一试贪心。
例如刚刚举的拿钞票的例子就是模拟一下每次拿做大的最后就能拿到最多的钱这还要数学证明的话其实就不在算法面试的范围内了可以看看专业的数学书籍
所以这也是为什么很多同学通过accept了贪心的题目但都不知道自己用了贪心算法因为贪心有时候就是常识性的推导所以会认为本应该就这么做
那么刷题的时候什么时候真的需要数学推导呢
例如这道题目链表环找到了那入口呢(opens new window)这道题不用数学推导一下就找不出环的起始位置想试一下就不知道怎么试这种题目确实需要数学简单推导一下。
#贪心一般解题步骤
贪心算法一般分为如下四步
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
这个四步其实过于理论化了我们平时在做贪心类的题目 很难去按照这四步去思考真是有点“鸡肋”。
做题的时候只要想清楚 局部最优 是什么如果推导出全局最优其实就够了。
#总结
本篇给出了什么是贪心以及大家关心的贪心算法固定套路。
不好意思了贪心没有套路说白了就是常识性推导加上举反例。
最后给出贪心的一般解题步骤大家可以发现这个解题步骤也是比较抽象的不像是二叉树回溯算法给出了那么具体的解题套路和模板。
455.分发饼干已观看
1、题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2、文章讲解代码随想录
3、题目
假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。
对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。
示例 1:
输入: g [1,2,3], s [1,1]输出: 1 解释:你有三个孩子和两块小饼干3 个孩子的胃口值分别是1,2,3。虽然你有两块小饼干由于他们的尺寸都是 1你只能让胃口值是 1 的孩子满足。所以你应该输出 1。
示例 2:
输入: g [1,2], s [1,2,3]输出: 2解释:你有两个孩子和三块小饼干2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2.
提示
1 g.length 3 * 10^40 s.length 3 * 10^41 g[i], s[j] 2^31 - 1
4、视频讲解
贪心算法你想先喂哪个小孩| LeetCode455.分发饼干_哔哩哔哩_bilibili
5、思路
为了满足更多的小孩就不要造成饼干尺寸的浪费。
大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子那么就应该优先满足胃口大的。
这里的局部最优就是大饼干喂给胃口大的充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组用大饼干优先满足胃口大的并统计满足小孩数量。
如图 这个例子可以看出饼干 9 只有喂给胃口为 7 的小孩这样才是整体最优解并想不出反例那么就可以撸代码了。
时间复杂度O(nlogn)空间复杂度O(1)
从代码中可以看出我用了一个 index 来控制饼干数组的遍历遍历饼干并没有再起一个 for 循环而是采用自减的方式这也是常用的技巧。
有的同学看到要遍历两个数组就想到用两个 for 循环那样逻辑其实就复杂了。
class Solution {// 优先考虑饼干小饼干先喂饱小胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int start 0;int count 0;for (int i 0; i s.length start g.length; i) {if (s[i] g[start]) {count;start;}}return count;}
}
class Solution {// 优先考虑胃口先喂饱大胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int start s.length - 1;int count 0;for (int index g.length - 1; index 0; index--) {if (start 0 s[start] g[index]) {count;start--;}}return count;}
}
376.摆动序列
1、题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2、文章讲解代码随想录
3、题目
如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列。第一个差如果存在的话可能是正数或负数。少于两个元素的序列也是摆动序列。
例如 [1,7,4,9,2,5] 是一个摆动序列因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。
给定一个整数序列返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些也可以不删除元素来获得子序列剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]输出: 6解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]输出: 7解释: 这个序列包含几个长度为 7 摆动序列其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]输出: 2
4、视频链接
贪心算法寻找摆动有细节| LeetCode376.摆动序列_哔哩哔哩_bilibili
class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length 1) {return nums.length;}// 当前差值int curDiff 0;// 上一个差值int preDiff 0;// 峰值和谷值的个数int count 1;// 遍历数组从1开始因为count初始化为1for (int i 1; i nums.length; i) {// 计算差值curDiff nums[i] - nums[i - 1];// 如果当前差值和上一个差值为一正一负// 等于0的情况表示这个数和前一个数相等不影响结果if ((curDiff 0 preDiff 0) || (curDiff 0 preDiff 0)) {count;preDiff curDiff;}}return count;}
}
53.最大子序和
1、题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2、文章讲解代码随想录
3、题目
给定一个整数数组 nums 找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大为 6。
4、视频链接
贪心算法的巧妙需要慢慢体会LeetCode53. 最大子序和_哔哩哔哩_bilibili
5、思路
暴力解法
暴力解法的思路第一层 for 就是设置起始位置第二层 for 循环遍历数组寻找最大值
class Solution {
public:int maxSubArray(vectorint nums) {int result INT32_MIN;int count 0;for (int i 0; i nums.size(); i) { // 设置起始位置count 0;for (int j i; j nums.size(); j) { // 每次从起始位置i开始遍历寻找最大值count nums[j];result count result ? count : result;}}return result;}
};
时间复杂度O(n^2)空间复杂度O(1)
以上暴力的解法 C勉强可以过其他语言就不确定了。
#贪心解法
贪心贪的是哪里呢
如果 -2 1 在一起计算起点的时候一定是从 1 开始计算因为负数只会拉低总和这就是贪心贪的地方
局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。
全局最优选取最大“连续和”
局部最优的情况下并记录最大的“连续和”可以推出全局最优。
从代码角度上来讲遍历 nums从头开始用 count 累积如果 count 一旦加上 nums[i]变为负数那么就应该从 nums[i1]开始从 0 累积 count 了因为已经变为负数的 count只会拖累总和。
这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
那有同学问了区间终止位置不用调整么 如何才能得到最大“连续和”呢
区间的终止位置其实就是如果 count 取到最大值了及时记录下来了。例如如下代码
if (count result) result count;
1
这样相当于是用 result 记录最大子序和区间和变相的算是调整了终止位置。
如动画所示 红色的起始位置就是贪心每次取 count 为正数的时候开始一个区间的统计。
那么不难写出如下 C代码关键地方已经注释
class Solution {
public:int maxSubArray(vectorint nums) {int result INT32_MIN;int count 0;for (int i 0; i nums.size(); i) {count nums[i];if (count result) { // 取区间累计的最大值相当于不断确定最大子序终止位置result count;}if (count 0) count 0; // 相当于重置最大子序起始位置因为遇到负数一定是拉低总和}return result;}
}; 时间复杂度O(n)空间复杂度O(1)
当然题目没有说如果数组为空应该返回什么所以数组为空的话返回啥都可以了。
常见误区
误区一
不少同学认为 如果输入用例都是-1或者 都是负数这个贪心算法跑出来的结果是 0 这是又一次证明脑洞模拟不靠谱的经典案例建议大家把代码运行一下试一试就知道了也会理解 为什么 result 要初始化为最小负数了。
误区二
大家在使用贪心算法求解本题经常陷入的误区就是分不清是遇到 负数就选择起始位置还是连续和为负选择起始位置。
在动画演示用大家可以发现 4遇到 -1 的时候我们依然累加了为什么呢
因为和为 3只要连续和还是正数就会 对后面的元素 起到增大总和的作用。 所以只要连续和为正数我们就保留。
这里也会有录友疑惑那 4 -1 之后 不就变小了吗 会不会错过 4 成为最大连续和的可能性
其实并不会因为还有一个变量 result 一直在更新 最大的连续和只要有更大的连续和出现result 就更新了那么 result 已经把 4 更新了后面 连续和变成 3也不会对最后结果有影响。
class Solution {public int maxSubArray(int[] nums) {if (nums.length 1) {return nums[0];}int sum Integer.MIN_VALUE;int count 0;for (int i 0; i nums.length; i) {count nums[i];// 取区间累计的最大值sum Math.max(count, sum);// 剪枝如果当前累加和已经小于0那么后面无论再怎么加结果都不会比当前sum大了if (count 0) {count 0;}}return sum;}
}
