贪心算法（一）
创始人
2025-05-31 00:15:21

一、概念

贪心算法的核心思想是，在处理一个大问题时，划分为多个局部并在每个局部选择最优解，并且认为在每个局部选择最优解，那么最后全局的问题得到的就是最优解。

贪心算法可以解决一些问题，但是不适用于所有问题，也不保证使用贪心算法得出的就是最优解。

维基百科更详细的解释：

 二、分配问题

先来看一道简单的分配问题：

力扣icon-default.png?t=N176https://leetcode.cn/problems/assign-cookies/解题思路：

孩子的胃口值需要小于等于饼干大小，根据贪心算法的局部最优解的思想，就是给每个孩子分配能满足她胃口的最小的饼干，且应该优先处理胃口小的孩子。

C++代码：

class Solution {
public:int findContentChildren(vector& g, vector& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int i = 0, j = 0;while(i

下面这题难度略大一些，同样也是分配问题：

力扣icon-default.png?t=N176https://leetcode.cn/problems/candy/

解题思路：

每个孩子需要与左右两边的孩子比较评分，贪心算法的运用在于从左到右遍历一次评分数组，每个元素只考虑是否比左边的元素大，再从右到左遍历一次评分数组，每个元素只考虑是否比右边的元素大。这样两次遍历后，就能得到同时满足左右限制的糖果数量了。

C++代码：

class Solution {
public:int candy(vector& ratings) {int n = ratings.size();vector c(n,1);for(int i=1;iratings[i-1]){c[i] = c[i-1] + 1;}}for(int i=n-2;i>=0;i--){if(ratings[i]>ratings[i+1]){c[i] = max(c[i], c[i+1] + 1);}}return accumulate(c.begin(), c.end(), 0);}
};

上一篇：这一次，吃了Redis的亏，也败给了GPT

下一篇：“粽”情端午 幸福邻里！燕罗街道罗田社区开展端午游园活动

相关内容

热门资讯

“土味消费”圈粉！特色乡村文旅... 央视网消息：新年启步，万象更新。各地乡村文旅融合点燃了消费引擎，为振兴开局注入蓬勃新动能。 乡村冰雪...
瓷坛售酒机 瓷坛售酒机：传统容器与现代零售的智能融合 在白酒零售领域，一场静悄悄的变革正在发生。曾经作为储酒与...
国内酒水源头正品十大推荐排行榜... 在琳琅满目的酒水市场中，寻找源头正品如同沙里淘金。消费者渴望品质保障，商家追求稳定供应，而真正的行业...
做酒容易管人难：酒业新势力的H... 重庆饮马晴川贸易有限责任公司成立于2021年，尽管年轻，却已是酒水赛道上一股不可忽视的“新势力”。作...
山姆开售年份酒！你囤的酒是涨还... 近日，南都湾财社记者在成都山姆会员商店的酒类专区发现，年份酒成为山姆白酒区陈列的重点，五粮液、国窖1...