当前位置：首页 > news >正文

代码随想录算法训练营第三十三天| 1005.K次取反后最大化的数组和，134. 加油站，135. 分发糖果

news 来源：原创 2024/9/29 13:32:16

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);int i = 0;while (i < nums.length && nums[i] < 0 && k > 0) {nums[i] = nums[i] * -1;i++;k--;}// K大于0，表示负数已经处理完毕了，还需转换if (k % 2 != 0) {if (i == nums.length) {i = nums.length - 1;}if (i == 0 || (i > 0 && nums[i] < nums[i - 1])) {nums[i] = nums[i] * -1;} else {nums[i - 1] = nums[i - 1] * -1;}}int result = 0;for (int j = 0; j < nums.length; j++) {result += nums[j];}return result;}
}

134. 加油站 - 力扣（LeetCode）

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {// if (gas.length == 1 && gas[0] >= cost[0]) {//     return 0;// }// int[] remain = new int[gas.length];// int sum = 0;// for (int i = 0; i < remain.length; i++) {//     remain[i] = gas[i] - cost[i];//     sum += remain[i];// }// if (sum < 0) {//     return -1;// }// for (int i = 0; i < remain.length; i++) {//     if (remain[i] <= 0) {//         continue;//     }//     sum = remain[i];//     int j = i + 1;//     for (; sum >= 0 && j % remain.length != i; j++) {//         sum += remain[j % remain.length];//     }//     if (sum >= 0 && j % remain.length == i) {//         return i;//     }// }// return -1;for (int i = 0; i < gas.length; i++) {int sumGas = 0;int sumCost = 0;int j = 0;while (sumGas >= sumCost && j <= gas.length) {sumGas += gas[(i + j) % gas.length];sumCost += cost[(i + j) % gas.length];j++;}if (sumGas >= sumCost && j > gas.length) {return i;} else {i = i + j - 1;}}return -1;}
}

135. 分发糖果 - 力扣（LeetCode）

class Solution {public int candy(int[] ratings) {int[] result = new int[ratings.length];Arrays.fill(result,1);for(int i=1;i<ratings.length;i++){if(ratings[i] > ratings[i-1]){result[i] = result[i-1] +1;}}for(int j=ratings.length-2;j>=0;j--){if(ratings[j] >ratings[j+1]){if(result[j] < result[j+1]+1){result[j] = result[j+1] +1;}}}int sum = 0;for(int k=0;k<ratings.length;k++){sum+= result[k];    }return sum;}
}