LeetCode刷题day50

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

//暴力法  TCL
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
  for(int i = 0; i < gas.size(); i++) { //从加油站中选择一个 出发点
    int rest = gas[i]-cost[i];//当前汽车的汽油量
    int index = (i+1) % gas.size();//下一个加油站的下标
    while(rest >= 0 && index!=i) { //开始绕路一周
      rest += gas[index]-cost[index];
      index =  (index+1) % gas.size();
    }
    if(rest>=0 && index==i) {//如果汽车剩余量>=0,并且回到了出发点,则可以驾驶一周!
      return i;
    }
  }
  return -1;//遍历所有的加油站,如果没有找到可满足的则返回-1
}

//贪心一:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
  int min = INT_MAX;//绕圈过程中汽车的最小汽油量
  int rest = 0;//当前汽车的汽油量
  //从0开始走一圈,看看是否可能跑 一圈
  for(int i = 0; i < gas.size(); i++) {
    rest  += gas[i] - cost[i]  ;
    if(rest < min) {
      min = rest;
    }
  }
  if(rest <0) { //如果gas的综合小于cost总和,则无论从哪里出发,都无法跑一圈
    return -1;
  }
  if(min >= 0) { //如果res最小值 >=0,则0汽油站便是出发点
    return 0;
  }
  //从后往前,看看何时能使min>=0
  for(int i = gas.size()-1; i >=0; i--) {//?为啥要从后往前呢? 因为从前往后res遇到了负值.说明可能的情况是 
  //res先>0 ==> res=0 ==>res <0 ==>res>0,说明后面的gas相对于cost会大的多,这样才可能抵消前面的负值. 所以应该从后往前寻找加油站直至能把min抵消. 
    int curSum = gas[i]-cost[i];//curSum当前加油和小号的差值.
    min += curSum;
    if(min >= 0) { //什么时候抵消了,就从哪里开始.
      return i;
    }
  }
  return -1;//如果最后还没有找到,则返回-1
}

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

//从前往后 右边孩子大于左边孩子 ,右边孩子糖果数增加
for(int i = 1;i < ratings.size();i++){
    if(ratings[i] > ratings[i-1]){
        candy[i] = candy[i-1]+1; //右边糖果+1 
    }
} 

#include<bits/stdc++.h>
using namespace std;
int candy(vector<int>& ratings) {
  int res = 0;
  vector<int> candy(ratings.size(),1);//初始化糖果数组 每个孩子至少为1个 
  //从前往后 右边孩子大于左边孩子 ,右边孩子糖果数增加
  for(int i = 1;i < ratings.size();i++){
    if(ratings[i] > ratings[i-1]){
      candy[i] = candy[i-1]+1; //右边糖果+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); // 选candy[i] candy[i+1]+1  ,如果candy[i]<=candy[i+1]则是candy[i+1]+1. 如果candy[i] > candy[i+1],则为candy[i] 
    }
  }
  for(int i = 0;i < candy.size();i++){
    res += candy[i];
  } 
  return res;
}

输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

#include<bits/stdc++.h>
using namespace std;
bool lemonadeChange(vector<int>& bills) {
  int five = 0,ten = 0,twenty = 0;
  for(int bill : bills){
    //当支付5美元
    if(bill==5){
      five++;
    }
    //当支付10美元
    if(bill==10){
      ten++;
      if(five > 0){
        five--;
      }else{//如果five不够的话. 
        return false;
      }
    }
    //当支付20美元
    if(bill==20){
      twenty++;
      if(five > 0&&ten > 0){//优先选择1张five 和1张ten 
        five--;
        ten--;
      }else if(five >= 3){//次之选择3张five 
        five-=3;
      }else{//否则 无法找零,结束 
        return false;
      }
    } 
  }
  return true; 
}

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

#include<bits/stdc++.h>
using namespace std;
static bool cmp(vector<int>& a,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) ;//进行排序
  //按照k从前往后整理元素   由于升高是从高到底所以插入元素对前面元素的k无影响
  vector<vector<int>> res;
  //要是第一个元素的k>0呢,还有元素呢  ??? 中间的插入会报错嘛. 
  for(int i = 0;i < people.size();i++){
    int position = people[i][1];
    res.insert(res.begin()+position,people[i]);
  } 
  return res; 
}