每日一题——贪心算法

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

题解：

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

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {nums = IntStream.of(nums).boxed().sorted((o1,o2) -> Math.abs(o2)-Math.abs(o1)).mapToInt(Integer::intValue).toArray();int len = nums.length;for(int i = 0;i < len;i++){if(nums[i]<0 && k<0){nums[i] = -nums[i];k--;}}if(k%2==1){nums[len-1] = -nums[len-1];}return Arrays.stream(nums).sum();}
}

134. 加油站 - 力扣（LeetCode）

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

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int sum = 0;int min = 0;for(int i = 0; i < gas.length;i++){sum += (gas[i]-cost[i]);min = Math.min(sum,min);}if(sum<0){return -1;}if(min>=0){return 0;}for(int i = gas.length-1;i > 0;i--){min += (gas[i] - cost[i]);if(min>=0){return i;}}return -1;}
}

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

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

class Solution {public int candy(int[] ratings) {int len = ratings.length;int[] candyVec = new int[len];candyVec[0] = 1;for(int i = 1; i < len; i++){if(ratings[i]>ratings[i-1]){candyVec[i] = candyVec[i-1]+1;}else{candyVec[i] = 1;}}for(int i = len-2;i>=0;i--){if(ratings[i]>ratings[i+1]){candyVec[i] = Math.max(candyVec[i],candyVec[i+1]+1);}}int ans = 0;for(int num : candyVec){ans += num;}return ans;}
}