手表网站免费设计,丹阳信息网,在线做文档的网站,php网站建设模板目录
#x1f388;LeetCode1005.K次取反后最大化的数组和
#x1f388;LeetCode134.加油站
#x1f388;LeetCode135.分发糖果 #x1f388;LeetCode1005.K次取反后最大化的数组和
链接#xff1a;1005.K次取反后最大化的数组和 给你一个整数数组 nums 和一个整数 k…目录
LeetCode1005.K次取反后最大化的数组和
LeetCode134.加油站
LeetCode135.分发糖果 LeetCode1005.K次取反后最大化的数组和
链接1005.K次取反后最大化的数组和 给你一个整数数组 nums 和一个整数 k 按以下方法修改该数组 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后返回数组 可能的最大和 。 方法一 直接把最小的一直取反但是时间复杂度为O(n^2logn) public int largestSumAfterKNegations(int[] nums, int k) {for(int i0;ik;i){Arrays.sort(nums);nums[0]-nums[0]; }int sum0;for(int i0;inums.length;i){sumnums[i];}return sum;}
LeetCode134.加油站
链接134.加油站 在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。 给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。 方法一
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int minInteger.MAX_VALUE;int curSum0;for(int i0;igas.length;i){int tempgas[i]-cost[i]; //每天的剩余油量curSumtemp;if(curSummin){mincurSum;}}if(curSum0){return -1; //油量总和小于要用的油}if(min0){return 0; //从0出发油没有断过}// 不是从0出发的情况for(int igas.length-1;i0;i--){int tempgas[i]-cost[i];min temp;if(min0){return i;}}return -1;}
}
方法二
public int canCompleteCircuit(int[] gas, int[] cost) {int curSum0;int totalSum0;int result0;for(int i0;igas.length;i){curSumgas[i]-cost[i];totalSumgas[i]-cost[i];if(curSum0){resulti1;curSum0;}}if(totalSum0){return -1;}return result;}
LeetCode135.分发糖果
链接135.分发糖果 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求给这些孩子分发糖果 每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。 public int candy(int[] ratings) {int[] candysnew int[ratings.length];for(int i0;icandys.length;i){candys[i]1;}// 从前向后for(int i1;iratings.length;i){if(ratings[i]ratings[i-1]){candys[i]candys[i-1]1;}}// 从后向前for(int iratings.length-2;i0;i--){if(ratings[i]ratings[i1]){candys[i]Math.max(candys[i],candys[i1]1);}}int result0;for(int i0;icandys.length;i){resultcandys[i];}return result;}
