力扣（134.860.406.452）补9.26
力扣200题了，留个小小的纪念。
134.加油站
这题我用2层循环可以通过35/39个用例，但是卡在一个死变态的，数据贼多，超过时间限制了。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
for(int i=0;i<gas.size();i++){
if(gas[i]>=cost[i]){
int sum=gas[i]-cost[i];
int j=0;
for(j=(i+1)%gas.size();j!=i;j=(j+1)%gas.size()){
sum=sum+gas[j]-cost[j];
if(sum<0||(sum==0&&(j+1)%gas.size()!=i)) break;
}
if(j==i){
return i;
}
}
}
return -1;
}
};
不过我现在也发现了，贪心不是一个意义非常明确的算法，感觉就是没有一个固定的套路，更多的是数学上的思考吧。所以除了暴力我完全不会这题。题解也没看明白。。算了，我真的头疼了。。这题就当没做过有缘再见吧。做题别那么轴。
860.柠檬水找零
没想出来，这题一开始没想清楚怎么做，怎么也想不到贪心算法上，其实贪心，就是数学思维题，想通了就简单，想不通就一直卡着。其实就是记录自己手里的5元，10元，钞票的个数。
因为10元钞票只能用于顾客给20元的时候，所以优先找别人10元钞票，再找5元的，只要手里钞票不出现负数就可以了。
这个就是考思维的地方。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
vector<int> a(2,0);
if(bills[0]!=5){
return false;
}
a[0]=1;
for(int i=1;i<bills.size();i++){
if(bills[i]==5){
a[0]++;
}
if(bills[i]==10){
a[1]++;
a[0]--;
}
if(bills[i]==20){
if(a[1]>=1)
{a[1]--;
a[0]-=1;}
else{
a[0]-=3;
}
}
if(a[0]<0||a[1]<0)
return false;
}
return true;
}
};
406.根据身高重建队列
c++的东西早就忘了差不多了，要不是4月8号有个蓝桥杯，都没什么能督促我刷算法了。
begin：返回指向容器第一个元素的迭代器
end：返回指向容器最后一个元素下一个位置的迭代器
str1=str1（被插入字符串）.insert(插入位置,str2（被插入字符串），n ，m)
在下标处插入东西，原来的东西整体后移。
ps：n，m分别是插入字符串要截取的（真正要插入的部分）即在str2.n位置数m个，不写这个的话就是将str2整个全部插入。
这里自己模拟一遍会发现思路比较清晰了。先对数组进行排序在插入很重要。
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(),people.end(),[](const vector<int>&u,const vector<int>&v){
return u[0]>v[0]||(u[0]==v[0]&&u[1]<v[1]);
});
vector<vector<int>> ans;
for(int i=0;i<people.size();i++){
if(people[i][1]<i)
ans.insert(ans.begin()+people[i][1],people[i]);
else ans.push_back(people[i]);
}
return ans;
}
};
452.用最少数量的箭引爆气球
这题的贪心我实在不明白，凭啥局部最优能得到整体最优，凭啥，凭啥。。。没有严格的数学证明，我实在不能接受啊啊啊啊啊啊啊。