摘要
- 尝试分解出一些简单的子问题，模拟其求解过程，有助于找到合适的贪心策略。
LeetCode860 柠檬水找零
- 这道题确实是用常识就能想出的贪心策略：
5美元面值更小，在有限范围内能组合出的面值更多，5美元的比10美元更容易找零。所以应该尽可能多地保留5美元，能用10美元找零就用10美元找零。
题解代码如下，用数组实现了一个简易的哈希表来模拟找零（其实只用三个int就可以实现...）
class Solution {
public:
int hash(int i) {
if (i < 0 || i > 20) return 0;
return i % 5 ? 0 : i / 5;
}
bool lemonadeChange(vector<int>& bills) {
vector<int> change(hash(20) + 1);
for (int i = 0; i < bills.size(); i++) {
int bill = bills[i];
change[hash(bill)]++;
if (bill == 10) {
// 10美元只能用5美元找零
if (change[hash(5)] > 0) change[hash(5)]--;
else return false;
}
if (bill == 20) {
// 20美元优先用10美元找零
if (change[hash(10)] > 0) {
change[hash(10)]--;
if (change[hash(5)] > 0) change[hash(5)]--;
else return false;
}// 没有10美元再用3张5美元找零
else if (change[hash(5)] >= 3) change[hash(5)] -= 3;
else return false;
}
}
return true;
}
};
LeetCode406 根据身高重建队列
-
这道题目需要考虑两个维度：一是身高
，二是前面要排
个身高大于或等于
- 尝试将全局最优分解为局部最优，先确定身高，再根据
k值排，模拟一下排队的过程 - 先取身高最高的一组人，假设最高身高为
H，可能的排列是
[ [H,0], [H,1], [H,2], …]- 然后，尝试把身高为
H-1的一个人排入队列中，根据其值不同，可能有如下情况
[ [H-1,0], [H,0], [H,1], …][ [H,0], [H-1, 1], [H,1], …]- 如果前面已经插入了一个
[H-1,0]，再插入一个[H-1,1]应该是这样的
[ [H-1,0], [H-1,1], [H,0], [H,1], …] - 尝试将全局最优分解为局部最优，先确定身高，再根据
从以上模拟过程可以看出，当一组人的身高值都相同时，这组人各自的
k值就是他们在队伍中的位置。而再插入一个人，且其身高值不大于队伍中所有人时，等待插入队列的人的k值也是他在队伍中的位置。对于每一步而言，排好的队伍都符合题目的要求，只是还没有把所有人排完，这是一种局部最优。所以可以尝试如下的贪心策略：将所有人按身高从大到小排序，每次取未排列身高值最高的人，根据其
k值排入已经排好的队伍中，在这一步中，他对应的下标就是k（从0开始）。原本排在k及k之后的人向后移一位，由于当前要插入队列的人的身高不大于已经排好的人的身高，不会影响到k及k之后的人的排序。
题解代码如下
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
if (a[0] != b[0]) return a[0] > b[0];
else return a[1] < b[1];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), cmp);
list<vector<int>> lq;
for (int i = 0; i < people.size(); i++) {
int k = people[i][1];
lq.insert(next(lq.begin(), k), people[i]);
}
vector<vector<int>> res(lq.begin(), lq.end());
return res;
}
};
- STL中的 list 底层是链表实现，所以插入操作的效率较高，顺便复习一下链表的
insert操作
lq.insert(next(lq.begin(), k), people[i]);
不使用STL的next函数，以上代码相当于
auto iter = lq.begin();
while (k--) iter++;// iter++ 相当于 iter = iter->next;
lq.insert(iter, people[i]);
LeetCode452 用最少数量的箭引爆气球
- 初见题目的想法，按气球的左边界（即
）从小到大排序，取两个相邻的气球
、
，首先根据排序规则
- 如果
，此时只需要
1根箭就可以引爆这两个气球，箭所在的范围应该是，这可以等效成一个新的气球，让下一个气球继续和这个等效出来的气球比较左边界和右边界。
- 如果
，说明气球 A 和气球 B 在垂直于 x 轴的平面上的投影没有重叠的区域，此时需要
2根箭。新使用的那根箭可以继续尝试第一步。
- 如果
- 贪心策略就是，按气球的左边界（即
[INT_MIN, INT_MAX]，记为- 从左到右遍历，当前气球为
i，更新射击范围的区间：
- 如果
或
，说明气球
i不在当前这根箭的设计范围内，要用多一根箭。令，作为下一根箭的初始设计范围区间。
- 如果气球
i和
有交集，则求出这个交集，用来更新当前这根箭的射击范围。
- 从左到右遍历，当前气球为
题解代码如下
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
if (a[0] != b[0]) return a[0] < b[0];
else return a[1] < b[1];
}
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), cmp);
vector<int> cur {INT_MIN, INT_MAX};
int arrow = 1;
for (int i = 0; i < points.size(); i++) {
if (points[i][1] < cur[0] || cur[1] < points[i][0]) {
arrow++;
cur = points[i];
}
else {
cur[0] = max(points[i][0], cur[0]);
cur[1] = min(points[i][1], cur[1]);
}
}
return arrow;
}
};
实际上，由于左边界是非降序的，上述代码可以简化
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
if (a[0] != b[0]) return a[0] < b[0];
else return a[1] < b[1];
}
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), cmp);
vector<int> cur {INT_MIN, INT_MAX};
int arrow = 1;
for (int i = 0; i < points.size(); i++) {
if (/*points[i][1] < cur[0] || */cur[1] < points[i][0]) {
arrow++;
cur = points[i];
}
else {
/*cur[0] = max(points[i][0], cur[0]);*/
cur[1] = min(points[i][1], cur[1]);
}
}
return arrow;
}
};
