【贪默算法3】

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

链接: link
思绪

既然要求最大和，那么不妨先给数组排个序，如果有负数，先处理惩罚负数从前往后给数组取反，如果负数处理惩罚完后k尚有次数，此时数组满是正数了，只必要对第一个元素取反即可，无非就是奇数次或者偶数次取反使用。最终求和即可。
方法1:

1. class Solution {
2.     public int largestSumAfterKNegations(int[] nums, int k) {
3.         if (nums.length == 1)
4.             return nums[0];
5.         int ans = 0;
6.         Arrays.sort(nums);
7.         // 先处理负数
8.         for (int i = 0; i < nums.length && k > 0; i++) {
9.             if (nums[i] < 0) {
10.                 nums[i] = -nums[i];
11.                 k--;
12.             }
13.         }
14.         // 如果k还有次数
15.         if (k % 2 == 1) {
16.             Arrays.sort(nums);
17.             nums[0] = -nums[0];
18.         }
19.         for (int num : nums) {
20.             ans += num;
21.         }
22.         return ans;
23.     }
24. }

复制代码

相似题型

134.加油站
链接: link

1. class Solution {
2.     public int canCompleteCircuit(int[] gas, int[] cost) {
3.         int start = 0;
4.         int curSum = 0;
5.         int totalSum = 0;
6.         for (int i = 0; i < gas.length; i++) {
7.             curSum += gas[i] - cost[i];
8.             totalSum += gas[i] - cost[i];
9.             // 如果出现汽油小于使用量
10.             if (curSum < 0) {
11.                 start = i + 1;
12.                 curSum = 0;
13.             }
14.         }
15.         // 总共gas < cost 一定不能跑完一圈
16.         if (totalSum < 0) {
17.             return -1;
18.         }
19.         return start;
20.     }
21. }

复制代码

135.分发糖果
链接: link

1. class Solution {
2.     public int candy(int[] ratings) {
3.         int res = 0;
4.         int[] candyList = new int[ratings.length];
5.         Arrays.fill(candyList, 1);
7.         // 从左向右比较左孩子
8.         for (int i = 1; i < ratings.length; i++) {
9.             if (ratings[i] > ratings[i - 1]) {
10.                 candyList[i] = candyList[i - 1] + 1;
11.             }
12.         }
13.         // 从右向左比较右孩子
14.         for (int i = ratings.length - 2; i >= 0; i--) {
15.             if (ratings[i] > ratings[i + 1]) {
16.                 candyList[i] = Math.max(candyList[i], candyList[i + 1] + 1);
17.             }
18.         }
19.         for (int c : candyList) {
20.             res += c;
21.         }
22.         return res;
23.     }
24. }

复制代码

860.柠檬水找零
链接: link

1. class Solution {
2.     public boolean lemonadeChange(int[] bills) {
3.         int m5 = 0, m10 = 0;
4.         for (int i = 0; i < bills.length; i++) {
5.             if (bills[i] == 5) {
6.                 m5++;
7.             } else if (bills[i] == 10) {
8.                 m10++;
9.                 m5--;
10.             } else if (bills[i] == 20) {
11.                 if (m10 != 0) {
12.                     m10--;
13.                     m5--;
14.                 } else {
15.                     m5 -= 3;
16.                 }
17.             }
18.             if (m5 < 0 || m10 < 0) {
19.                 return false;
20.             }
21.         }
22.         return true;
23.     }
24. }

复制代码

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

1. class Solution {
2.     public int[][] reconstructQueue(int[][] people) {
3.         // 对身高排序
4.         Arrays.sort(people, (a, b) -> {
5.             if (a[0] == b[0])
6.                 return a[1] - b[1]; // a-b 是升序排列，按照k升序
7.             return b[0] - a[0];// 否则按照身高降序排列
8.         });
9.         List<int[]> que = new ArrayList<>();
10.         for (int i = 0; i < people.length; i++) {
11.             que.add(people[i][1], people[i]);
12.         }
13.         return que.toArray(new int[people.length][]);
14.     }
15. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。