手机怎么建立网站,做下载网站赚钱,最新域名网站,网站设计建议 作者#xff1a;დ旧言~ 座右铭#xff1a;松树千年终是朽#xff0c;槿花一日自为荣。 目标#xff1a;了解什么是贪心算法#xff0c;并且掌握贪心算法。 毒鸡汤#xff1a;有些事情#xff0c;总是不明白#xff0c;所以我不会坚持。早安! … 作者დ旧言~ 座右铭松树千年终是朽槿花一日自为荣。 目标了解什么是贪心算法并且掌握贪心算法。 毒鸡汤有些事情总是不明白所以我不会坚持。早安! 专栏选自贪心算法_დ旧言~的博客-CSDN博客 望小伙伴们点赞收藏✨加关注哟 一、算法讲解
贪心算法的定义
贪心算法是指在对问题求解时总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解关键是贪心策略的选择选择的贪心策略必须具备无后效性即某个状态以前的过程不会影响以后的状态只与当前状态有关。
解题的一般步骤是
建立数学模型来描述问题把求解的问题分成若干个子问题对每一子问题求解得到子问题的局部最优解把子问题的局部最优解合成原来问题的一个解。
如果大家比较了解动态规划就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题把解空间的遍历视作对子问题树的遍历则以某种形式对树整个的遍历一遍就可以求出最优解大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解对于这个子问题本身肯定也是最优的)。
动态规划方法代表了这一类问题的一般解法我们自底向上构造子问题的解对每一个子树的根求出下面每一个叶子的值并且以其中的最优值作为自身的值其它的值舍弃。而贪心算法是动态规划方法的一个特例可以证明每一个子树的根的值不取决于下面叶子的值而只取决于当前问题的状况。换句话说不需要知道一个节点所有子树的情况就可以求出这个节点的值。由于贪心算法的这个特性它对解空间树的遍历不需要自底向上而只需要自根开始选择最优的路一直走到底就可以了。
二、算法习题 2.1、第一题 题目链接409. 最长回文串 - 力扣LeetCode 题目描述 算法思路⽤尽可能多的字符去构造回⽂串
如果字符出现偶数个那么全部都可以⽤来构造回⽂串如果字符出现奇数个减去⼀个之后剩下的字符能够全部⽤来构造回⽂串最后再判断⼀下如果有字符出现奇数个就把它单独拿出来放在中间。
代码呈现
class Solution {
public:int longestPalindrome(string s) {// 1. 计数 - ⽤数组模拟哈希表int hash[127] {0};for (char ch : s)hash[ch];// 2. 统计结果int ret 0;for (int x : hash) {ret x / 2 * 2;}return ret s.size() ? ret 1 : ret;}
};
2.2、第二题 题目链接942. 增减字符串匹配 - 力扣LeetCode 题目描述 算法思路
当遇到 I 的时候为了让下⼀个上升的数可选择的「范围更多」当前选择「最⼩」的那个数当遇到 D 的时候为了让下⼀个下降的数可选择的「范围更多」选择当前「最⼤」的那个数。
代码呈现
class Solution {
public:vectorint diStringMatch(string s) {int left 0, right s.size(); // ⽤ leftright 标记最⼩值和最⼤值vectorint ret;for (auto ch : s) {if (ch I)ret.push_back(left);elseret.push_back(right--);}ret.push_back(left); // 把最后⼀个数放进去return ret;}
};
2.3、第三题 题目链接455. 分发饼干 - 力扣LeetCode 题目描述 算法思路
先将两个数组排序。针对胃⼝较⼩的孩⼦从⼩到⼤挑选饼⼲
如果当前饼⼲能满⾜直接喂最⼩的饼⼲都能满⾜不要浪费⼤饼⼲如果当前饼⼲不能满⾜放弃这个饼⼲去检测下⼀个饼⼲这个饼⼲连最⼩胃⼝的孩⼦都⽆法满⾜更别提那些胃⼝⼤的孩⼦了。
代码呈现
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {// 先排序sort(g.begin(), g.end());sort(s.begin(), s.end());// 利⽤双指针找答案int ret 0, n s.size();for (int i 0, j 0; i g.size() j n; i, j) {while (j n s[j] g[i])j; // 找饼⼲if (j n)ret;}return ret;}
};
2.4、第四题 题目链接553. 最优除法 - 力扣LeetCode 题目描述 算法思路
在最终的结果中前两个数的位置是⽆法改变的。因为每⼀个数的都是⼤于等于 2 的为了让结果更⼤我们应该尽可能的把剩下的数全都放在「分⼦」上。
代码呈现
class Solution {
public:string optimalDivision(vectorint nums) {int n nums.size();// 先处理两个边界情况if (n 1) {return to_string(nums[0]);}if (n 2) {return to_string(nums[0]) / to_string(nums[1]);}string ret to_string(nums[0]) /( to_string(nums[1]);for (int i 2; i n; i) {ret / to_string(nums[i]);}ret );return ret;}
};
2.4、第五题 题目链接45. 跳跃游戏 II - 力扣LeetCode 题目描述 算法思路
⽤类似层序遍历的过程将第 i 次跳跃的「起始位置」和「结束位置」找出来⽤这次跳跃的情况更新出下⼀次跳跃的「起始位置」和「终⽌位置」。这样「循环往复」就能更新出到达 n - 1 位置的最⼩跳跃步数。
代码呈现
class Solution {
public:int jump(vectorint nums) {int left 0, right 0, maxPos 0, ret 0, n nums.size();while (left right) // 保险的写法以防跳不到 n - 1 的位置{if (maxPos n - 1) // 先判断⼀下是否已经能跳到最后⼀个位置{return ret;}// 遍历当成层更新下⼀层的最右端点for (int i left; i right; i) {maxPos max(maxPos, nums[i] i);}left right 1;right maxPos;ret;}return -1; // 跳不到的情况}
};
2.6、第六题 题目链接55. 跳跃游戏 - 力扣LeetCode 题目描述 算法思路
和 跳跃游戏II ⼀样仅需修改⼀下返回值即可。
代码呈现
class Solution {
public:bool canJump(vectorint nums) {int left 0, right 0, maxPos 0, n nums.size();while (left right) {if (maxPos n - 1) {return true;}for (int i left; i right; i) {maxPos max(maxPos, nums[i] i);}left right 1;right maxPos;}return false;}
};
三、结束语
今天内容就到这里啦时间过得很快大家沉下心来好好学习会有一定的收获的大家多多坚持嘻嘻成功路上注定孤独因为坚持的人不多。那请大家举起自己的小手给博主一键三连有你们的支持是我最大的动力回见。
