开普网站建设公司,企业网站模板下载尽在,软件商店下载安装应用,惠州seo工作室一、概念
贪心算法的核心思想是#xff0c;在处理一个大问题时#xff0c;划分为多个局部并在每个局部选择最优解#xff0c;并且认为在每个局部选择最优解#xff0c;那么最后全局的问题得到的就是最优解。
贪心算法可以解决一些问题#xff0c;但是不适用于所有问题在处理一个大问题时划分为多个局部并在每个局部选择最优解并且认为在每个局部选择最优解那么最后全局的问题得到的就是最优解。
贪心算法可以解决一些问题但是不适用于所有问题也不保证使用贪心算法得出的就是最优解。
维基百科更详细的解释 二、分配问题
先来看一道简单的分配问题
力扣https://leetcode.cn/problems/assign-cookies/解题思路
孩子的胃口值需要小于等于饼干大小根据贪心算法的局部最优解的思想就是给每个孩子分配能满足她胃口的最小的饼干且应该优先处理胃口小的孩子。
C代码
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int i 0, j 0;while(ig.size()js.size()){if(g[i]s[j]){i;}j;}return i;}
};
下面这题难度略大一些同样也是分配问题
力扣https://leetcode.cn/problems/candy/
解题思路
每个孩子需要与左右两边的孩子比较评分贪心算法的运用在于从左到右遍历一次评分数组每个元素只考虑是否比左边的元素大再从右到左遍历一次评分数组每个元素只考虑是否比右边的元素大。这样两次遍历后就能得到同时满足左右限制的糖果数量了。
C代码
class Solution {
public:int candy(vectorint ratings) {int n ratings.size();vectorint c(n,1);for(int i1;in;i){if(ratings[i]ratings[i-1]){c[i] c[i-1] 1;}}for(int in-2;i0;i--){if(ratings[i]ratings[i1]){c[i] max(c[i], c[i1] 1);}}return accumulate(c.begin(), c.end(), 0);}
};
