算法训练营day28--134. 加油站 +135. 分发糖果+860.柠檬水找零+406.根据身高重建队列

一、 134. 加油站

题目链接：https://leetcode.cn/problems/gas-station/
文章讲解：https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html
视频讲解：https://www.bilibili.com/video/BV1jA411r7WX

1.1 初见思路

得模拟分析出，先计算每个加油站的汽油数量和消耗汽油数量的差值，再进行后续的分析

1.2 具体实现

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum = 0;int totalSum = 0;int index = 0;for (int i = 0; i < gas.length; i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {// 当前累加rest[i]和 curSum一旦小于0index = (i + 1) % gas.length ; // 起始位置更新为i+1curSum = 0; // curSum从0开始}}if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了return index;}
}

1.3 重难点

这个题目不太好模拟

二、 135. 分发糖果

题目链接：https://leetcode.cn/problems/candy/
文章讲解：https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
视频讲解：https://www.bilibili.com/video/BV1ev4y1r7wN

2.1 初见思路

首先找到评分最低的孩子，从他们开始分一个糖果
再逐个向两边扩散

2.2 具体实现

class Solution {
/**分两个阶段1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 12、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大*/public int candy(int[] ratings) {int length = ratings.length;int[] arr = new int[length];int result=0;Arrays.fill(arr,1);for(int j=0;j<length-1;j++){if(ratings[j+1]>ratings[j]){arr[j+1]=arr[j]+1;}}for(int j=length-2;j>=0;j--){if(ratings[j]>ratings[j+1]){arr[j]=Math.max(arr[j+1]+1,arr[j]);}}for(int i=0;i<length;i++){result+=arr[i];}//int result = Arryas.sum(arr);return result;}
}

2.3 重难点

不能在考虑局部的时候想两边兼顾，这样会顾此失彼；
采用了两次贪心的策略，一次是从左到右遍历，只比较右边孩子评分比左边大的情况、一次是从右到左遍历，只比较左边孩子评分比右边大的情况

三、 860.柠檬水找零

题目链接：https://leetcode.cn/problems/lemonade-change/
文章讲解：https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html
视频讲解：https://www.bilibili.com/video/BV12x4y1j7DD

3.1 初见思路

目的是找零，设置三个数来统计三种面额的钱的剩余数量
找零的优先顺序是先找面额大的，也就是10美元，没有10美元再找5美元的

3.2 具体实现

class Solution {public boolean lemonadeChange(int[] bills) {int fiveNum=0;int tenNum=0;for(int i=0;i<bills.length;i++){if(bills[i]==5){fiveNum++;}if(bills[i]==10){if(fiveNum==0){return false;}fiveNum--;tenNum++;}if(bills[i]==20){if(tenNum>0 && fiveNum>0){tenNum--;fiveNum--;}else if(tenNum==0 && fiveNum>=3){fiveNum-=3;}else{return false;}}}return true;}
}

3.3 重难点

四、 406.根据身高重建队列

题目链接：https://leetcode.cn/problems/queue-reconstruction-by-height/
文章讲解：https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html
视频讲解：https://www.bilibili.com/video/BV1EA411675Y

4.1 初见思路

需要考虑两个因素，身高和k，所以需要控制变量，先按照身高排序

4.2 具体实现

class Solution {public int[][] reconstructQueue(int[][] people) {// 身高从大到小排（身高相同k小的站前面）Arrays.sort(people, (a, b) -> {if (a[0] == b[0]) return a[1] - b[1];   // a - b 是升序排列，故在a[0] == b[0]的狀況下，會根据k值升序排列return b[0] - a[0];   //b - a 是降序排列，在a[0] != b[0]，的状况会根据h值降序排列});LinkedList<int[]> que = new LinkedList<>();for (int[] p : people) {//按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点que.add(p[1],p);   //Linkedlist.add(index, value)，会将value插入到指定index裡。}return que.toArray(new int[people.length][]);}
}

4.3 重难点

为什么按照k为下标重新插入队列就可以了？
因为按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
使用LinkedList的效率更高，因为这里频繁使用插入操作，LinkedList的底层是链表，所以插入操作的性能远高于ArrayList