Day29–贪心–134. 加油站，135. 分发糖果，860. 柠檬水找零，406. 根据身高重建队列
134. 加油站
方法：循环数组，模拟
思路：
循环数组模拟闭环的效果。
最重要的剪枝：当油不够的时候，直接从断油的这个点i开始循环。
自己写的有点累赘。可以看下一个优化版本。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
// 这个循环，把每次出发的情况都考虑到
for (int k = 0; k < n; k++) {
// 这个循环，指的是从这个点出发转一圈行不行。是起到转圈作用。
boolean flag = true;
int oil = 0;
int meet = 0;
int i = k;
for (; i < n * 2 && meet != 2; i++) {
// 用meet参数来判断是否闭环（走回原点）
if (meet == k) {
meet++;
}
oil += gas[i % n] - cost[i % n];
if (oil < 0) {
flag = false;
break;
}
}
// 只有两种情况会退出上面的循环，一是meet==2，也就是闭环了。另一种是断油了。
if (flag) {
return k;
}
// 最重要的是这一步：当油不够的时候，直接从断油的这个点i开始循环
// 不做这一步剪枝的话会超时，时间是O(n^2)，数据量10^5*10^5
if (!flag) {
k = i;
}
}
return -1;
}
}
方法：贪心
思路：
利用curRest和totalRest，一次循环搞定。关键要理解，为什么当curRest<0之后，下一个起点是i+1，这和数学/逻辑证明有关。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int startIndex = 0;
// 当前剩余油量
int curRest = 0;
// 总剩余油量
int totalRest = 0;
for (int i = 0; i < gas.length; i++) {
// 加油减油
curRest += gas[i] - cost[i];
totalRest += gas[i] - cost[i];
// 当前累加rest[i]和 curRest一旦小于0，起始位置更新为i+1，并且curRest从0开始
if (curRest < 0) {
startIndex = i + 1;
curRest = 0;
}
}
// 总油量剩余小于0的话，说明怎么走都不可能跑一圈了
if (totalRest < 0) {
return -1;
}
return startIndex;
}
}
135. 分发糖果
方法：贪心
思路：
- 从左向右遍历。只要i个孩子比i-1那个孩子厉害，就比他多一颗糖。
- 从右向左遍历。如果i个孩子，大于i+1个孩子了。要判断，是要比i+1多一颗糖呢？还是领原来的打败左边孩子的糖呢？取二者之间较大值
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
if (n == 0) {
return 0;
}
int[] candys = new int[ratings.length];
// 每个人至少得到1颗糖
Arrays.fill(candys, 1);
// 从左向右遍历。只要i个孩子比i-1那个孩子厉害，就比他多一颗糖
for (int i = 1; i < n; i++) {
if (ratings[i - 1] < ratings[i]) {
candys[i] = candys[i - 1] + 1;
}
}
// 从右向左遍历。
// 如果i个孩子，大于i+1个孩子了。要判断，是要比i+1多一颗糖呢？还是领原来的打败左边孩子的糖呢？
// 取二者之间较大值
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candys[i] = Math.max(candys[i + 1] + 1, candys[i]);
}
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += candys[i];
}
return sum;
}
}
860. 柠檬水找零
方法：贪心
思路：
当收20时，先找10块和5块，再考虑三张5块。（搞笑的事，20块没用，不用记账）
// 当收20时，先找10块和5块，再考虑三张5块
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
for (int i = 0; i < bills.length; i++) {
switch (bills[i]) {
case 5: {
five++;
break;
}
case 10: {
// 找一张5块，收一张10块
if (five > 0) {
five--;
ten++;
} else {
return false;
}
break;
}
case 20: {
// 先找一张10和5，最大程度保留5，因为当付10块的时候也要找钱5块
if (ten > 0 && five > 0) {
ten--;
five--;
// 如果没有，就要消耗3张5块
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
}
return true;
}
}
406. 根据身高重建队列
方法：贪心
思路：
- 排序规则：
- 身高从大到小排列（降序）
- 若身高相同，则按照k值从小到大排列（升序）
- 遍历排序后的数组，按照k值插入到对应位置
记录：特别地，需要掌握Arrays.sort()的高级排序操作，和LinkedList的toArray()方法。
class Solution {
/**
* 根据身高和位置信息重建队列
*
* @param people 二维数组，每个元素包含两个值：[身高, 前面身高大于等于当前的人数]
* @return 重建后的队列数组
*/
public int[][] reconstructQueue(int[][] people) {
// 对数组进行排序
// 排序规则：
// 1. 身高从大到小排列（降序）
// 2. 若身高相同，则按照k值从小到大排列（升序）
Arrays.sort(people, (a, b) -> {
// 身高相同的情况，按k值升序排列
if (a[0] == b[0]) {
return a[1] - b[1];
}
// 身高不同的情况，按身高降序排列
return b[0] - a[0];
});
// 创建链表用于插入操作
LinkedList<int[]> que = new LinkedList<>();
// 遍历排序后的数组，按照k值插入到对应位置
for (int[] p : people) {
// LinkedList的add(index, element)方法：
// 将元素插入到指定索引位置，原索引及之后的元素后移
que.add(p[1], p);
}
// 将链表转换为数组并返回
return que.toArray(new int[people.length][]);
}
}