代码随想录day26 | leetcode 134.加油站 135.分发糖果 860.柠檬水找零 406.根据身高重建队列

加油站

解法1：暴力法。

找到第一个能出发的点，开始往后试。
不需两个for，同步遍历，比较消耗油量与获得油量。
遍历每一个加油站为起点的情况，模拟一圈。
如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。
暴力的方法思路比较简单，但代码写起来也不是很容易，关键是要模拟跑一圈的过程。

for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！
容易超时。

解法2：查看每个站点的剩余油量。

例子：gas:2 5 2 3 5
cost:1 2 8 2 4
1 3 -6 1 1

例子2: gas:5 8 2 3 5
cost:1 2 8 2 4
4 6 -6 1 1

题目中说明：如果存在解，则 保证 它是 唯一 的，例子2有多个解。

 public int canCompleteCircuit(int[] gas, int[] cost) {
        //  int[] num 可以不用创建新数组。
        int curSum = 0,tolSum = 0,start = 0;

        for (int i = 0; i < gas.length; i++) {
            curSum += gas[i] - cost[i];//
            tolSum += gas[i] - cost[i];//最终剩余油量。
            if (curSum < 0) {
                start = i + 1;
                curSum = 0;
            }
        }
        if (tolSum<0){
            return  -1;
        }
        return start;
    }

分发糖果

题目：n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

解法：现从左往右，在从右往左，选取最大的保留。

1. 先确定右边评分大于左边的情况（也就是从前向后遍历）

此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果

局部最优可以推出全局最优。

2. 左孩子大于右孩子的情况一定要从后向前遍历。

如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。

局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

 public int candy(int[] ratings) {
        int[] count = new int[ratings.length];//4 2 3 1 在3时再+1，不能用count++;
        Arrays.fill(count,1);
        int sum = 0;
        for (int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i-1]){
                count[i] = count[i-1] + 1;
            }
        }
        for (int i = ratings.length-2; i >= 0; i--) {
            if (ratings[i]>ratings[i+1]){
                count[i] = Math.max(count[i+1]+1,count[i]);
            }
        }
        for (int i = 0; i < ratings.length; i++) {
            sum += count[i];
        }
        return sum;
    }

柠檬水找零

题目：在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

解法：用到了hash表和贪心

情况一：账单是5，直接收下。

情况二：账单是10，消耗一个5，增加一个10

情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5。贪心：优先对10与5的组合找零。

public boolean lemonadeChange(int[] bills) {

        int five = 0;
        int ten = 0;
        int twenty = 0;

        for (int i = 0; i < bills.length; i++) {
            if(bills[i] == 5){
                five++;
            }
            if (bills[i] == 10){
                if (five == 0){
                    return false;
                }
                ten++;
                five--;
            }
            if (bills[i] == 20 ){
                if (ten >0&&five>0){
                    ten--;
                    five--;
                    twenty++;
                }
                else if (five >= 3){
                    five = five - 3;
                    twenty++;
                }
                else {
                    return false;
                }
            }
        }
        return true;
    }

根据身高重建队列

题目：假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
解析：不能改变数据，根据它前面有多少人进行排队，还要看是否比它自身高。
先按k排序，在按h排序。
先按h排序，在按k排序。

解法：最后排序方式是在队列的插入进行的。

详细解释：

在Java中，Arrays.sort 方法可以接受一个数组和一个比较器（Comparator），用于自定义排序规则。当使用 lambda 表达式来定义比较器时，(a, b) 是 lambda 表达式的参数，它们代表数组中的两个元素，用于比较它们的顺序。
a 和 b 是长度为 2 的数组，分别代表 people 数组中的两个元素，每个元素包含两个整数值：第一个表示身高（hi），第二个表示前面有多少个身高大于或等于他的人（ki）。

people 是要排序的二维整数数组，其中每个元素都是一个整数数组，表示一个人的身高和前面高于或等于其身高的人数。a 和 b 是这个二维数组中的两个元素，它们的形式是 int[2]，其中：

• a[0] 表示第一个人（或元素a）的身高。
• a[1] 表示第一个人（或元素a）前面高于或等于其身高的人数。

同样地：

• b[0] 表示第二个人（或元素b）的身高。
• b[1] 表示第二个人（或元素b）前面高于或等于其身高的人数。

1. 初始化队列：
   • LinkedList<int[]> que = new LinkedList<>(); 创建了一个空的LinkedList，用来存放最终的队列。
2. 遍历排序后的数组：
   • for (int[] p : people) 是一个增强型for循环，它遍历排序后的people数组。
3. 插入元素：
   • que.add(p[1], p); 是插入过程的核心。这里，p是一个长度为2的数组，其中p[0]是身高h，p[1]是前面大于等于h的人数k。
   • p[1]作为add方法的第一个参数，表示p应该插入到队列中的位置索引。由于LinkedList允许在任意位置插入元素，add(index, element)方法会将element插入到index指定的位置，并将原来的元素以及之后的元素向后移动。
   • 为什么这样插入是正确的？这是因为people数组已经根据身高降序排列，并且对于相同身高的人来说，k值小的在前。所以，对于队列中的每个位置，k值表示了当前人前面应该有多少个比他高或者和他一样高的人。由于队列是从前往后构建的，每次插入时，队列中已经存在的元素都是比当前人高的，或者身高相同但k值更小的，所以直接在k指定的位置插入当前人是正确的。
     假设我们有以下排序后的people数组：

复制

[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

插入过程如下：

• 对于[7,0]，p[1]是0，所以我们将其插入到队列的第0个位置：[[7,0]]
• 对于[7,1]，p[1]是1，所以我们将其插入到队列的第1个位置：[[7,0], [7,1]]
• 对于[6,1]，p[1]是1，但由于队列中已经有2个元素，我们需要将其插入到第1个位置，并且将后面的元素向后移动：[[7,0], [6,1], [7,1]]
• 对于[5,0]，p[1]是0，所以我们将其插入到队列的第0个位置，并将所有其他元素向后移动：[[5,0], [7,0], [6,1], [7,1]]
• 对于[5,2]，p[1]是2，所以我们将其插入到队列的第2个位置：[[5,0], [7,0], [5,2], [6,1], [7,1]]
• 对于[4,4]，p[1]是4，所以我们将其插入到队列的第4个位置：[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

int[] p 是一个一维数组，它代表了二维数组 people 中的每一个子数组。在这个循环中，p 依次被赋值为 people 中的每一个子数组。
每次迭代，p 就指向 people 中的一个新的子数组，你可以通过 p[0] 和 p[1] 来访问这个子数组的第一个和第二个元素，这些元素分别代表了人的身高和前面高于或等于其身高的人数。
所以，这个增强型for循环实际上是在遍历二维数组的每一行，而不是单个元素。每次循环，p 都是一个指向 people 中一个子数组的引用，而不是一个单独的整数。因此，你可以在 LinkedList 的 add 方法中使用 p[1] 作为索引，将整个子数组 p 插入到 LinkedList 的正确位置。

public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(a,b)->{
            if (a[0] == b[0]){
                return a[1] - b[1];
            }
            return b[0] - a[0];
        });


        LinkedList<int[]> que = new LinkedList<>();

        for (int[] p:people) {
            que.add(p[1],p);
        }

        return que.toArray(new int[people.length][]);
    }