网站建设和维护一年的费用,wordpress文章摘录,记录开发wordpress主题,怎么知道公司网站是哪家做的贪心算法理论基础
代码随想录 (programmercarl.com)
贪心算法理论基础#xff01;_哔哩哔哩_bilibili 贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。 例如#xff0c;有一堆钞票#xff0c;你可以拿走十张#xff0c;如果想达到最大的金额#xff…贪心算法理论基础
代码随想录 (programmercarl.com)
贪心算法理论基础_哔哩哔哩_bilibili 贪心的本质是选择每一阶段的局部最优从而达到全局最优。 例如有一堆钞票你可以拿走十张如果想达到最大的金额你要怎么拿指定每次拿最大的最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优最后拿走最大数额的钱就是推出全局最优。 有没有什么套路可以一看就看出来是贪心 贪心算法并没有固定的套路。所以唯一的难点就是如何通过局部最优推出整体最优。 如何能看出局部最优是否能推出整体最优呢有没有什么固定策略或者套路呢 也没有 靠自己手动模拟如果模拟可行就可以试一试贪心策略如果不可行可能需要动态规划。 如何验证可不可以用贪心算法呢 最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。
面试中基本不会让面试者现场证明贪心的合理性代码写出来跑过测试用例即可或者自己能自圆其说理由就行了。
刷题或者面试的时候手动模拟一下感觉可以局部最优推出整体最优而且想不到反例那么就试一试贪心。
贪心一般解题步骤
贪心算法一般分为如下四步
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
这个四步其实过于理论化了我们平时在做贪心类的题目 很难去按照这四步去思考真是有点“鸡肋”。
做题的时候只要想清楚 局部最优 是什么如果推导出全局最优其实就够了。
455.分发饼干 文档讲解代码随想录 (programmercarl.com) 视频讲解贪心算法你想先喂哪个小孩| LeetCode455.分发饼干_哔哩哔哩_bilibili 状态能直接做出来。文档提供了两种思路我用的是思路2。 思路1
为了满足更多的小孩就不要造成饼干尺寸的浪费。
大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子那么就应该优先满足胃口大的。
这里的局部最优就是大饼干喂给胃口大的充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组用大饼干优先满足胃口大的并统计满足小孩数量。
// 时间复杂度O(nlogn)
// 空间复杂度O(1)
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int index s.size() - 1; // 饼干数组的下标int result 0;for (int i g.size() - 1; i 0; i--) { // 遍历胃口 if (index 0 s[index] g[i]) { // 遍历饼干 result;index--;}}return result;}
};从代码中可以看出我用了一个index来控制饼干数组的遍历遍历饼干并没有再起一个for循环而是采用自减的方式这也是常用的技巧。
注意事项
上面代码中可以看出来是先遍历的胃口在遍历的饼干那么可不可以 先遍历 饼干在遍历胃口呢其实是不可以的。
外面的for 是里的下标i 是固定移动的而if里面的下标 index 是符合条件才移动的。若 for 控制的是饼干 if 控制胃口就出现如下情况 if 里的 index 指向 胃口 10 for里的i指向饼干9因为 饼干9 满足不了 胃口10所以 i 持续向前移动而index 走不到s[index] g[i] 的逻辑所以index不会移动那么当i 持续向前移动最后所有的饼干都匹配不上。
所以 一定要for 控制 胃口里面的if控制饼干。
思路2
小饼干先喂饱小胃口
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index 0;for(int i 0; i s.size(); i) { // 饼干if(index g.size() g[index] s[i]){ // 胃口index;}}return index;}
};这种写法两个循环的顺序改变了先遍历的饼干在遍历的胃口这是因为遍历顺序变了我们是从小到大遍历。
理由在上面 “注意事项”中 已经讲过。
376. 摆动序列 文档讲解代码随想录 (programmercarl.com) 视频讲解贪心算法寻找摆动有细节| LeetCode376.摆动序列_哔哩哔哩_bilibili 状态做不出来。很难情况很多。 思路
来分析一下要求删除元素使其达到最大摆动序列应该删除什么元素呢用示例二来举例如图所示 局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。
整体最优整个序列有最多的局部峰值从而达到最长摆动序列。
实际操作上其实连删除的操作都不用做因为题目要求的是最长摆动子序列的长度所以只需要统计数组的峰值数量就可以了
这就是贪心所贪的地方让峰值尽可能的保持峰值然后删除单一坡度上的节点
在计算是否有峰值的时候大家知道遍历的下标i 计算prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - nums[i]如果prediff 0 curdiff 0 或者 prediff 0 curdiff 0 此时就有波动就需要统计。
这是我们思考本题的一个大题思路但本题要考虑三种情况
情况一上下坡中有平坡情况二数组首尾两端情况三单调坡中有平坡
情况一上下坡中有平坡 它的摇摆序列长度是多少呢 其实是长度是3也就是我们在删除的时候 要不删除左面的三个2要不就删除右边的三个2。
如图可以统一规则删除左边的三个2 在图中当i指向第一个2的时候prediff 0 curdiff 0 当 i 指向最后一个2的时候 prediff 0 curdiff 0。
如果我们采用删左面三个2的规则那么 当 prediff 0 curdiff 0 也要记录一个峰值因为他是把之前相同的元素都删掉留下的峰值。所以我们记录峰值的条件应该是 (preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)。
情况二数组首尾两端
数组最左面和最右面如何统计呢
例如序列[2,5]如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。
因为我们在计算 prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - nums[i]的时候至少需要三个数字才能计算而数组只有两个数字。
这里我们可以写死就是 如果只有两个元素且元素不同那么结果为2。
不写死的话如果和我们的判断规则结合在一起呢
可以假设数组最前面还有一个数字那这个数字应该是什么呢
之前我们在 讨论 情况一相同数字连续 的时候 prediff 0 curdiff 0 或者 0 也记为波谷。
那么为了规则统一针对序列[2,5]可以假设为[2,2,5]这样它就有坡度了即preDiff 0如图 针对以上情形result初始为1默认最右面有一个峰值此时curDiff 0 preDiff 0那么result计算了左面的峰值最后得到的result就是2峰值个数为2即摆动序列长度为2
经过以上分析后我们可以写出如下代码
class Solution {
public:int wiggleMaxLength(vectorint nums) {if (nums.size() 1) return nums.size();int curDiff 0; // 当前一对差值int preDiff 0; // 前一对差值int result 1; // 记录峰值个数序列默认序列最右边有一个峰值for (int i 0; i nums.size() - 1; i) {curDiff nums[i 1] - nums[i];// 出现峰值if ((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) {result;}preDiff curDiff;}return result;}
};情况三单调坡度有平坡 图中我们可以看出上面的代码在三个地方记录峰值但其实结果因为是2因为 单调中的平坡 不能算峰值即摆动。
之所以会出问题是因为我们实时更新了 prediff。
那么我们应该什么时候更新prediff呢
我们只需要在 这个坡度 摆动变化的时候更新prediff就行这样prediff在 单调区间有平坡的时候 就不会发生变化造成我们的误判。
所以本题的最终代码为
class Solution {
public:int wiggleMaxLength(vectorint nums) {if (nums.size() 1) return nums.size();int curDiff 0; // 当前一对差值int preDiff 0; // 前一对差值int result 1; // 记录峰值个数序列默认序列最右边有一个峰值for (int i 0; i nums.size() - 1; i) {curDiff nums[i 1] - nums[i];// 出现峰值if ((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) {result;preDiff curDiff; // 注意这里只在摆动变化的时候更新prediff }}return result;}
};53. 最大子序和 文档讲解代码随想录 (programmercarl.com) 视频讲解贪心算法的巧妙需要慢慢体会LeetCode53. 最大子序和_哔哩哔哩_bilibili 状态暴力法可以做出来贪心法做不出来。 思路 **贪心贪的是哪里呢**如果 -2 1 在一起计算起点的时候一定是从1开始计算因为负数只会拉低总和这就是贪心贪的地方 局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。 全局最优选取最大“连续和”。 局部最优的情况下并记录最大的“连续和”可以推出全局最优。 从代码角度上来讲遍历nums从头开始用count累积如果count一旦加上nums[i]变为负数那么就应该从nums[i1]开始从0累积count了因为已经变为负数的count只会拖累总和。 这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
那有同学问了区间终止位置不用调整么 如何才能得到最大“连续和”呢
区间的终止位置其实就是如果count取到最大值了及时记录下来了。例如如下代码
if (count result) result count;这样相当于是用result记录最大子序和区间和变相的算是调整了终止位置。
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;}
};常见误区
那 4 -1 之后 不就变小了吗 会不会错过 4 成为最大连续和的可能性
其实并不会因为还有一个变量result 一直在更新 最大的连续和只要有更大的连续和出现result就更新了那么result已经把4更新了后面 连续和变成3也不会对最后结果有影响。
