文章目录

一、算法思想二、分配问题2.1 Leetcode 4552.1.1 题目描述2.1.2 输入输出格式2.1.3求解思路2.1.4 代码示例（C++）2.2 Leetcode 1352.2.1 题目描述2.2.2 输入输出格式2.2.3求解思路2.2.4 代码示例（C++）2.3 Leetcode 6052.3.1 题目描述2.3.2 输入输出格式2.1.3求解思路2.1.4 代码示例（C++）三、区间问题3.1 Leetcode4353.1.1 题目描述3.1.2 输入输出格式3.1.3求解思路3.1.4 代码示例（C++）3.2 Leetcode4523.2.1 题目描述3.2.2 输入输出格式3.2.3求解思路3.2.4 代码示例（C++）3.3 Leetcode7633.3.1 题目描述3.2.2 输入输出格式3.2.3 代码示例（C++）

一、算法思想

贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的

二、分配问题

2.1 Leetcode 455

2.1.1 题目描述

有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃

最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

2.1.2 输入输出格式

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

2.1.3求解思路

将孩子胃口值和饼干大小从小到大进行排序。饼干优先提供给胃口值最小的孩子，直到饼干被分配完。

2.1.4 代码示例（C++）

class Solution {public:int findContentChildren(vector<int>& g, vector<int>& s) {int num = 0;//记录孩子的最大数目int i = 0;//遍历饼干sort(g.begin(), g.end());//将孩子数组排序sort(s.begin(), s.end());//将饼干数组排序while (num < g.size() && i < s.size()) {if (g[num] <= s[i]) {num++;}i++;}return num;}};

2.2 Leetcode 135

2.2.1 题目描述

一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一

个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所有孩子至少要有一个糖果。求解最少需要多少个糖果。

2.2.2 输入输出格式

输入：[1,0,2]输出：5解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。

2.2.3求解思路

从左往右遍历，当右边的孩子评分高于左边的孩子时，右边孩子是左边孩子糖果数+1;从右往左遍历，当左边孩子的评分高于右边孩子评分时，左边孩子的糖果数等于自身糖果数和右边孩子糖果数+1的最大值。

2.2.4 代码示例（C++）

class Solution {public:int candy(vector<int>& ratings) {int size = ratings.size();//储存孩子个数if (size < 2) {//当孩子的个数小于2时，返回孩子个数1或0return size;}vector<int> num(size, 1);//初始化一个大小为size,数值为1的糖果数组//从左往右遍历，当右边的孩子评分高于左边的孩子时，右边孩子是左边孩子糖果数+1for (int i = 1; i < size; i++) {if (ratings[i] > ratings[i - 1]) {num[i] = num[i - 1] + 1;}}//从右往左遍历，当左边孩子的评分高于右边孩子评分时，左边孩子的糖果数等于自身糖果数和右边孩子糖果数+1的最大值。for (int i = size - 1; i > 0; i--) {if (ratings[i - 1] > ratings[i]) {num[i - 1] = max(num[i - 1], num[i] + 1);}}return accumulate(num.begin(), num.end(), 0);}};

2.3 Leetcode 605

2.3.1 题目描述

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false

2.3.2 输入输出格式

输入：flowerbed = [1,0,0,0,1], n = 1输出：true

2.1.3求解思路

从左往右进行遍历，判断此位置是否种植花，若未种植，则判断此花左右两边是否种植花，若两边均未种植花，则此位置可以种植花；反之往前移动，继续判断。

2.1.4 代码示例（C++）

class Solution {public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int size = flowerbed.size();int num = 0;if (n == 0) {return true;}if (size == 1 ) {if (flowerbed[0] == 0) {num = 1;return num >= n;}else {return num >= n;}}else if (size == 2) {if (flowerbed[0] == 0 && flowerbed[1] == 0) {num = 1;}return num >= n;}else {for (int i = 0; i < size; i++) {if (i == 0) {if (flowerbed[i + 1] == 0 && flowerbed[i] == 0) {num++;flowerbed[i] = 1;}else {continue; }}else if (i == size - 1) {if (flowerbed[i - 1] == 0 && flowerbed[i] == 0) {num++;flowerbed[i] = 1;}else {continue; }}else {if (flowerbed[i - 1] == 0 && flowerbed[i] == 0 && flowerbed[i + 1] == 0) {num++;flowerbed[i] = 1;}}}return num >= n;}}};

三、区间问题

3.1 Leetcode435

3.1.1 题目描述

给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

3.1.2 输入输出格式

输入是一个数组，数组由多个长度固定为 2 的数组组成，表示区间的开始和结尾。输出一个

整数，表示需要移除的区间数量。

Input: [[1,2], [2,4], [1,3]]Output: 1在这个样例中，我们可以移除区间 [1,3]，使得剩余的区间 [[1,2], [2,4]] 互不重叠。

3.1.3求解思路

根据贪心算法，在选择要保留区间时：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。

3.1.4 代码示例（C++）

class Solution {private:static bool func(vector<int>& a,vector<int >& b){return a[1] < b[1];}public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) {return 0;}int size = intervals.size();int num = 0;sort(intervals.begin(), intervals.end(), func);int pre = intervals[0][1];for (int i = 1; i < size; i++) {if (intervals[i][0] < pre) {num++;}else {pre = intervals[i][1];}}return num;}};

3.2 Leetcode452

3.2.1 题目描述

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数

3.2.2 输入输出格式

输入：points = [[10,16],[2,8],[1,6],[7,12]]输出：2解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

3.2.3求解思路

根据贪心算法，按照气球直径末尾位置从小到大排序，每一次射箭，必须满足末尾位置最小的气球被射穿。

3.2.4 代码示例（C++）

class Solution {private:static bool func(vector<int> &a, vector<int> &b) {return (a[1]<b[1]);}public:int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end(), func);int num = 0;int size = points.size();if (size == 1) {return 1;}int start = 0;int end = 1;while (start < size && end < size) {while (points[start][1] >= points[end][0]) {end++;if (end >= size || start >= size) {break;}}num++;start = end;}return num;}};

3.3 Leetcode763

3.3.1 题目描述

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

3.2.2 输入输出格式

输入：S = "ababcbacadefegdehijhklij"输出：[9,7,8]解释：划分结果为 "ababcbaca", "defegde", "hijhklij"。每个字母最多出现在一个片段中。像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少

3.2.3 代码示例（C++）

class Solution {public:vector<int> partitionLabels(string s) {if (s.length() == 1) {vector<int> ans;ans.push_back(1);return ans;}int num[200] = {0 };for (int i = s.length(); i >= 0; i--) {if (num[s[i]] == 0) {num[s[i]] = i;}}vector<int> ans;int start = 0;int end = 0;for(int i=0;i<s.length();i++){end=max(end,num[s[i]]);if(i==end){ans.push_back(end-start+1);start=end+1;}}return ans;}};

如果觉得《Leetcode刷题：贪心算法》对你有帮助，请点赞、收藏，并留下你的观点哦！