数据结构】Leetcode——贪心算法 经典题"/>
【数据结构】Leetcode——贪心算法 经典题
Contents
- 1 分发饼干(455)
- 2 摆动序列(376)
- 3 最大子序和(53)
- 4 买卖股票的最佳时机②(122)
- 5 跳跃游戏(55)
- 6 跳跃游戏②(45)
- 7 K 次取反后最大化的数组和(1005)
- 8 加油站(134)
- 9 分发糖果(135)
- 10 柠檬水找零(860)
- 11 根据身高重建队列(406)
- 12 用最少数量的箭引爆气球(452)
- 13 无重叠区间 (435)
- 14 划分字母区间(763)
- 15 合并区间(56)
- 16 单调递增的数字(738)
- 17 单调递增的数字(714)
开始之前学习一个单词热热身：
invigorating 英[ɪnˈvɪɡəreɪtɪŋ]
adj. 提神的; 令人精力充沛的; 振奋精神的;
v. 使生气勃勃; 使精神焕发; 使蒸蒸日上; 使兴旺发达;
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
贪心算法并没有固定的套路。说白了就是常识性推导加上举反例。
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
接下来的17到贪心算法题，是简单困难交织在一起的，因贪心算法并不像回溯法那样有套路可言。这17道题可以分类为：
贪心简单题：分发饼干、K次取反后最大化的数组、柠檬水找零
贪心中等题：摆动序列、单调递增的数字
贪心解决区间问题：跳跃游戏、跳跃游戏II、用最少数量的箭引爆气球、无重叠区间、划分字母区间、合并区间
两个维度权衡问题：在出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个维度。包括分发糖果、根据身高重建队列
1 分发饼干(455)
题目：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例：
思路：
本题的局部最优就是大饼干喂给胃口大的，全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略，先将饼干数组和小孩数组排序，然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int index = s.size()-1;int result=0;for(int i=g.size()-1; i>=0; i--){if(index>=0 && g[i]<=s[index]){result++;index--;}}return result;}
};
2 摆动序列(376)
题目：
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如，[1,7,4,9,2,5]是一个摆动序列，因为差值(6,-3,5,-7,3)是正负交替出现的。相反, [1,4,7,2,5] 和[1,7,4,5,5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
思路：
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
其实题目中提到的删除操作可以不做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了。
数列的第一个起点一定包含在最后的最长摆动子序列中，故初始化result=1。
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if(nums.size()<=1) return nums.size();int curDiff = 0;int preDiff = 0;int result = 1;for(int i=1; i<nums.size();i++){curDiff = nums[i] - nums[i-1];if(curDiff>0 && preDiff<=0 || curDiff<0 && preDiff>=0){result++;preDiff = curDiff;}}return result;}
};
3 最大子序和(53)
题目:
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;int temp = 0; // 不要忘记初始化!for(int i=0; i<nums.size(); i++){temp = temp + nums[i];if(result < temp) result = temp;if(temp < 0) temp = 0;}return result;}
};
4 买卖股票的最佳时机②(122)
题目：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
思路：
假若第一天买入，第三天卖出，则利润为price[3] - price[0]
而其利润也可以写为：
(price[3] - price[2])+(price[2] - price[1])+(price[1] - price[0])
这样，不管是第几天到第几天的利润，从可以由相邻两天的利润所得出；
从而可以算出相邻两天间的利润，然后只将正利润求和即为最大利润。（只求和正利润，就是贪心所在。）
class Solution {
public:int maxProfit(vector<int>& prices) {int res;for(int i=1; i<prices.size(); i++){int profit = prices[i] - prices[i-1];if(profit > 0){res += profit;}}return res;}
};
5 跳跃游戏(55)
题目：
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
思路：
1、处于数组的某个位置，不一定必须跳该位置的值的步数，小于等于均可；
2、问题可转化为数组在某个位置的值 与该值可覆盖数组范围内的值的和 可不可以覆盖到数组尾部；
3、贪心局部最优解为每次取最大跳跃步数；得到整体最优解，即得到整体最大覆盖范围；
class Solution {
public:bool canJump(vector<int>& nums) {int length = 0;if(nums.size()==1) return true;for(int i=0; i<=length; i++){length = max(i+nums[i], length);if(length >= nums.size()-1) return true;}return false;}
};
6 跳跃游戏②(45)
题目：
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
思路：
因为要求最小跳跃数，则跳跃步数加一时要十分谨慎，即计算好当前和下一步覆盖范围的和的最大值不能到达数组最后一个位置时，才可以加一；
当移动下标达到了当前这一步的最大覆盖范围最远距离，还没有到达终点的话，那么就必须再走一步来增加覆盖距离，直到覆盖范围覆盖了终点。
class Solution {
public:int jump(vector<int>& nums) {int res = 0;int curDistance = 0; //当前覆盖最远距离下标int nextDistance = 0; //下一步覆盖最远距离下标for(int i=0; i<nums.size(); i++){nextDistance = max(i+nums[i], nextDistance);if(i == curDistance){if(curDistance != nums.size()-1){res++;curDistance = nextDistance;if(nextDistance > nums.size()-1)return res;}else break;}}return res;}
};
7 K 次取反后最大化的数组和(1005)
题目：
给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
思路：
1、将数组按绝对值从小到大排序；
2、从后向前遍历数组，每遇到一个负数，将其变为正数，K–；
3、若遍历完毕后，K仍大于0，则反复转变数值最小的元素，将K用完；
4、求最终数组的元素和，即为结果。
class Solution {
static bool cmp(int a, int b){return abs(a)<abs(b);
}
public:int largestSumAfterKNegations(vector<int>& A, int K) {int res = 0;sort(A.begin(), A.end(), cmp);for(int i=A.size()-1; i>=0; i--){if(A[i]<0 && K>0){A[i] *= -1;K--;}}while(K){A[0] *= -1;K--;}for(auto &j:A){res += j;}return res;}
};
8 加油站(134)
题目：
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
示例：
for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历！！
如果总油量减去总消耗大于等于零，则一定可以跑完一圈，说明剩油量一定是大于等于零；
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。
「局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置」。
// 暴力解法，学习用while对数组进行环形遍历
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {for(int i = 0; i<gas.size(); i++){int rest = gas[i] - cost[i];int index = (i+1)%gas.size();while(rest>0 && index!=i){rest += gas[index] - cost[index];index = (index + 1) % gas.size();}if(rest >= 0 && index==i) return i;}return -1;}
};// 贪心解法
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int totalSum = 0;int start = 0;for(int i = 0; i<gas.size(); i++){curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if(curSum < 0){start = i + 1;curSum = 0;}}if(totalSum < 0) return -1;return start;}
};
9 分发糖果(135)
题目：
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
示例：
思路：
1、首先初始化一个全为1的数组，表示每个孩子至少给一个糖果；
2、先确定右边评分大于左边的情况（也就是从前向后遍历）。此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果；
3、再确定左边评分大于右边的情况（从后向前遍历）。此时局部最优：取candy[i + 1] + 1 和 candy[i] 最大的糖果数量，保证第i个小孩的糖果数量即大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
4、达到全局最优，统计结果即可。
class Solution {
public:int candy(vector<int>& ratings) {vector<int> candy(ratings.size(), 1); // 初始化每个都给1个糖果int res = 0;for(int i=0; i<ratings.size()-1; i++){ // 从左到右遍历 ->找右边比左边大的if(ratings[i]<ratings[i+1]){candy[i+1] = candy[i]+1;}}for(int j=ratings.size()-1; j>0; j--){ // 从右到左遍历 ->找左边比右边大的 取最大值；if(ratings[j-1]>ratings[j]){candy[j-1] = max(candy[j]+1, candy[j-1]);}}for(int &m: candy){res += m;}return res;}
};
10 柠檬水找零(860)
题目：
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
示例：
思路：
分三种情况考虑：
情况一：账单是5，直接收下；
情况二：账单是10，消耗一个5，增加一个10；
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5、
因为顾客排队购买支付，故从左向右遍历数组，不断判断符合以上哪种情况，并记录手中不同面值的钞票数量，若遍历到数组尾部，即返回ture。
class Solution {
public:bool lemonadeChange(vector<int>& bills) {vector<int> moneyNums(3, 0); // 0->5, 1->10, 2->20for(int i=0; i<bills.size(); i++){if(bills[i]==5){moneyNums[0]++;}if(bills[i]==10){if(moneyNums[0]==0)return false;else{moneyNums[0]--;moneyNums[1]++;}}if(bills[i]==20){if(moneyNums[1]>0 && moneyNums[0]>0){moneyNums[1]--;moneyNums[0]--;moneyNums[2]++;}else if(moneyNums[0]>=3){moneyNums[0] = moneyNums[0]-3;moneyNums[2]++;}else return false;}}return true;}
};
11 根据身高重建队列(406)
题目：
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
思路：
遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。
「如果两个维度一起考虑一定会顾此失彼」。
1、首先按身高从大到小排（身高相同的话则k小的站前面），让高个子在前面。此时确定了一个维度——身高，前面的节点一定都比本节点高；
2、按照k为下标重新插入队列就可以了，为什么呢？
按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点（因为后序插入的节点的身高不会影响到身高高的people的k值），最终按照k的规则完成了队列。
class Solution {
static bool cmp(const vector<int> a, const vector<int> b){if(a[0]>b[0]) return true;if(a[0]==b[0] && a[1]<b[1]) return true;return false;
}
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(), cmp);vector<vector<int>> res;for(int i=0; i<people.size(); i++){int position = people[i][1];res.insert(res.begin()+position, people[i]);}return res;}
};
12 用最少数量的箭引爆气球(452)
题目：
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
示例：
思路：
刚看到题的时候可能有些没看懂，上面的示例对应的解答如上图（来自代码随想录）。那么该题的思路为：
1、对每个气球子数组按xstart进行从小到大排序；「为了让气球尽可能的重叠，需要对数组进行排序」。
2、当下一个气球的xstart小于等于上一个气球的xend，说明这两个气球有重叠；若判断没重叠的话，res加一；
3、若没有重叠的情况下，更新xend的值以便于对下一个气球进行比较；其值为当前气球的xend和下一个气球xend中的最小值；
class Solution {
static bool cmp(vector<int>& a, vector<int>& b){return a[0] < b[0];
}
public:int findMinArrowShots(vector<vector<int>>& points) {int res = 1;sort(points.begin(), points.end(), cmp);if(points.size()==0) return 0;for(int i=1; i<points.size(); i++){if(points[i][0] > points[i-1][1]){res++;}else{points[i][1] = min(points[i-1][1], points[i][1]);}}return res;}
};
13 无重叠区间 (435)
题目：
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
示例：
思路：
从上一题的感觉可知，需要对子区间进行排序，那么按照右边界排序还是左边界排序呢？
其实都是可以的，它仅仅和之后的遍历数组的方向有关。
若按照右边界排序，就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的；
而若按照左边界排序，就要从右向左遍历，因为先遍历到的子区间的左边界数值越大越好（越靠右），这样就给前一个区间的空间就越大，所以可以从右向左遍历。
这里按右边界排序，且从左向右遍历；从左向右记录非交叉区间的个数，然后用区间总数减去非交叉区间个数就是需要移除的区间个数。 故解题顺序如下：
1、按照子区间右边界进行升序排列；
2、从左到右遍历，当当前子区间与上一个子区间有重叠时，将当前子区间的右边界设置为上一个重叠子区间的右边界（每次取非交叉区间时，取右边界最小的作为分割点，这样留给下一个区间的空间就是最大）；
3、如果当前子区间和上一个子区间无重叠时，非交叉区间个数加一；
4、区间总个数减去非交叉区间个数等于需要移除的区间个数。
class Solution {
static bool cmp(vector<int>& a, vector<int>& b){return a[1] < b[1];
}
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if(intervals.size()==0) return 0;sort(intervals.begin(), intervals.end(), cmp);int temp = 1; // 记录非交叉区间个数；for(int i=1; i<intervals.size(); i++){if(intervals[i][0] < intervals[i-1][1]){intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);}else {temp++;}}return intervals.size()-temp;}
};
14 划分字母区间(763)
题目：
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
思路：
在遍历的过程中找到每一个字母的边界，如果找到遍历过得所有字母的最远边界，说明这个边界就是分割点：
1、第一遍遍历，将每个字符出现的最大索引记录；
2、第二遍遍历，不断更新遍历到的字符的最大索引记录，当当前的最大索引记录和当前下标相同时，则找到了分割点。
class Solution {
public:vector<int> partitionLabels(string S) {int hash[27] = {0};for(int i=0; i<S.size(); i++){hash[S[i] - 'a'] = i;}vector<int> res;int left = 0;int right = 0;for(int i=0; i<S.size(); i++){right = max(hash[S[i] - 'a'], right);if(right == i){res.push_back(right - left + 1);left = right + 1;}} return res;}
};
15 合并区间(56)
题目：
给出一个区间的集合，请合并所有重叠的区间。
示例：
思路：
1、首先将子区间按左边界排序，然后从左向右遍历，如果intervals[i][0] <= intervals[i-1][1]，则说明两个子区间有重叠，进行合并；
2、for循环中加入while并进行判断可以一直循环直到遇到第一个不重叠的子区间，进而将该积攒的子区间保存，即可。
3、要注意最后一个子区间如果没有被连接起来的情况！
class Solution {
static bool cmp(vector<int>& a, vector<int>& b){return a[0] < b[0];
}
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);vector<vector<int>> res;bool flag = false;for(int i=1; i<intervals.size(); i++){int left = intervals[i-1][0];int right = intervals[i-1][1];while(i < intervals.size() && intervals[i][0] <= right){right = max(right, intervals[i][1]);if(i == intervals.size()-1) flag = true;i++;}res.push_back({left, right});}if(flag == false) res.push_back({intervals[intervals.size()-1][0], intervals[intervals.size()-1][1]});return res;}
};
16 单调递增的数字(738)
题目：
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例：
思路：
题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。
例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]-1，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
全局最优：得到小于等于N的最大单调递增的整数。
但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。遍历顺序需要从后向前遍历，如果从前向后遍历，会改变以遍历过的结果。在从后向前遍历的过程中，遍历到的最后一位strNum[i - 1] > strNum[i]的情况时，记录此时的i值，即该i值之后的值（包括下标i）都设置为9，以保证为最大的单调递增整数。
C++中整数转字符串的函数：to_string(int)；
C++中字符串转整数的函数：stoi(string);
class Solution {
publicint monotoneIncreasingDigits(int N) {string strNum = to_string(N);int flag = strNum.size();for(int i=strNum.size()-1; i>0; i--){if(strNum[i]<strNum[i-1]){strNum[i-1]--;flag = i;}}for(int i=flag; i<strNum.size(); i++){strNum[i] = '9';}return stoi(strNum);}
};
17 单调递增的数字(714)
题目：
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
思路：
如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。
此时无非就是要找到两个点，买入日期和卖出日期。
买入日期：其实很好想，遇到更低点就记录一下。
卖出日期：这个就不好算了，随着时间的推移，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（再过一天就要降了， 所以在降之前卖掉它）。
所以在做收获利润操作的时候其实有三种情况：
情况一：收获利润的这一天并不是收获利润区间里的最后一天，所以后面要继续收获利润；
情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了；
情况三：不作操作，保持原有状态（不买不卖）
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int res = 0;int minPrice = prices[0];for(int i=1; i<prices.size(); i++){// 情况二：记录最小价格，相当于买入if(prices[i]<minPrice) minPrice = prices[i];// 情况三：不操作，（因为此时买则不便宜，卖则亏本）if(prices[i]>=minPrice && prices[i]<=minPrice + fee)continue;// 情况一：可能有多次计算利润，最后一次计算利润才是真正的卖出if(prices[i] > minPrice + fee){res += prices[i] - minPrice - fee;// 连续多次获利时，第二次获利时候的最低价就是前一天最高价减去手续费；// 因为相当于第一天的利润已经加到res中了。 minPrice = prices[i] - fee; }}return res;}
};
欢迎关注【OAOA】
更多推荐
【数据结构】Leetcode——贪心算法 经典题
发布评论