【贪心算法3】

力扣1005.k次取反后最大化的数组和

链接: link

思路

既然要求最大和，那么不妨先给数组排个序，如果有负数，先处理负数从前往后给数组取反，如果负数处理完后k还有次数，此时数组全是正数了，只需要对第一个元素取反即可，无非就是奇数次或者偶数次取反操作。最终求和即可。

方法1:

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {if (nums.length == 1)return nums[0];int ans = 0;Arrays.sort(nums);// 先处理负数for (int i = 0; i < nums.length && k > 0; i++) {if (nums[i] < 0) {nums[i] = -nums[i];k--;}}// 如果k还有次数if (k % 2 == 1) {Arrays.sort(nums);nums[0] = -nums[0];}for (int num : nums) {ans += num;}return ans;}
}

相似题型

134.加油站
链接: link

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int start = 0;int curSum = 0;int totalSum = 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;}}// 总共gas < cost 一定不能跑完一圈if (totalSum < 0) {return -1;}return start;}
}

135.分发糖果
链接: link

class Solution {public int candy(int[] ratings) {int res = 0;int[] candyList = new int[ratings.length];Arrays.fill(candyList, 1);// 从左向右比较左孩子for (int i = 1; i < ratings.length; i++) {if (ratings[i] > ratings[i - 1]) {candyList[i] = candyList[i - 1] + 1;}}// 从右向左比较右孩子for (int i = ratings.length - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candyList[i] = Math.max(candyList[i], candyList[i + 1] + 1);}}for (int c : candyList) {res += c;}return res;}
}

860.柠檬水找零
链接: link

class Solution {public boolean lemonadeChange(int[] bills) {int m5 = 0, m10 = 0;for (int i = 0; i < bills.length; i++) {if (bills[i] == 5) {m5++;} else if (bills[i] == 10) {m10++;m5--;} else if (bills[i] == 20) {if (m10 != 0) {m10--;m5--;} else {m5 -= 3;}}if (m5 < 0 || m10 < 0) {return false;}}return true;}
}

406.根据身高重建队列
链接: link

class Solution {public int[][] reconstructQueue(int[][] people) {// 对身高排序Arrays.sort(people, (a, b) -> {if (a[0] == b[0])return a[1] - b[1]; // a-b 是升序排列，按照k升序return b[0] - a[0];// 否则按照身高降序排列});List<int[]> que = new ArrayList<>();for (int i = 0; i < people.length; i++) {que.add(people[i][1], people[i]);}return que.toArray(new int[people.length][]);}
}