加油站
想法：暴力遍历？
好吧第一遍写的时候读错题意了，以为是比较gas[i]与cost[i+1]的值，shit。
int sum1=0,sum2=0;
for(int g:gas)
sum1+=g;
for(int c:cost)
sum2+=c;
if(sum1<sum2)
return -1;
//如果gas没cost多
int youliang=0;
int n=gas.size();
for(int i=0;i<n;i++){
int count=0;
youliang=0;//每一次要记得重置
for(int j=i;count<n;count++){
if(j==n)
j=0;//用来解决循环
youliang+=gas[j];
if(youliang>=cost[j]){
youliang-=cost[j];
j++;
}
else
break;
if(count==n)
return i;
}
return -1;
但这样碰到大数据时会超时。
如果从i开始到j处不满足，那从i+1处必然时不满足的，因为i处是在积累油量，这个想法就和之前求最大连续子数组和一样，直接果断舍弃，让i=j，然后下一次i++，就从下一处开始
分发糖果
好吧，这题我确实没啥思路。。。
这是力扣上的官解给出的：
我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理。
左规则：当 ratings[i−1]<ratings[i] 时，i 号学生的糖果数量将比 i−1 号孩子的糖果数量多。
右规则：当 ratings[i]>ratings[i+1] 时，i 号学生的糖果数量将比 i+1 号孩子的糖果数量多。
代码倒是不难写，主要这思路好难想
vector<int> candy(ratings.size());
candy[0]=1;
for(int i=1;i<ratings.size();i++){
if(ratings[i]>ratings[i-1]){
candy[i]=candy[i-1]+1;
}
else
candy[i]=1;
}
for(int i=ratings.size()-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){
candy[i]=max(candy[i],candy[i+1]+1);
}
}
int sum=0;
for(int cd:candy){
sum+=cd;
}
return sum;
}
vector的初始化
如果一开始写的是vector candy;没给大小，那就不能用candy[0]来赋值，只能push_back来加元素。
或者写成vector candy（ratings.size()）;
柠檬水找零
这道还挺简单，我是用map来记录面额，收下一张就++；
unordered_map<int,int> money;
for(int i=0;i<bills.size();i++){
money[bills[i]]++;
if(bills[i]==10){
if(money[5]!=0){
money[5]--;
}
else
return false;
}
else if(bills[i]==20){
if(money[10]>=1&&money[5]>=1){
money[5]--;
money[10]--;
}
else if(money[10]==0&&money[5]>=3){
money[5]-=3;
}
else
return false;
}
}
return true;
}
406.根据身高重建队列
先找到最矮的一个人，然后他的second就是他重建后的位置，因为其他人都比他高。
好吧看来理解的还是不够深刻，面对两个维度的问题，一定要先考虑一个在考虑另一个，如果两个维度一起考虑一定会顾此失彼。
这题的思路是先按身高排序，而且要是从大往小排，这样就只用再根据有k个比他高的人在他前面考虑了。
要自己手写排序方式
static bool cmp(vector<int> a,vector<int>b){
if(a[0]==b[0]){
return a[1]<b[1];
]
return a[0>b[0];
}
sort 排序 return a < b 就是 从小到大； return a > b 就是 从大到小
而
堆 排序 return a < b 就是大顶堆 ； return a > b 就是小顶堆
sort(people.begin(),people.end(),cmp);
vector<vector<int>> queue;
for(int i=0;i<people.size();i++){
int position=people[i][1];
queue.insert(queue.begin()+position,people[i]);
}