leetcode 经典贪心算法题目(思路、方法、code)

Helen ·

更新时间:2024-09-21

· 697 次阅读

用于回顾数据结构与算法时刷题的一些经验记录

(提出对应的贪心算法时最好自己举例子试试能否可行)

文章目录[455. 分发饼干](https://leetcode-cn.com/problems/assign-cookies/)[376. 摆动序列](https://leetcode-cn.com/problems/wiggle-subsequence/)[402. 移掉K位数字](https://leetcode-cn.com/problems/remove-k-digits/)[55. 跳跃游戏](https://leetcode-cn.com/problems/jump-game/)[45. 跳跃游戏 II](https://leetcode-cn.com/problems/jump-game-ii/)[134. 加油站](https://leetcode-cn.com/problems/gas-station/)[452. 用最少数量的箭引爆气球](https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/)[135. 分发糖果](https://leetcode-cn.com/problems/candy/)[921. 使括号有效的最少添加](https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/)[1326. 灌溉花园的最少水龙头数目](https://leetcode-cn.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/) 455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 iii ，都有一个胃口值 gigigi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 jjj，都有一个尺寸sjsjsj 。如果 sj>=gisj >= gisj>=gi，我们可以将这个饼干jjj分配给孩子iii，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

你可以假设胃口值为正,且一个小朋友最多只能拥有一块饼干。

示例 1:
输入: [1,2,3], [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。

分析：由于每个孩子最多只需要一个饼干，并且我们需要的是满足尽可能多的孩子，因此我们有如下策略

如果一个孩子能被更小的饼干满足，则就应该采用更小的饼干，尽量保留大的饼干给胃口更大的孩子如果一个饼干不能满足胃口最小的孩子，故它将不能满足每个孩子

因此，我们可以对饼干尺寸和孩子胃口进行排序，然后遍历饼干尺寸。

如果当前饼干可以满足当前孩子，就满足该孩子，向后遍历饼干和孩子胃口如果当前饼干不可以满足当前孩子，说明该饼干不会再被利用，向后遍历饼干如果孩子或者饼干遍历完了，则返回结果即可

class Solution {
public:
    int findContentChildren(vector& g, vector& s) 
    {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int cookie=0;  //表示cookie遍历到第几个了 
        int child=0;
        while(child<g.size()&&cookie<s.size())
        {
        	if(g[child]<=s[cookie]) //该饼干可以满足孩子，使用即可 
        		child++;  //孩子向后遍历 
        	cookie++;  //饼干向后遍历 
		}
		return child;
    }
};

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

分析：

可视化数字发现贪心规律

分析题目可知，实际上摇摆序列就是画到坐标轴上连线后，上下波动的线条的每个顶点。
原创文章 76获赞 88访问量 3万+ 关注私信展开阅读全文
作者：coding丁