代码随想录 Day34 - 贪心算法（三）
作者：jjn0703
- 2023-08-01 江苏
本文字数：1851 字
阅读完需：约 6 分钟
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); }}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/1fc43ba9a2f7b236f1b1168a8】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论