【数据结构】Leetcode——贪心算法
不打扰 | 是我的温柔。
Content
-
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道题可以分类为：
1 分发饼干(455)
题目：
示例：
思路：
本题的局部最优就是大饼干喂给胃口大的，全局最优就是喂饱尽可能多的小孩。可以尝试使用贪心策略，先将饼干数组和小孩数组排序，然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。
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)
题目：
思路：
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)
题目：
示例：
思路：
for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历！！
如果总油量减去总消耗大于等于零，则一定可以跑完一圈，说明剩油量一定是大于等于零；
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。
// 暴力解法，学习用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)
题目：
示例：
思路：
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，直接收下；
情况二：账单是10，消耗一个5，增加一个10；
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5、
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
vector<int> moneyNums(3, 0); // 0->5, 1->10, 2->20
for(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)
题目：
思路：
「如果两个维度一起考虑一定会顾此失彼」。
1、首先按身高从大到小排（身高相同的话则k小的站前面），让高个子在前面。此时确定了一个维度——身高，前面的节点一定都比本节点高；
2、按照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)
题目：
示例：
思路：
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)
题目：
思路：
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)
题目：
示例：
思路：
class Solution {
public
int 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)
题目：
思路：
卖出日期：这个就不好算了，随着时间的推移，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（再过一天就要降了， 所以在降之前卖掉它）。
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;
}
};
🔗往期分享