算法训练营Day30

2024-01-01 22:51:37

#Java #回溯

开源学习资料

Feeling and experiences:

加油站:力扣题目链接

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

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

给定两个整数数组 gascost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -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!
?

文章来源:https://blog.csdn.net/momolinshaomo/article/details/135327927
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。