算法训练营第三十四天"/>
代码随想录算法训练营第三十四天
1005. K 次取反后最大化的数组和
给你一个整数数组
nums
和一个整数k
,按以下方法修改该数组:
- 选择某个下标
i
并将nums[i]
替换为nums[i]
。重复这个过程恰好
k
次。可以多次选择同一个下标i
。以这种方式修改数组后,返回数组 可能的最大和 。
输入:nums = [4,2,3], k = 1
输出:5
解释:选择下标 1 ,nums 变为 [4,-2,3] 。
解题思路:
- 将数组按照绝对值得从大到小排序
- 遍历数组,如果nums[i]<0并且k>0时让nums[i]=-nums[i];并k—;
- 遍历结束如果k依然大于0,则反转数组中最小的元素为负数,让k值用完
- 求和
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {nums= IntStream.of(nums).boxed().sorted((o1,o2)-> Math.abs(o2)-Math.abs(o1)).mapToInt(Integer::intValue).toArray();for(int i=0;i<nums.length;i++){if(nums[i]<0&&k>0){nums[i]=-nums[i];k--;}}if(k%2==1) nums[nums.length-1]=-nums[nums.length-1];return Arrays.stream(nums).sum();}
}
134. 加油站
在一条环路上有
n
个加油站,其中第i
个加油站有汽油gas[i]
**升。你有一辆油箱容量无限的的汽车,从第 **
i
**个加油站开往第 **i+1
**个加油站需要消耗汽油cost[i]
**升。你从其中的一个加油站出发,开始时油箱为空。给定两个整数数组
gas
和cost
,如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回-1
。如果存在解,则 保证 它是 唯一 的。
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。
解题思路:
- 总油量减去总消耗大于0则一定可以跑完一圈,反之小于0则返回-1
- 每个加油站的余量rest[i]=gas[i]-cost[i]
- i从0开始累加rest[i],累加和为curtotal,当curtotal<0时说明[0,i]区间不能作为起始位置,所以将i+1作为起始位置,curtotal从0开始计算。
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curtotal=0;int sumtotal=0;int index=0;for(int i=0;i<gas.length;i++){curtotal+=gas[i]-cost[i];sumtotal+=gas[i]-cost[i];if(curtotal<0){index=i+1;curtotal=0;}}if(sumtotal<0) return -1;return index;}
}
135. 分发糖果
n
个孩子站成一排。给你一个整数数组ratings
表示每个孩子的评分。你需要按照以下要求,给这些孩子分发糖果:
- 每个孩子至少分配到
1
个糖果。- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
输入:ratings = [1,0,2]
输出:5
解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
本题采用了两次贪心的策略:
- 从左到右遍历,只比较右边孩子评分比左边大的情况。
- 从右到左遍历,只比较左边孩子评分比右边大的情况。
从局部最优推出了全局最优,即:相邻的孩子中,评分高的孩子获得更多的糖果。
解题思路:
- 定义一个空数组用来存储每个人分的糖果数量
- 首先从左到右遍历,
ratings[i]>ratings[i-1]
令count[i]=count[i-1]+1
- 从右向左遍历,当
ratings[i]>ratings[i+1]
时count[i]=Math.max(count[i],count[i+1]+1);
- 最后求和
class Solution {public int candy(int[] ratings) {int len=ratings.length;int[] count=new int[len];count[0]=1;//从前向后for(int i=1;i<len;i++){if(ratings[i]>ratings[i-1]){count[i]=count[i-1]+1;}else{count[i]=1;}}//从后向前for(int i=len-2;i>=0;i--){if(ratings[i]>ratings[i+1]){count[i]=Math.max(count[i],count[i+1]+1);}}int reslut=0;for(int i:count){reslut+=i;}return reslut;}
}
更多推荐
代码随想录算法训练营第三十四天
发布评论