IT评测·应用市场-qidao123.com

标题: 每日一题——贪默算法 [打印本页]

---

作者: 道家人    时间: 2024-8-3 13:30
标题: 每日一题——贪默算法
1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
题解：

一开始有点理解错他的意思，以为是i是标题中会给出，所以一开始没有什么思路，然后当看了题解之后，就知道了原来i是自己订的，到时候自己找就可以，我的思路是，先按照绝对值的大小给他排列出来，然后给他遍历，负数就给他变成正数，当没负数的时候，再变小的正数，这就是贪心的思想由局部最小推出整体最小！

1. [/code] [code]class Solution {
2.     public int largestSumAfterKNegations(int[] nums, int k) {
3.         nums = IntStream.of(nums).boxed().sorted((o1,o2) -> Math.abs(o2)-Math.abs(o1)).
4.                 mapToInt(Integer::intValue).toArray();
5.         int len = nums.length;
6.         for(int i = 0;i < len;i++){
7.             if(nums[i]<0 && k<0){
8.                nums[i] = -nums[i];
9.                k--;
10.             }
11.         }
12.         if(k%2==1){
13.            nums[len-1] = -nums[len-1];
14.         }
15.         return Arrays.stream(nums).sum();
16.     }
17. }

复制代码

134. 加油站 - 力扣（LeetCode）

这个标题一开始并不是很明白，看了题解之后发现有三种情况，第一种情况就是，当加油站的油的总和小于消耗的油的话就不会绕圈一周，当总和大于等于0的时候就返回0

1. [/code] [code]class Solution {
2.     public int canCompleteCircuit(int[] gas, int[] cost) {
3.         int sum = 0;
4.         int min = 0;
5.         for(int i = 0; i < gas.length;i++){
6.             sum += (gas[i]-cost[i]);
7.             min = Math.min(sum,min);
8.         }
9.         if(sum<0){
10.             return -1;
11.         }
12.         if(min>=0){
13.             return 0;
14.         }
16.         for(int i = gas.length-1;i > 0;i--){
17.             min += (gas[i] - cost[i]);
18.             if(min>=0){
19.                 return i;
20.             }
22.         }
23.         return -1;
25.     }
26. }

复制代码

135. 分发糖果 - 力扣（LeetCode）

该题的思路就是分两种情况，就是先从左往右比，如果右边的数比左边的大就加一，然后就反过来遍历，如果左边的数比右边的数大就加一；

1. [/code] [code]class Solution {
2.     public int candy(int[] ratings) {
3.         int len = ratings.length;
4.         int[] candyVec = new int[len];
5.         candyVec[0] = 1;
6.         for(int i = 1; i < len; i++){
7.             if(ratings[i]>ratings[i-1]){
8.                 candyVec[i] = candyVec[i-1]+1;
9.             }else{
10.                 candyVec[i] = 1;
11.             }
12.         }
13.         for(int i = len-2;i>=0;i--){
14.             if(ratings[i]>ratings[i+1]){
15.                 candyVec[i] = Math.max(candyVec[i],candyVec[i+1]+1);
16.             }
17.         }
18.         int ans = 0;
19.         for(int num : candyVec){
20.             ans += num;
21.         }
22.         return ans;
23.     }
24. }

复制代码

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

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4