LeetCode T1005 K次取反后最大化的数组和
题目链接:1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
题目思路:
这道题的意思是,有一个数组,你指定对数组中的元素进行k次取反(取反的数是你定的),最后希望返回可能的结果中的最大值,我们仍然采用贪心算法,我们首先想将尽可能小的负数,也就是绝对值尽可能大的负数变成正数,然后如果k还是大于0的,我们就对绝对值最小的元素进行取反,这里如果k%2余数是偶数,就无需操作,余数是奇数,就操作一次取反即可
这里第一个没有完全按照这个思路,但大体没问题
1.对负数转正数(先排序,让最小的在最前面)
Arrays.sort(nums); for(int i = 0;i<nums.length;i++) { if(nums[i]<0 && k>0) { nums[i] = -nums[i]; k--; } }
2.对剩下的k次进行处理(也要先排序,因为前面转正之后变成了无序的数组)
Arrays.sort(nums); k = k % 2; if(k == 1) { nums[0] = -nums[0]; }
题目代码:
1.按照绝对值排序法(逻辑更清晰,企业中使用更多)
class Solution { public int largestSumAfterKNegations(int[] nums, int K) { int sum = 0; Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (nums[i] < 0 && K > 0) { nums[i] = -nums[i]; K--; } } Arrays.sort(nums); if (K % 2 == 1) { nums[0] = -nums[0]; } for(int i = 0;i<nums.length;i++) { sum += nums[i]; } return sum; } }
2.笔者使用方法,效率相当
class Solution { public int largestSumAfterKNegations(int[] nums, int k) { int sum = 0; Arrays.sort(nums); for(int i = 0;i<nums.length;i++) { if(nums[i]<0 && k>0) { nums[i] = -nums[i]; k--; } } Arrays.sort(nums); k = k % 2; if(k == 1) { nums[0] = -nums[0]; } for(int j = 0;j<nums.length;j++) { sum += nums[j]; } return sum; } }
LeetCode T134 加油站
题目思路:
这道题的意思是,给定一个gas数组和一个cost数组,要求我们从一个点出发,如果能再回到这个点,那么我们就返回这个出发点的下标,如果不能,那么就返回-1即可
这里我们使用贪心的解法,首先我们判断一下这里所有的油和消耗之差是否有盈余,如果没有,那么本题无解,所以我们定义一个变量totalSum来查看是否有解
for(int i = 0;i<gas.length;i++) { int temp = gas[i] - cost[i]; totalSum += temp; } if(totalSum < 0) { return -1; }
知道有解之后,我们该判断从哪里出发了,这里我们定义一个sum来代表目前邮箱的油量情况,
每次记录每个站点的油量和消耗差,添加到sum中,如果sum小于0了,那么从前面的站点出发都是不可能的 ,后面我们将sum置0重新开始即可
那么为什么一旦[0，i] 区间和为负数，起始位置就可以是i+1呢，i+1后面就不会出现更大的负数？
如果出现更大的负数，就是更新i，那么起始位置又变成新的i+1了。
那有没有可能 [0，i] 区间 选某一个作为起点，累加到 i这里 curSum是不会小于零呢？
如图:
如果 curSum<0 说明 区间和1 + 区间和2 < 0， 那么 假设从上图中的位置开始计数curSum不会小于0的话，就是 区间和2>0。
区间和1 + 区间和2 < 0 同时 区间和2>0，只能说明区间和1 < 0， 那么就会从假设的箭头初就开始从新选择其实位置了。
for(int i = 0;i<gas.length;i++) { int temp = gas[i] - cost[i]; sum += temp; if(sum < 0) { index = i+1; sum = 0; } }
题目代码:
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int sum = 0; int totalSum = 0; int index = 0; for(int i = 0;i<gas.length;i++) { int temp = gas[i] - cost[i]; totalSum += temp; } if(totalSum < 0) { return -1; } for(int i = 0;i<gas.length;i++) { int temp = gas[i] - cost[i]; sum += temp; if(sum < 0) { index = i+1; sum = 0; } } return index; } }
LeetCode T135 分发糖果
题目思路:
这题我们不能进行一次for循环两边一起比较,否则一定会顾此失彼,所以我们选择两次for循环来决定答案,首先我们创建一个数组来存放每个孩子获得的糖果数,我们将第一个孩子置为1,向右比较,如果此时右孩子比左孩子大,那么它的糖果数就比左孩子多1,否则就给1就可以,因为每个孩子至少要分得一个糖果.
1.和左边比较
for(int i = 1;i<ratings.length;i++) { candyVec[i] = ratings[i]>ratings[i-1]?candyVec[i-1]+1:1; }
2.和右边比较
比较右孩子是否比左孩子大的时候一定得从后往前遍历,因为我下一个左右孩子比较会用到后面产生的结果,如图所示
我们要获取4,5下标的结果,就一定要先知道5,6的结果,由此,只能从后向前遍历
这里如果i下标的值大于i+1的时候,我们就让i此时的糖果取之前比较值和i+1下标的糖果值中的较大值,因为要满足比两边的糖果都多
for(int i = ratings.length-2;i>=0;i--) { if(ratings[i]>ratings[i+1]) { candyVec[i] = Math.max(candyVec[i],candyVec[i + 1] + 1); } }
最后求和即可
题目代码:
class Solution { public int candy(int[] ratings) { int[] candyVec = new int[ratings.length]; candyVec[0] = 1; for(int i = 1;i<ratings.length;i++) { candyVec[i] = ratings[i]>ratings[i-1]?candyVec[i-1]+1:1; } for(int i = ratings.length-2;i>=0;i--) { if(ratings[i]>ratings[i+1]) { candyVec[i] = Math.max(candyVec[i],candyVec[i + 1] + 1); } } int sum = 0; for(int num:candyVec) { sum += num; } return sum; } }
