算法训练营Day30

#Java #回溯

开源学习资料

Feeling and experiences：

加油站：力扣题目链接

在一条环路上有 n?个加油站，其中第 i?个加油站有汽油?gas[i]?升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1?个加油站需要消耗汽油?cost[i]?升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

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;
    }
}

?for?循环遍历每个加油站。

对于每个站点：
更新?curSum?和?totalSum?以反映从当前加油站到下一个加油站的油量变化（考虑加油和消耗）。
如果?curSum?变成负数，表示无法从当前起始站点到达下一个加油站。因此，需要更新起始站点为下一个加油站，并重置?curSum?为?0。
?在循环结束后，检查?totalSum。如果?totalSum?小于?0，表示整个路线的油量总和不足以支持整个旅程，因此返回?-1。
如果?totalSum?大于等于?0，则存在至少一个有效的起始加油站。此时，index?存储的就是这样一个有效起始站点的索引。

分发糖果:力扣题目链接

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

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

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

class Solution {
    public int candy(int[] ratings) {
        int[] tmp = new int[ratings.length];
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1]){
                tmp[i]=tmp[i-1]+1;
            }
        }
        for(int i=ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                tmp[i]=Math.max(tmp[i],tmp[i+1]+1);
            }
        }
        int sum = ratings.length;
        for(int i=0;i<tmp.length;i++){
            sum+=tmp[i];
        }
        return sum;
    }
}

?1. 初始化：
? 创建一个与?ratings?数组相同长度的?tmp?数组，用于存储每个孩子应得的额外糖果数。
2. 从左至右遍历：
? 第一个?for?循环从左至右遍历?ratings?数组。对于每个孩子：
? 如果一个孩子的评分高于他左边邻近的孩子，那么他应得的糖果数至少比左边的孩子多一个。因此，更新?tmp[i]?为?tmp[i-1]?+?1。
3. 从右至左遍历：
? 第二个?for?循环从右至左遍历?ratings?数组。这次检查的是每个孩子相对于右边邻近孩子的评分。
? 如果一个孩子的评分高于他右边邻近的孩子，那么他应得的糖果数至少比右边的孩子多一个。因此，更新?tmp[i]?为?Math.max(tmp[i],?tmp[i+1]?+?1)，确保不会减少已经由左至右遍历时分配的糖果数。
4. 计算总糖果数：
? 初始化?sum?为?ratings.length，因为每个孩子至少得到一颗糖果。
? 通过第三个?for?循环遍历?tmp?数组，将所有额外的糖果数加到?sum?中。
5. 返回结果：
? 返回?sum，它代表了满足条件的最小糖果总数。

Finghting！
?