个人做旅游网站,网站专题报道页面怎么做的,卢松松的网站,网络推广培训平台 作者#xff1a;დ旧言~ 座右铭#xff1a;松树千年终是朽#xff0c;槿花一日自为荣。 目标#xff1a;了解什么是贪心算法#xff0c;并且掌握贪心算法。 毒鸡汤#xff1a;有些事情#xff0c;总是不明白#xff0c;所以我不会坚持。早安! … 作者დ旧言~ 座右铭松树千年终是朽槿花一日自为荣。 目标了解什么是贪心算法并且掌握贪心算法。 毒鸡汤有些事情总是不明白所以我不会坚持。早安! 专栏选自贪心算法_დ旧言~的博客-CSDN博客 望小伙伴们点赞收藏✨加关注哟 一、算法讲解
贪心算法的定义
贪心算法是指在对问题求解时总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解关键是贪心策略的选择选择的贪心策略必须具备无后效性即某个状态以前的过程不会影响以后的状态只与当前状态有关。
解题的一般步骤是
建立数学模型来描述问题把求解的问题分成若干个子问题对每一子问题求解得到子问题的局部最优解把子问题的局部最优解合成原来问题的一个解。
如果大家比较了解动态规划就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题把解空间的遍历视作对子问题树的遍历则以某种形式对树整个的遍历一遍就可以求出最优解大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解对于这个子问题本身肯定也是最优的)。
动态规划方法代表了这一类问题的一般解法我们自底向上构造子问题的解对每一个子树的根求出下面每一个叶子的值并且以其中的最优值作为自身的值其它的值舍弃。而贪心算法是动态规划方法的一个特例可以证明每一个子树的根的值不取决于下面叶子的值而只取决于当前问题的状况。换句话说不需要知道一个节点所有子树的情况就可以求出这个节点的值。由于贪心算法的这个特性它对解空间树的遍历不需要自底向上而只需要自根开始选择最优的路一直走到底就可以了。
二、算法习题 2.1、第一题 题目链接860. 柠檬水找零 - 力扣LeetCode 题目描述 算法思路
a. 遇到 5 元钱直接收下
b. 遇到 10 元钱找零 5 元钱之后收下
c. 遇到 20 元钱
先尝试凑 10 5 的组合如果凑不出来拼凑 5 5 5 的组合
代码呈现
class Solution {
public:bool lemonadeChange(vectorint bills) {int five 0, ten 0;for (auto x : bills) {if (x 5)five; // 5 元直接收下else if (x 10) // 10 元找零 5 元{if (five 0)return false;five--;ten;} else // 20 元分情况讨论{if (ten five) // 贪⼼{ten--;five--;} else if (five 3) {five - 3;} elsereturn false;}}return true;}
};
2.2、第二题 题目链接2208. 将数组和减半的最少操作次数 - 力扣LeetCode 题目描述 算法思路
每次挑选出「当前」数组中「最⼤」的数然后「减半」直到数组和减少到⾄少⼀半为⽌。
为了「快速」挑选出数组中最⼤的数我们可以利⽤「堆」这个数据结构。
代码呈现
class Solution {
public:int halveArray(vectorint nums) {priority_queuedouble heap; // 创建⼀个⼤根堆double sum 0.0;for (int x : nums) // 把元素都丢进堆中并求出累加和{heap.push(x);sum x;}sum / 2.0; // 先算出⽬标和int count 0;while (sum 0) // 依次取出堆顶元素减半直到减到之前的⼀半以下{double t heap.top() / 2.0;heap.pop();sum - t;count;heap.push(t);}return count;}
};
2.3、第三题 题目链接179. 最大数 - 力扣LeetCode 题目描述 算法思路
可以先优化
将所有的数字当成字符串处理那么两个数字之间的拼接操作以及⽐较操作就会很⽅便。
贪⼼策略
按照题⽬的要求重新定义⼀个新的排序规则然后排序即可。
排序规则
「A 拼接 B」 ⼤于 「B 拼接 A」那么 A 在前B 在后 「A 拼接 B」 等于 「B 拼接 A」那么 A B 的顺序⽆所谓「A 拼接 B」 ⼩于 「B 拼接 A」那么 B 在前A 在后
代码呈现
class Solution {
public:string largestNumber(vectorint nums) {// 优化把所有的数转化成字符串vectorstring strs;for (int x : nums)strs.push_back(to_string(x));// 排序sort(strs.begin(), strs.end(), [](const string s1, const string s2) {return s1 s2 s2 s1;});// 提取结果string ret;for (auto s : strs)ret s;if (ret[0] 0)return 0;return ret;}
};
2.4、第四题 题目链接376. 摆动序列 - 力扣LeetCode 题目描述 算法思路
对于某⼀个位置来说
如果接下来呈现上升趋势的话我们让其上升到波峰的位置如果接下来呈现下降趋势的话我们让其下降到波⾕的位置。因此如果把整个数组放在「折线图」中我们统计出所有的波峰以及波⾕的个数即可
代码呈现
class Solution {
public:int wiggleMaxLength(vectorint nums) {int n nums.size();if (n 2)return n;int ret 0, left 0;for (int i 0; i n - 1; i) {int right nums[i 1] - nums[i]; // 计算接下来的趋势if (right 0)continue; // 如果⽔平直接跳过if (right * left 0)ret; // 累加波峰或者波⾕left right;}return ret 1;}
};
2.5、第五题 题目链接300. 最长递增子序列 - 力扣LeetCode 题目描述 算法思路
我们在考虑最⻓递增⼦序列的⻓度的时候其实并不关⼼这个序列⻓什么样⼦我们只是关⼼最后⼀个元素是谁。这样新来⼀个元素之后我们就可以判断是否可以拼接到它的后⾯。因此我们可以创建⼀个数组统计⻓度为 x 的递增⼦序列中最后⼀个元素是谁。为了尽可能让这个序列更⻓我们仅需统计⻓度为 x 的所有递增序列中最后⼀个元素的「最⼩值」。统计的过程中发现数组中的数呈现「递增」趋势因此可以使⽤「⼆分」来查找插⼊位置。
代码呈现
class Solution {
public:int lengthOfLIS(vectorint nums) {int n nums.size();vectorint ret;ret.push_back(nums[0]);for (int i 1; i n; i) {if (nums[i] ret.back()) // 如果能接在最后⼀个元素后⾯直接放{ret.push_back(nums[i]);} else {// ⼆分插⼊位置int left 0, right ret.size() - 1;while (left right) {int mid (left right) 1;if (ret[mid] nums[i])left mid 1;elseright mid;}ret[left] nums[i]; // 放在 left 位置上}}return ret.size();}
};
2.6、第六题 题目链接334. 递增的三元子序列 - 力扣LeetCode 题目描述 算法思路
不⽤⼀个数组存数据仅需两个变量即可。也不⽤⼆分插⼊位置仅需两次⽐较就可以找到插⼊位 置。
代码呈现
class Solution {
public : bool increasingTriplet(vectorint nums)
{int a nums[0], b INT_MAX;for (int i 1; i nums.size(); i) {if (nums[i] b)return true;else if (nums[i] a)b nums[i];elsea nums[i];}return false;}
};
三、结束语
今天内容就到这里啦时间过得很快大家沉下心来好好学习会有一定的收获的大家多多坚持嘻嘻成功路上注定孤独因为坚持的人不多。那请大家举起自己的小手给博主一键三连有你们的支持是我最大的动力回见。
