Day33题目
LeetCode1005:K 次取反后最大化的数组和
核心思想:每次取反都取反最小的。如果有负数,则一直取反最小的负数,如果没有就取反正数。取反次数只需要看是奇数还是偶数。偶数则正数序列不变,奇数则最小的变成负数
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {// 负数的话直接取反最小的,正数的话取反最小的,2次则重新取反为正数Arrays.sort(nums);// index记录的第一个非负数元素的位置int index = 0;while (nums[index] <= 0 && index<nums.length-1) {index++;}// 如果没有负数if (index == 0) {if (k % 2 != 0) {// 只有在变化次数是偶数的时候,把最小的正数变成负数就行了nums[0] = 0 - nums[0];}} else {// 变化的次数大于负数的个数if (index < k) {// 首先把负数都变成正数for (int i = 0; i < index; i++) {nums[i] = 0 - nums[i];}// 如果还剩下奇数次的变化if ((k - index) % 2 != 0) {// 排序之后将第一个变化为负数Arrays.sort(nums);nums[0] = 0 - nums[0];}} else {// 如果变化次数小于负数,按顺序从小到大把负数变成正数就行for (int i = 0; i < k; i++) {nums[i] = 0 - nums[i];}}}// 这里计算结果int sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];}return sum;}
}
LeetCode134加油站:
核心思想:每一个站点的加油量减去到下一个站的消耗量,就是这个站点的结余。如果结余是负数,那么就需要其他站点来补充。整个加油站是个环,那么就直接从负数的下一个开始。如果总共的结余总和为负数,那么从哪开始都是走不完的
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {// 当前节点的结余量int curSum =0 ;int totalSum = 0;// 从哪个开始int start = 0;for(int i = 0 ; i < cost.length ; i++){totalSum += gas[i] - cost[i];curSum += gas[i] - cost[i];// 这里 我觉得可以判断是不是最小的,从最小的下一个开始走。但是好像没影响if(curSum < 0 ){curSum = 0 ;start = i + 1;}}if(totalSum < 0 ){return -1;}return start;}
}
LeetCode135分发糖果:
核心思想:从左往右遍历一次,比左边大就+1,比左边小就置为1(贪心)。这样的话,如果右边比左边小减一的话,就可能得到负数。从右边往左边遍历左边比右边大的情况,如果左边比右边大就右边右边的+1,然后和之前左边遍历的取较大的
class Solution {public int candy(int[] ratings) {// 用来存储每个分到几个糖int[] candyList = new int[ratings.length];// 第一个置为1,最小为1candyList[0] = 1;for(int i = 1 ; i < ratings.length ; i ++){if(ratings[i-1] < ratings[i]){// 右边比左边大,+1candyList[i] = candyList[i-1]+1;}else{// 否则就是1candyList[i] = 1;}}for(int i = ratings.length - 2 ; i >= 0 ; i --){int cur = ratings[i];int next = ratings[i+1];if(cur > next ){// 左边比右边大// 取右边+1 和原有值的较大值candyList[i] = Math.max(candyList[i],candyList[i+1] +1);}}// 计算结果int sum = 0;for(int i = 0; i < ratings.length; i ++){sum += candyList[i];}return sum;}
}