算法训练营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!
?
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!