郑州彩票网站建设,沈阳响应式网站建设,山东建设厅官网,电子商务网站多少钱1005. Maximize Sum Of Array After K Negations
参考视频#xff1a;贪心算法#xff0c;这不就是常识#xff1f;还能叫贪心#xff1f;LeetCode#xff1a;1005.K次取反后最大化的数组和_哔哩哔哩_bilibili
贪心#x1f50d;
的思路#xff0c;局部最优#xff…1005. Maximize Sum Of Array After K Negations
参考视频贪心算法这不就是常识还能叫贪心LeetCode1005.K次取反后最大化的数组和_哔哩哔哩_bilibili
贪心
的思路局部最优让绝对值大的负数变为正数当前数值达到最大整体最优整个数组和达到最大。
局部最优可以推出全局最优。
那么如果将负数都转变为正数了K依然大于0此时的问题是一个有序正整数序列如何转变K次正负让 数组和 达到最大。
那么又是一个贪心局部最优只找数值最小的正整数进行反转当前数值和可以达到最大例如正整数数组{5, 3, 1}反转1 得到-1 比 反转5得到的-5 大多了全局最优整个 数组和 达到最大。
虽然这道题目大家做的时候可能都不会去想什么贪心算法一鼓作气就AC了。
我这里其实是为了给大家展现出来 经常被大家忽略的贪心思路这么一道简单题就用了两次贪心
那么本题的解题步骤为
第一步将数组按照绝对值大小从大到小排序注意要按照绝对值的大小 第二步从前向后遍历遇到负数将其变为正数同时K-- 第三步如果K还大于0那么反复转变数值最小的元素将K用完 第四步求和
public class Leetcode1005 {public static int largestSumAfterKNegations(int[] nums, int k) {sort(nums);for (int i 0; i nums.length; i) {if (k 0 nums[i] 0) {nums[i] * -1;k--;}}if (k % 2 1) nums[nums.length - 1] * -1;int res 0;for (int num : nums) {res num;}return res;}public static void sort(int[] nums) {for (int i 0; i nums.length; i) {for (int j i 1; j nums.length; j) {if (Math.abs(nums[i]) Math.abs(nums[j])) {int temp nums[j];nums[j] nums[i];nums[i] temp;}}}}
}134. 加油站
解题思路
可以换一个思路首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]和记为curSum一旦curSum小于零说明[0, i]区间都不能作为起始位置因为这个区间选择任何一个位置作为起点到i这里都会断油那么起始位置从i1算起再从0计算curSum。
public class Leetcode134 {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum 0;int totalSum 0;int start 0;for (int i 0; i gas.length; i) {curSum (gas[i] - cost[i]);totalSum (gas[i] - cost[i]);if (curSum 0) {start i 1;curSum 0;}}if (totalSum 0) return -1;return start;}
} 135. 分发糖果
public class Leetcode135 {public static int candy(int[] ratings) {int[] candy new int[ratings.length];Arrays.fill(candy, 1);for (int i 1; i ratings.length; i) {if (ratings[i] ratings[i - 1]) {candy[i] candy[i - 1] 1;}}System.out.println(Arrays.toString(candy));for (int i ratings.length - 2; i 0; i--) {if (ratings[i] ratings[i 1]) {candy[i] Math.max(candy[i 1] 1, candy[i]);}}System.out.println(Arrays.toString(candy));int res 0;for (int i : candy) {res i;}return res;}
}
