算法 贪心4 || 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球

860.柠檬水找零

很简单的一题，完全是常识题

class Solution {
public:bool lemonadeChange(vector<int>& bills) {unordered_map<int,int> map;for(int i = 0; i < bills.size(); ++i){map[bills[i]]++;if(bills[i] != 5){if(map[5] == 0) return false;if(bills[i] == 10) map[5]--;if(bills[i] == 20){if(map[10] != 0) {map[10]--;map[5]--;}else{if(map[5]>=3) map[5] -= 3;else return false;}}}}return true;}
};

406.根据身高重建队列

思路ok，但是使用vector会非常耗时。C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。

所以使用vector（动态数组）来insert，是费时的，插入再拷贝的话，单纯一个插入的操作就是O(n²)了，甚至可能拷贝好几次，就不止O(n^2)了。
原vector中的size和capicity相同都是3，初始化为1 2 3，此时要push_back一个元素4。那么底层其实就要申请一个大小为6的普通数组，并且把原元素拷贝过去，释放原数组内存，注意图中底层数组的内存起始地址已经变了。同时也注意此时capicity和size的变化

而在贪心算法：根据身高重建队列
(opens new window)中，我们使用vector来做insert的操作，此时大家可会发现，虽然表面上复杂度是O(n²)，但是其底层都不知道额外做了多少次全量拷贝了，所以算上vector的底层拷贝，整体时间复杂度可以认为是O(n^2 + t × n)级别的，t是底层拷贝的次数。

class Solution {
public:static bool cmp(vector<int> v1,vector<int> v2){if(v1[0] == v2[0]){return v1[1] < v2[1];}return v1[0] > v2[0];}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){res.insert(res.begin() + people[i][1],people[i]);}return res;}};

使用链表：

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());}
};

452. 用最少数量的箭引爆气球

之前写过，记得本题贪心思路，一遍过

class Solution {
public:static bool cmp(const vector<int>& v1,const vector<int>& v2){return v1[1] < v2[1];}int findMinArrowShots(vector<vector<int>>& points) {int count = 1;sort(points.begin(),points.end(),cmp);int temp = points[0][1];for(int i = 1; i < points.size(); i++){if(points[i][0] <= temp) continue;else{count++;temp = points[i][1];} }return count;}
};

smoking info