135. 分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
1、贪心策略
本题目需要使用两次贪心策略,首先给每个孩子发一个糖果，然后：
- 第一次是从左边往右边贪心：只要右边评分比左边大，右边的孩子就多一个糖果
-
第二次是右边往左边贪心：只要左边比右边大，左边的孩子得到
max(当前左边孩子糖果数， 右边孩子糖果数 + 1)
，这是为了保证第一次贪心结果有效，如左边孩子糖果为5，右边为1；那么第二次贪心后左边孩子守里面的糖果仍然是5，这是因为5 > 1 + 1
2、代码实现
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyVec(ratings.size(), 1); //每个孩子发一个
int candySum = 0;
/-----第一次贪心，从左往右-----/
for(int i = 1; i < ratings.size(); i++){
if(ratings[i] > ratings[i -1]) candyVec[i] = candyVec[i - 1] + 1;
}
/-----第二次贪心，从右往左----/
for(int i = ratings.size() - 1; i > 0; i--){
if(ratings[i - 1] > ratings[i]){
candyVec[i - 1] = max(candyVec[i - 1], candyVec[i] + 1);
}
}
/-----统计糖果总数量-----/
for(int i = 0; i < candyVec.size(); i++){
candySum += candyVec[i];
}
return candySum;
}
};
860. 柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
1、贪心策略
情况一：账单是5，直接收下。
情况二：账单是10，消耗一个5，增加一个10
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
2、算法实现
这里其实用不到map，直接设置三个int变量来表示5,10和20的数量就可以
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0, twenty = 0;
for (int bill : bills) {
// 情况一
if (bill == 5) five++;
// 情况二
if (bill == 10) {
if (five <= 0) return false;
ten++;
five--;
}
// 情况三
if (bill == 20) {
// 优先消耗10美元，因为5美元的找零用处更大，能多留着就多留着
if (five > 0 && ten > 0) {
five--;
ten--;
twenty++; // 其实这行代码可以删了，因为记录20已经没有意义了，不会用20来找零
} else if (five >= 3) {
five -= 3;
twenty++; // 同理，这行代码也可以删了
} else return false;
}
}
return true;
}
};
406. 根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
1、贪心策略
这种具有双重维度的题，一般都是两次贪心才能解决，每次解决一个维度，如果两个维度一起考虑，会顾此失彼，最后解不出来
第一次贪心：按照身高从大到小排列，身高相同的话则k小的站前面
第二次贪心：那么只需要按照k为下标重新插入队列；按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列
2、代码实现
// 版本一
class Solution {
public:
static bool cmp(const vector<int> a, const vector<int> b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort (people.begin(), people.end(), cmp);
vector<vector<int>> que;
for (int i = 0; i < people.size(); i++) {
int position = people[i][1];
que.insert(que.begin() + position, people[i]);
}
return que;
}
};
452. 用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
1、贪心策略
为了使用尽量少的键，我们需要尽量用一支箭射更多的重叠气球：
- 按照气球起始位置排序
-
如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭；每次遍历一个气球，需要更新当前重叠气球的最小右边界，此时箭就应从最小右边界射出。如果箭大于最小右边界，当前重叠的气球中一定有射不到的
第一组重叠气球，一定是需要一个箭，气球3，的左边界大于了 第一组重叠气球的最小右边界，所以再需要一支箭来射气球3了
2、代码实现
class Solution {
private:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.size() == 0) return 0;
sort(points.begin(), points.end(), cmp);
int result = 1; // points 不为空至少需要一支箭
for (int i = 1; i < points.size(); i++) {
if (points[i][0] > points[i - 1][1]) { // 气球i和气球i-1不挨着
result++; // 需要一支箭
}
else { // 气球i和气球i-1挨着
points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
}
}
return result;
}
};
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
1、贪心策略
- 首先按照区间起始位置从小到大排序
- 从头遍历区间，如果两个区间重叠，则删除区间结束位置大的，这样才能尽可能给后面留出空间，从而少删除区间
2、代码实现
class Solution {
private:
static bool cmp(vector<int>& a, vector<int>& b){
return a[0] < b[0];
}
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size() == 0) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int removeNum = 0;
int rightRange = intervals[0][1];
for(int i = 1; i < intervals.size(); i++){
/----如果重复了，删除计数+1，删除右边界大的区间，更新右边界为小右边界-----/
if(intervals[i][0] < rightRange){
removeNum++;
rightRange = min(rightRange, intervals[i][1]);
} else {
/----正常更新右边界为下一个区间-----/
rightRange = intervals[i][1];
}
}
return removeNum;
}
};
763. 划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
1、贪心策略
- 统计每一个字符最后出现的位置
-
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
2、解题代码
class Solution {
public:
vector<int> partitionLabels(string s) {
/-----统计字符最远出现位置-----/
int hash[26] = {0};
for(int i = 0; i < s.size(); i++){
hash[s[i] - 'a'] = i;
}
/-----寻找分割点-----/
vector<int> res;
int rightRange = 0;
int leftRange = 0;
for(int i = 0; i < s.size(); i++){
//更新最远右边界
if(hash[s[i] - 'a'] > rightRange) rightRange = hash[s[i] - 'a'];
//找到分割点
if(i == rightRange) {
res.push_back(rightRange - leftRange + 1);
leftRange = i + 1;
}
}
return res;
}
};
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
1、贪心策略
将区间按照左边界从小到大排序，然后从第一个区间开始对重叠区间开始合并，每次合并都取最大的右边界，这样就可以合并更多的区间了。
2、解题代码
class Solution {
private:
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;
int rightRange = intervals[0][1];
int leftRange = intervals[0][0];
/----从第一个区间开始合并重叠区间-----/
for(int i = 1; i < intervals.size(); i++){
if(intervals[i][0] > rightRange){
res.push_back(vector<int> {leftRange, rightRange});
leftRange = intervals[i][0];
rightRange = intervals[i][1];
} else {
rightRange = max(rightRange, intervals[i][1]);
}
}
/------由于最后一个区间不会遇到条件将其添加到res中，因此要手动添加----/
res.push_back(vector<int> {leftRange, rightRange});
return res;
}
};
738. 单调递增的数字
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
1、贪心策略
从后向前遍历，遇到最后一个strNum[i – 1] > strNum[i]的时候，让strNum[i – 1]–，然后strNum[i]及其之后均改为9，可以保证这两位变成最大单调递增整数。
注意一定要从后向前遍历
，因为当index = i处更改为9后，会导致index = i-1处-1，这可能会导致index = i-1的元素小于index = i- 2；如果从前向后遍历，会导致后面的遍历更改影响前面的遍历结果
2、解题代码
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string strNum = to_string(n);
/-----找到改成9的位置----/
int flagIndex =strNum.size();
for(int i = strNum.size() - 1; i > 0; i--){
if(strNum[i - 1] > strNum[i]){
flagIndex = i;
strNum[i - 1]--;
}
}
/----改成9-----/
for(int i = flagIndex; i < strNum.size(); i++){
strNum[i] = '9';
}
return stoi(strNum);
}
};
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
1、贪心策略
- 首先计算每天的净收益
-
然后根据净收益有如下三种策略：
情况一：今天价格 > 持仓价格 + 手续费，收获这一天的利润。相当于今天卖出（实际上并没有真的卖出），把今天的钱赚了，然后在根据今天的价格买入，今天卖出时候交的手续费可以抵扣今天买入价格。这样相当于只有今天卖出不买入的时候才真的扣手续费。
情况二：今天价格 < 持仓价格，相当于前一天是收获利润区间里的最后一天（相当于真正的卖出了），直接更改买入价格为今天的价格，相当于前一天真的卖出了。
情况三：持仓价格 < 今天价格 < 今天价格 + 手续费， 则今天不作操作，保持原有状态
2、解题代码
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int result = 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) {
result += prices[i] - minPrice - fee;
minPrice = prices[i] - fee; // 情况一，这一步很关键
}
}
return result;
}
};
968. 监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
1、贪心策略
- 叶子节点不放摄像头
-
定义如下三种状态：
0：该节点无覆盖
1：本节点有摄像头
2：本节点有覆盖
将空节点定义为有覆盖，从而避免在叶子节点上放摄像头。根据叶子节点的状态确定根节点状态：
1）左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖
2）左右节点至少有一个无覆盖的情况，此时根节点应该放摄像头
3）左右节点至少有一个有摄像头，此时根节点为被覆盖
以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，因此递归后需要再判断一下头节点的状态，考虑是否再头结点加一个摄像头
2、代码实现
class Solution {
private:
int cameraNum = 0;
int travelBack(TreeNode* root){
if(root == nullptr) return 2; //空节点状态
int left = travelBack(root->left);
int right = travelBack(root->right);
if(left == 2 && right == 2) return 0; //情况1）
if(left == 0 || right == 0){ //情况2）
cameraNum++;
return 1;
}
if(left == 1 || right == 1) return 2; //情况3）
return -1; //必须有返回值，实际上用不到
}
public:
int minCameraCover(TreeNode* root) {
if(travelBack(root) == 0) cameraNum++;
return cameraNum;
}
};
版权声明：本文为qq_42138662原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。