134.加油站
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
思路
这道题我觉得关键还是搞清楚遍历几次和环路的问题。
假设从第一个加油站出发，一共有n个加油站，当汽车从x加油站想开到x+1加油站时发现没油了，或者说剩下的油不支持开到下一个加油站了，那么，从1号加油站到x加油站之间所有的加油站开始开出都无法到达x+1加油站，我们直接从x+1加油站开始判断，这样，我们只要遍历一次所有的加油站，就可以找到唯一解或者无解。
那么比如从中间一个加油站开出，怎样用代码表示开到了前面几号加油站呢，可以记录当前开出的距离，并加上出发点号码，再除以总数量取余，就是当前开至地点。
在遍历的过程中，记录总加油量和消耗量，若消耗量大于加油量说明无法行驶一周。
代码
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n=gas.length;
int i=0;
while(i<n){
int sumGas=0,sumCost=0;
int cnt=0;
while(cnt<n){
int j=(i+cnt)%n;
sumGas+=gas[j];
sumCost+=cost[j];
if(sumGas<sumCost){
break;
}
cnt++;
}
if(cnt==n){
return i;
}
}
return -1;
}
}135.分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
思路
方法一 两次遍历
这道题中，“相邻孩子中，评分高的孩子必须获得更多的糖果”可以拆分为两个规则分别处理：
左规则：当i-1评分小于i时，i糖果数量将比i-1多。
右规则：当i+1评分小于i时，i糖果数量比i+1多。
这样，我们遍历数组两次，处理出一个学生分别满足左规则或右规则时最少分得的糖果数量，每个人最终分到的糖果数就是两个数量的较大值。
方法二
这样的一个ratings数组必然由若干个递增序列和递减序列组成，在遍历过程中，如果当前同学评分比上一个同学高，说明在递增序列中，给该同学分配pre+1个糖果，pre是前一个同学分得的糖果数量。否则的话就在递减序列中，直接给当前同学分配一个糖果，并把该同学所在递减序列中的同学都再多分配一个糖果。这样，我们只要记录递减序列的长度和最近的递增序列长度和钱一个同学分得的糖果数量pre即可。
代码
方法一
class Solution {
public int candy(int[] ratings) {
int n=ratings.length;
int[] candys=new int[n];
for(int i=0;i<n;i++){
if(i>0&&ratings[i]>ratings[i-1]){
candys[i]=candys[i-1]+1;
}else{
candys[i]=1;
}
}
int right=0,ret=0;
for(int i=n-1;i>=0;i--){
if(i<n-1&&ratings[i+1]<ratings[i]){
right++;
}else{
right=1;
}
ret+=Math.max(candys[i],right);
}
return ret;
}
}方法二
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int ret = 1;
int inc = 1, dec = 0, pre = 1;
for (int i = 1; i < n; i++) {
if (ratings[i] >= ratings[i - 1]) {
dec = 0;
pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
ret += pre;
inc = pre;
} else {
dec++;
if (dec == inc) {
dec++;
}
ret += dec;
pre = 1;
}
}
return ret;
}
}
