LeetCode860. 柠檬水找零
题目链接：860. 柠檬水找零
独上高楼，望尽天涯路
本来以为只想到了最笨的方法，即讨论所有情况。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int change_5 = 0;
int change_10 = 0;
for (int i = 0; i < bills.size(); i++) {
if (bills[i] == 5) {
change_5++;
}
else if (bills[i] == 10) {
if (change_5 > 0) change_5--;
else return false;
change_10++;
}
else if (bills[i] == 20) {
if (change_5 > 0 && change_10 > 0) {
change_5--;
change_10--;
}
else if (change_5 > 2) {
change_5 -= 3;
}
else return false;
}
}
return true;
}
};
慕然回首，灯火阑珊处
结果没想到题解也是这么做的。
LeetCode406. 根据身高重建队列
题目链接：406. 根据身高重建队列
独上高楼，望尽天涯
这次终于思路对了！！！并且代码ac！！！
class Solution {
public:
static bool cmp(vector<int> a, vector<int> b) {
return (a[0] > b[0]) || (a[0] == b[0] && a[1] < b[1]);
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), cmp);
for (int i = 0; i < people.size(); i++) {
if (people[i][1] < i) {
vector<int> temp = people[i];
people.erase(people.begin() + i);
people.insert(people.begin() + temp[1], temp);
}
}
return people;
}
};
慕然回首，灯火阑珊
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性
使用vector比较费时，使用list（底层是链表实现）新创建一个数组作为输出会省时不少。
class Solution {
public:
// 身高从大到小排（身高相同k小的站前面）
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);
list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多
for (int i = 0; i < people.size(); i++) {
int position = people[i][1]; // 插入到下标为position的位置
std::list<vector<int>>::iterator it = que.begin();
while (position--) { // 寻找在插入位置
it++;
}
que.insert(it, people[i]);
}
return vector<vector<int>>(que.begin(), que.end());
}
};
LeetCode452. 用最少数量的箭引爆气球
题目链接：452. 用最少数量的箭引爆气球
独上高楼，望尽天涯
没有很好的思路。
慕然回首，灯火阑珊
这类问题被称作重叠区间问题。
为了让气球尽可能的重叠，需要对数组进行排序。
从前向后遍历遇到重叠的气球了怎么办？
如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
if (points.size() == 0) return 0;
sort(points.begin(), points.end(), cmp);
int result = 1;
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], points[i - 1][1]); // 更新重叠气球的最小右边界
}
}
return result;
}
};