关于网站建设的合同,杭州网站制作蒙特,宜兴公司做网站,提升学历的十大好处是什么Day291005.K次取反后最大化的数组和力扣题目链接给定一个整数数组 A#xff0c;我们只能用以下方法修改该数组#xff1a;我们选择某个索引 i 并将 A[i] 替换为 -A[i]#xff0c;然后总共重复这个过程 K 次。#xff08;我们可以多次选择同一个索引 i。#xff09;以这种方…Day291005.K次取反后最大化的数组和力扣题目链接给定一个整数数组 A我们只能用以下方法修改该数组我们选择某个索引 i 并将 A[i] 替换为 -A[i]然后总共重复这个过程 K 次。我们可以多次选择同一个索引 i。以这种方式修改数组后返回数组可能的最大和。输入A [2,-3,-1,5,-4], K 2输出13解释选择索引 (1, 4) 然后 A 变为 [2,3,-1,5,4]。思路我们可以先把数组按照绝对值从大到小进行排序[5,-4,-3,2,-1]对这个数组从前往后进行遍历遇到负数就变为相反数并把k--循环结束条件是遍历到数组末尾或k0如果k0跳出循环那就可以直接返回改变后数组的和如果数组遍历结束跳出循环这时k还大于零如果k是偶数那其实不用管了取反两次还是自己如果k是奇数就把数组最后一位的元素取反因为它的绝对值最小取反后让sum变小的最少代码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 k 0; i) {//循环结束条件是遍历结束或k为0了if (nums[i] 0) {nums[i] -nums[i];//把绝对值最大的负数取反k--;//处理k}}if (k % 2 1) nums[nums.length - 1] -nums[nums.length - 1];//k为偶数不用管为奇数就把绝对值最小的正数取反return Arrays.stream(nums).sum();}
}134. 加油站力扣题目链接在一条环路上有 N 个加油站其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。如果你可以绕环路行驶一周则返回出发时加油站的编号否则返回 -1。思路暴力遍历计算gas和cost数组的差数组对这个arr进行遍历如果arr[i]小于0那直接continue这个加油站的油跑不到下一个加油站能跑到上一个加油站么不需要考虑因为可以看上一个加油站能不能跑到这个加油站如果大于0那就从这里开始循环跑一圈取余操作如果跑的过程中haveGas小于零那从这个加油站开始就跑不了一圈结束内层循环如果发现能跑一圈那直接返回i最后外层循环结束每个加油站都看完了还没有找到能跑一圈的返回-1比较巧妙的解法还是先给出rest数组对rest数组进行遍历计算数组前i个元素的和并计算部分和的最小值如果遍历结束数组所有元素和加起来小于0说明肯定跑不到返回-1如果部分和的最小值都大于零那随便跑返回0剩下的情况就是要研究从哪个加油站开始跑的我们这时倒着开始遍历找恰好能填平最小部分和的元素位置贪心算法局部最优当前累加rest[i]的和curSum一旦小于0起始位置至少要是i1因为从i之前开始一定不行。全局最优找到可以跑一圈的起始位置。首先需要知道rest数组累加如果不小于0那就一定能跑玩对rest数组进行遍历计算部分和如果发现计算到i部分和为负数那其实从0到i这一段不可能能作为起点那就从i1开始继续计算部分和部分和从0开始重新计算如果遍历结束累加小于0跑不完返回-1否则一定能跑完其实就是部分和大于零的初始值用index进行记录代码class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int[] arr new int[cost.length];for (int i 0; i arr.length; i) {arr[i] gas[i] - cost[i];//计算arr数组}for (int i 0; i cost.length; i){if (arr[i] 0) continue;//小于0跑不到下一个加油站直接continueint index i;//记录iint haveGas arr[i];//记录这个加油站的油量while (haveGas 0){//haveGas小于零了说明跑不够一圈进行下一次外层循环index (index 1) % arr.length;//注意是循环最后一位的下一位是第一位haveGas arr[index];//不断更新油量可能多也可能少if (index i) return i;//如果跑了一圈了直接返回i}}return -1;//外层循环结束了都没有返回返回-1}
}class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int[] rest new int[gas.length];int sum 0;int min 0;for (int i 0; i rest.length; i) {rest[i] gas[i] - cost[i];sum rest[i];//计算部分和min Math.min(min,sum);//计算最小部分和}if (sum 0) return -1;//油量不够耗油量肯定跑不完这里其实是剪枝操作这一步也可以省去填不平就返回-1if (min 0) return 0;//最小部分和是0.没更新过那随便跑for (int i rest.length - 1; i 0;i--){//倒着遍历min rest[i];//不断加上油量if (min 0) return i;//恰好填平返回i}return -1;//其实不会执行到这里但还是要返回因为只要sum 0就一定有办法让跑完}
}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 curSum gas[i] - cost[i];totalSum totalSum gas[i] - cost[i];if (curSum 0){//部分和小于零curSum 0;//从0开始重新计算index i 1;//index从i1开始}}if (totalSum 0) return -1;//数组加和小于零一定跑不完否则一定跑的完return index;//从index开始能跑完}
}135. 分发糖果力扣题目链接老师想给孩子们分发糖果有 N 个孩子站成了一条直线老师会根据每个孩子的表现预先给他们评分。你需要按照以下要求帮助老师给这些孩子分发糖果每个孩子至少分配到 1 个糖果。相邻的孩子中评分高的孩子必须获得更多的糖果。那么这样下来老师至少需要准备多少颗糖果呢示例 1:输入: [1,0,2]输出: 5解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。示例 2:输入: [1,2,2]输出: 4解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这已满足上述两个条件。思路需要遍历两次一次不好考虑先从左向右遍历如果右边比左边分高那就是左边的糖果1其他情况都给一个糖果然后从右向左遍历如果左边比右边分高那就要更新糖果取原来的和右边糖果1最大的注意一定要取最大的最后计算数组元素的和即可代码class Solution {public int candy(int[] ratings) {int[] candyVec new int[ratings.length];for (int i 0; i ratings.length; i){//从左向右遍历if (i 0 ratings[i] ratings[i - 1])//比左边大candyVec[i] candyVec[i - 1] 1;//左边的1else {candyVec[i] 1;//其他情况都给1个糖果}}for (int i ratings.length - 1; i 0; i--){//从右向左遍历if (i ratings.length - 1 ratings[i] ratings[i 1])//比右边大candyVec[i] Math.max(candyVec[i],candyVec[i 1] 1);//取原来的和右边糖果数1更大的}int sum 0;for (int candy : candyVec){sum candy;}return sum;//返回candyVec数组元素的和}
}
