加油站
想法:暴力遍历?
好吧第一遍写的时候读错题意了,以为是比较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++;}elsebreak;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;}elsecandy[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]--;}elsereturn 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]);}