1005. K 次取反后最大化的数组和
本题目，通过排序先找到负数，优先将负数变为正数。此时再行排序，对于剩余的 k，最多只需要让数组第一个元素变为其相反数。
package jjn.carl.greedy; import java.util.Arrays; import java.util.Scanner; /** * @author Jjn * @since 2023/8/1 10:13 */ public class LeetCode1005 { public int largestSumAfterKNegations(int[] nums, int k) { Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (nums[i] < 0 && k > 0) { k--; nums[i] = -nums[i]; } else { break; } } k = k % 2; Arrays.sort(nums); if (k > 0) { nums[0] = -nums[0]; } int total = 0; for (int num : nums) { total += num; } return total; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int total = scanner.nextInt(); int k = scanner.nextInt(); int[] nums = new int[total]; for (int i = 0; i < total; i++) { nums[i] = scanner.nextInt(); } int largestSumAfterKNegations = new LeetCode1005().largestSumAfterKNegations(nums, k); System.out.println(largestSumAfterKNegations); } }
134. 加油站
采用累加和的方法，若累加到一个负数，则下一位极有可能是我们想要的起始位置。
package jjn.carl.greedy; import java.util.Scanner; /** * @author Jjn * @since 2023/8/1 12:03 */ public class LeetCode134 { public int canCompleteCircuit(int[] gas, int[] cost) { int totalSum = 0, currentSum = 0; int start = 0; for (int i = 0; i < gas.length; i++) { totalSum += (gas[i] - cost[i]); currentSum += (gas[i] - cost[i]); if (currentSum < 0) { currentSum = 0; start = i + 1; } } if (totalSum < 0) { return -1; } return start; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[] gas = new int[count]; int[] cost = new int[count]; for (int i = 0; i < count; i++) { gas[i] = scanner.nextInt(); } for (int i = 0; i < count; i++) { cost[i] = scanner.nextInt(); } int canCompleteCircuit = new LeetCode134().canCompleteCircuit(gas, cost); System.out.println(canCompleteCircuit); } }
135. 分发糖果
一遍正序遍历，一遍反序遍历即可。
package jjn.carl.greedy; import java.util.Arrays; import java.util.Scanner; /** * @author Jjn * @since 2023/8/1 12:35 */ public class LeetCode135 { public int candy(int[] ratings) { int[] candyNum = new int[ratings.length]; Arrays.fill(candyNum, 1); for (int i = 1; i < ratings.length; i++) { if (ratings[i] > ratings[i - 1]) { candyNum[i] = candyNum[i - 1] + 1; } } for (int i = ratings.length - 2; i >= 0; i--) { if (ratings[i + 1] < ratings[i]) { candyNum[i] = Math.max(candyNum[i], candyNum[i + 1] + 1); } } int total = 0; for (int candy : candyNum) { total += candy; } return total; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int total = scanner.nextInt(); int[] ratings = new int[total]; for (int i = 0; i < total; i++) { ratings[i] = scanner.nextInt(); } int candy = new LeetCode135().candy(ratings); System.out.println(candy); } }
