day 29 第八章 贪心算法part03

第一题：134.加油站

解题思路

本题要求在给定两个整数数组 gas（表示每个加油站的汽油量）和 cost（表示从一个加油站到下一个加油站的耗油量）的情况下，判断能否绕环路行驶一周，如果可以则返回出发时加油站的编号，否则返回 -1，解题思路基于贪心算法，以下是详细说明：

1. 整体思路：
   贪心算法在这里的体现是，我们尝试从每一个加油站出发去模拟绕环路行驶的过程，在这个过程中，一旦发现从某个加油站出发走到某个位置时油箱里的油不够继续往下走了（也就是累积剩余油量小于 0 了），那就没必要再从这个加油站以及之前的加油站继续尝试了，而是直接从下一个加油站重新开始尝试，通过这样不断尝试和排除不合适的出发点，最终找到能绕环路行驶一周的出发加油站编号，或者确定不存在这样的加油站（返回 -1）。

2. 变量初始化：

   • curSum：用于记录从当前尝试的起始加油站出发，走到当前位置时油箱内汽油的累积剩余量，初始值设为 0，因为刚开始出发时油箱是空的。
   • totalSum：用于记录整个环路一圈下来汽油的总剩余量（也就是把每个加油站的汽油量减去到下一个加油站的耗油量后全部累加起来），初始值也设为 0，同样基于还没开始模拟行驶的初始状态设定。
   • index：用于记录可能的起始加油站编号，初始设为 0，也就是先默认从第 0 个加油站开始尝试。

3. 遍历数组模拟行驶并更新状态：
   通过 for 循环从第 0 个加油站开始，依次模拟沿着环路行驶到每个加油站的情况（索引为 i，循环条件是 i < gas.length）。在循环中：

   • 计算当前位置的剩余油量并更新累积剩余量：
     每次计算当前加油站能获得的汽油量 gas[i] 减去开到下一个加油站需要消耗的汽油量 cost[i]（即 gas[i] - cost[i]），然后将这个差值累加到 curSum 中（通过 curSum += gas[i] - cost[i]），表示走到当前位置时油箱内汽油的累积剩余情况，同时也将这个差值累加到 totalSum 中（通过 totalSum += gas[i] - cost[i]），用于后续判断整个环路一圈下来总的汽油剩余情况。
   • 判断是否需要更换起始加油站：
     如果在模拟行驶过程中，发现 curSum 的值小于 0 了，这意味着从当前尝试的起始加油站出发，走到当前这个位置时油箱里的油已经不够继续往下走了，所以这个起始加油站肯定不行，那就需要更换起始加油站。将 index 更新为 (i + 1) % gas.length，这里取余操作是因为这是一个环路，当走到最后一个加油站后下一个要尝试的就是第 0 个加油站了，通过取余可以实现循环的索引效果。然后将 curSum 重置为 0，相当于从新的起始加油站重新开始计算剩余油量的累积情况，继续循环去模拟从新的起始加油站出发的行驶过程。

4. 判断是否能绕环路行驶并返回结果：
   当循环遍历完所有加油站后，先判断 totalSum 的值，如果 totalSum 小于 0，这说明整个环路一圈下来总的汽油剩余量是负数，也就是无论从哪个加油站出发，汽油都不够绕环路行驶一周的，此时直接返回 -1；而如果 totalSum 大于等于 0，那就说明存在能够绕环路行驶一周的情况，此时 index 中记录的就是最后一次确定的可以作为起始加油站的编号，直接返回 index 即可。

代码

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){
                index = (i + 1) % gas.length;
                curSum = 0;
            }
        }
        if(totalSum < 0){
            return -1;
        }
        return index;
    }
}

 第二题：135.分发糖果

解题思路

本题要求根据孩子们的评分来分发糖果，要满足每个孩子至少有 1 颗糖果且相邻评分更高的孩子获得更多糖果这两个条件，并求出最少需要准备的糖果数目，整体解题思路采用了两次遍历的方法，以下是详细说明：

1. 整体思路：
   为了得到最少的糖果数目，我们需要合理地根据相邻孩子的评分关系来分配糖果数量。首先从左到右遍历数组，按照相邻孩子中左边评分高的情况来初步确定糖果数量；然后再从右到左遍历数组，针对相邻孩子中右边评分高的情况对之前确定的糖果数量进行调整，这样综合两次遍历的结果就能保证满足题目条件且糖果数量是最少的，最后将所有孩子的糖果数累加起来得到最终答案。

2. 初始化糖果数组并进行第一次遍历（从左到右）：

   • 初始化糖果数组：
     创建一个和 ratings 数组长度相同的 int 数组 candyVec，用于记录每个孩子分配到的糖果数量。先将 candyVec[0] 初始化为 1，因为每个孩子至少要分配 1 颗糖果，所以第一个孩子先分配 1 颗糖果作为初始状态。
   • 从左到右遍历并分配糖果（考虑左边评分更高的情况）：
     通过 for 循环从第二个孩子开始遍历整个 ratings 数组（索引为 i，循环条件是 i < len）。在循环中进行判断：如果当前孩子的评分 ratings[i] 大于前一个孩子的评分 ratings[i - 1]，那么按照规则，当前孩子获得的糖果数应该比前一个孩子多 1，所以将 candyVec[i] 赋值为 candyVec[i - 1] + 1；而如果当前孩子的评分不大于前一个孩子的评分（也就是小于等于），那就给当前孩子分配 1 颗糖果（即 candyVec[i] = 1），因为只要满足每个孩子至少有 1 颗糖果这个基本条件就行。

3. 进行第二次遍历（从右到左）：
   通过 for 循环从倒数第二个孩子开始，反向遍历整个 ratings 数组（索引为 i，循环条件是 i >= 0）。这次遍历主要是考虑相邻孩子中右边评分更高的情况来调整糖果数量。如果发现当前孩子的评分 ratings[i] 大于后一个孩子的评分 ratings[i + 1]，此时为了满足相邻评分更高的孩子糖果更多的条件，当前孩子的糖果数应该取当前已有的糖果数 candyVec[i] 和后一个孩子糖果数加 1（即 candyVec[i + 1] + 1）中的最大值，通过 candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1) 来更新当前孩子的糖果数，这样能保证既满足条件又不会分配过多不必要的糖果。

4. 计算并返回最少糖果总数：
   初始化一个变量 ans 用于累加所有孩子的糖果数，通过 for 循环遍历 candyVec 数组（使用增强 for 循环 for(int num : candyVec)），将每个元素（也就是每个孩子的糖果数）累加到 ans 中，最后返回 ans 的值，这个值就是满足题目要求的最少糖果数目。

代码

class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candyVec = new int[len];
        candyVec[0] = 1;
        for(int i = 1;i < len;i++){
            if(ratings[i] > ratings[i - 1]){
                candyVec[i] = candyVec[i - 1] + 1;
            }else{
                candyVec[i] = 1;
            }
        }
        for(int i = len - 2;i >= 0;i--){
            if(ratings[i] > ratings[i + 1]){
                candyVec[i] = Math.max(candyVec[i],candyVec[i + 1] + 1);
            }
        }
        int ans = 0;
        for(int num : candyVec){
            ans += num;
        }
        return ans;
    }
}

第三题：860.柠檬水找零

解题思路

本题要求根据顾客付款的账单序列 bills，判断是否能够给每位顾客正确找零，整体解题思路基于模拟实际的交易找零过程，按照不同面额的钞票进行相应的数量统计和找零操作，以下是详细说明：

1. 整体思路：
   我们依次遍历顾客付款的账单数组 bills，针对每个顾客支付的不同面额钞票（5 美元、10 美元、20 美元），检查手头现有的零钱（通过记录不同面额钞票的数量来体现）是否足够进行找零，如果在遍历完整个数组后都能成功完成每一次找零操作，那就返回 true，表示可以给每位顾客正确找零；反之，如果在过程中出现无法完成找零的情况，就立即返回 false。

2. 变量初始化：
   定义三个变量 five、ten、twenty，分别用于记录手头拥有的 5 美元、10 美元、20 美元钞票的数量，初始值都设为 0，因为一开始手头没有任何零钱。

3. 遍历账单数组并处理找零情况：
   通过 for 循环从数组的第一个元素开始，依次遍历整个 bills 数组（索引为 i），在循环中根据顾客支付的不同面额钞票进行相应操作：

   • 顾客支付 5 美元情况：
     当 bills[i] == 5 时，说明顾客支付了 5 美元，此时直接将 five 的值加 1，表示手头的 5 美元钞票数量增加了 1 张，不需要进行找零操作，继续处理下一个顾客的账单。
   • 顾客支付 10 美元情况：
     当 bills[i] == 10 时，顾客支付了 10 美元，按照找零规则需要给顾客找零 5 美元。所以首先要检查手头是否有足够的 5 美元钞票（即判断 five 是否大于 0），如果 five == 0，说明没有 5 美元的零钱了，无法给这位顾客正确找零，直接返回 false；如果手头有 5 美元零钱，那么将 ten（10 美元钞票数量）加 1，表示收到了一张 10 美元钞票，同时将 five 减 1，表示用掉了一张 5 美元钞票去给顾客找零，然后继续处理下一个顾客的账单。
   • 顾客支付 20 美元情况：
     当 bills[i] == 20 时，顾客支付了 20 美元，找零方式有两种优先选择。优先尝试用一张 10 美元和一张 5 美元给顾客找零（这样能更灵活地利用手头的零钱），所以先判断手头是否有至少一张 10 美元（ten > 0）并且至少一张 5 美元（five > 0），如果满足这个条件，就将 ten 减 1（用掉一张 10 美元），five 减 1（用掉一张 5 美元），同时将 twenty（20 美元钞票数量）加 1，表示收到了一张 20 美元钞票；如果不满足上述条件（也就是没有 10 美元和 5 美元的组合来进行找零），那就尝试只用 5 美元来找零，判断手头是否有至少三张 5 美元（five >= 3），如果是，就将 five 减去 3，表示用三张 5 美元给顾客找零，同时将 twenty 加 1；如果既没有 10 美元和 5 美元的组合，也没有足够的三张 5 美元，那就说明无法给这位顾客正确找零，直接返回 false。

4. 最终结果返回：
   如果循环遍历完整个 bills 数组后，都没有出现无法找零的情况，那就说明可以给每位顾客正确找零，此时返回 true。

代码

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0,ten = 0,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 -= 3;
                    twenty++;
                }else{
                    return false;
                }
            }
        }
        return true;
    }
}

第四题：406.根据身高重建队列

解题思路

本题要求根据给定的表示人员身高和前面更高或相同身高人数的二维数组 people，重新构造出符合条件的队列，整体解题思路运用了贪心算法的思想，通过合理排序和插入操作来实现，以下是详细说明：

1. 整体策略：
   为了能准确地重建队列，我们先对人员信息按照一定规则进行排序，使得后续插入操作能够更方便地满足每个人前面有特定数量更高或相同身高人员的条件。然后按照排序后的顺序依次将人员插入到结果队列中合适的位置，最终得到重建后的队列。

2. 数组排序预处理：
   通过 Arrays.sort(people, (a, b) -> {...}) 对 people 数组进行自定义排序。排序规则如下：

   • 首先按照身高 h 值从大到小进行排序（通过 return b[0] - a[0]; 实现，因为 b - a 的差值比较方式在比较器中表示降序排列）。这样做的好处是，当我们从前往后处理人员插入时，先处理身高高的人，由于高个子的相对位置比较容易确定（前面高个子的人数相对固定，不受后面矮个子插入的影响），所以便于后续操作。
   • 当身高相同时，按照 k 值从小到大进行排序（通过 if (a[0] == b[0]) return a[1] - b[1]; 实现，a - b 的差值比较方式表示升序排列）。因为在身高相同的情况下，k 值小的人应该排在更前面，这样能保证在后续插入操作中符合每个人对应的 k 值条件。

3. 利用链表进行人员插入操作：
   创建一个 LinkedList<int[]> 类型的链表 que 用于构建最终的队列。接着遍历已经排好序的 people 数组，对于每一个人员信息数组 p（其中 p[0] 表示身高，p[1] 表示前面更高或相同身高的人数 k），使用 que.add(p[1], p); 方法将人员信息插入到链表 que 中。这里利用了 LinkedList 的 add(index, value) 方法的特性，它会将 value（也就是当前人员信息 p）插入到指定的 index（也就是 p[1] 所表示的位置）处。例如，如果 p[1] 的值为 2，就会将当前人员信息插入到链表中索引为 2 的位置，这样就保证了在这个位置之前恰好有 p[1] 个身高大于或等于当前人员身高的人，符合题目要求。

4. 返回最终队列结果：
   最后通过 que.toArray(new int[people.length][]); 将构建好的链表 que 转换为二维数组形式并返回，这个二维数组就是重新构造后的符合题目要求的队列。

代码

class Solution {
    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];//b - a是降序排列
        });
        LinkedList<int[]> que = new LinkedList<>();
        for(int[] p : people){
            que.add(p[1],p);
        }
        return que.toArray(new int[people.length][]);
    }
}