柠檬水找零
leetcode：860. 柠檬水找零
贪心法
思路
遍历一遍数组，只关注面值5、10的钞票的数量
每轮判断：如果是5，five++；如果是10，判断还有没有5，有的话five--；如果是20，检查有没有一张10、一张5，ten--，five--。或者三张5，five-=3。
贪心：先消耗面值10的钞票，因为它更万能。
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(1)。
注意点
略
代码实现
class Solution {
public:
// 遍历bills，存储5、10的数量。
// （10、20的时候检查钞票够不够）
// 如果是5，存入、继续；如果是10，存入，5--，继续
// 如果是20，10--，5--或者5-=3，继续
bool lemonadeChange(vector<int>& bills) {
int fiveNums = 0;
int tenNums = 0;
for(int i = 0;i < bills.size();i++){
if(bills[i] == 5) fiveNums++;
else if(bills[i] == 10){
if(fiveNums > 0){
fiveNums--;
tenNums++;
}else return false;
}else if(bills[i] == 20){
if(fiveNums > 0 && tenNums> 0){
fiveNums--;
tenNums--;
}else if(fiveNums >= 3){
fiveNums -=3;
}else return false;
}
}
return true;
}
};
根据身高重建队列
leetcode：406. 根据身高重建队列
贪心法
思路
复杂度分析
时间复杂度：
- 对people数组进行排序的时间复杂度为O(n*log(n))，其中n为people的长度。
- 在for循环中，每个人需要插入到list中，而插入操作的时间复杂度为O(n)（n为list的长度）。
- 最后将list中的结果转换为vector需要O(n)的时间。
因此，总体来说，这段代码的时间复杂度为O(n^2 * log(n))，其中n为people的长度。
空间复杂度：取决于list空间占用，O(N)。
注意点
-
（链表版）迭代器声明方式：
container_type::iterator iterator_name; -
迭代器不能直接进行加减运算，可以通过advance函数进行移动。（或者手写一个while循环让其自增自减）
-
vector扩容的实质：在size超过capacity时，复制原值创建一个两倍capacity的新数组，摧毁旧数组。因此vector的insert操作不仅是遍历一遍的O(N)，还有重建数组的O(N)。
代码实现
vector版：
class Solution {
public:
// 先按身高倒序排序，然后根据第k插入相应位置
static bool cmp(const vector<int>& a,const vector<int>& b){
// 根据h从大到小排序
if(a[0] == b[0]) return a[1] < b[1]; // 如果相等则按k升序
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++) {
que.insert(que.begin() + people[i][1],people[i]);
}
return que;
}
};
链表版：
class Solution {
public:
// 先按身高倒序排序，然后根据第k插入相应位置
static bool cmp(const vector<int>& a,const vector<int>& b){
// 根据h从大到小排序
if(a[0] == b[0]) return a[1] < b[1]; // 如果相等则按k升序
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(),people.end(),cmp);
list<vector<int>> que;
for (int i = 0;i < people.size();i++) {
list<vector<int>>::iterator it = que.begin();
advance(it,people[i][1]);
que.insert(it,people[i]);
}
vector<vector<int>> result;
for(vector<int> vec : que) result.push_back(vec);
return result;
}
};
用最少数量的箭引爆气球
leetcode：452. 用最少数量的箭引爆气球
贪心法
思路
-
按左边界从小到大排序，如果左边界相等，则按右边界从小到大排序。
（
这步很关键，有了右边界和下一元素左、右边界比较已经不重要了） -
遍历每个元素，arrow++，然后进行当前元素的边界的内检测：
以当前元素为对比标准，取i的右边界为right
若right >= i+1的左边界且right >= i+1右边界，那么一起射爆它，i++。
若right < i+1右边界，那么right更改为i+1右边界，再i++（此时对比的标准已经转变为这个i+1元素）。
直至不再满足这个条件。
（关键在于，当前右边界与下一元素左、右边界都比较，如果right>左边界，可以一箭多雕；如果right>右边界，那么从right更新为下一元素的右边界，以下一元素为基准进行循环比较）
贪心：局部最优——每箭尽可能多射爆气球；总体最优——用尽可能少的箭射爆所有气球。
复杂度分析
时间复杂度：O(NlogN)。虽有两层循环，但只每个元素大致只遍历一次。复杂度主要在排序。
空间复杂度：O(1)。
注意点
略
代码实现
class Solution {
public:
// 按左边界从小到大排序，如果左边界相等则按右边界从小到大排序。
// 遍历每个元素，arrow++，然后进行当前元素的边界的内检测
// 内检测：取i的右边界为right若right >= i+1的左边界且right >= i+1右边界，那么一起射爆它，i++，
// 若right < i+1右边界，那么right更改为i+1右边界
// 直至不再满足这个条件
static bool cmp(vector<int>& a,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);
int arrow = 0;
for(int i = 0;i < points.size();i++){
arrow++;
int right = points[i][1];
while(i < points.size() - 1 && right >= points[i + 1][0]){
if(points[i + 1][1] < right) right = points[i + 1][1];
i++;
}
}
return arrow;
}
};