新的一天开始啦
860.柠檬水找零
第一题分三类讨论，一点点做就可以。最开始想用map，后来发现用数组就可以。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
if(bills[0] != 5)return false;
int own[3] = {0};
for(int i = 0;i<bills.size();i++){
if(bills[i] == 5){
own[0]++;
}
if(bills[i] == 10){
own[1]++;
own[0]--;
}
if(bills[i] == 20){
own[2]++;
if(own[1] > 0){
own[1]--;
own[0]--;
}else{
own[0]-= 3;
}
}
if(own[0] < 0 || own[1] < 0 || own[2] < 0)return false;
}
return true;
}
};406.根据身高重建队列
vector用法先总结一下：
删除：v.erase(v.begin()+2); //删除第三个位置的元素
插入：v.insert(v.begin()+n,1);//插入任意位置,n是想要插入的位置
交换：iter_swap(persons.begin()+4,persons.begin()+5);//交换 5 6 之后
这题的思路是先排序，排序后逐个添加到新的vector里即可，插入顺序其实可以依照people[i][j]
class Solution {
public:
// static bool cmp(const vector<int>& a, const vector<int>& b){ 我感觉我写那个应该可以
static bool cmp(vector<int> a,vector<int> b){
if(a[0] == b[0])return a[1] < b[1];
else 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 k = 0;k < people.size();k++){
que.insert(que.begin() + people[k][1],people[k]);
}
return que;
}
};有一个节省空间的方式，使用链表list来做，似乎用list不能直接在insert里面加
// 版本二
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(vector<int>pointa,vector<int>pointb){
if(pointa[0] == pointb[0]) return pointa[1] < pointb[1];
return(pointa[0] < pointb[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-1][1] < points[i][0]){
result++;
}
else{
points[i][1] = min(points[i-1][1],points[i][1]);//找最小右边界的方式
}
}
return result;
}
};
