本題簡單一些，估計大家不用想著貪心?，用自己直覺也會有思路。?

代碼隨想錄

Python:

class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:nums.sort(key=lambda x: abs(x), reverse=True) # 關鍵：按絕對值降序排列for i in range(len(nums)):if nums[i]<0 and k>0:nums[i] = -nums[i]k -= 1if k%2==1: nums[-1] *= -1return sum(nums)

C++：

class Solution {
static bool cmp(int a, int b) {return abs(a) > abs(b);
}
public:    int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), cmp); //注意：這里cmp是static methodfor (int i=0; i<nums.size(); i++) {if (nums[i]<0 && k>0) {nums[i] *= -1;k--;}}if (k%2==1) nums[nums.size()-1] *= -1;int ans = 0;for (int a:nums) ans+=a;return ans;}
};

134.?加油站?

本題有點難度，不太好想，推薦大家熟悉一下方法二?

代碼隨想錄

Python:

情況三是比較難想到的，從后向前看如何覆蓋cum_sum of net gas.

• 情況三：如果累加的最小值是負數，汽車就要從非0節點出發，從后向前，看哪個節點能把這個負數填平，能把這個負數填平的節點就是出發節點。

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:cum_sum = 0min_net = float('inf')for i in range(len(gas)):cum_sum += gas[i] - cost[i]if cum_sum < min_net:min_net = cum_sumif cum_sum < 0: return -1if min_net > 0: return 0for i in reversed(range(len(gas))):min_net += gas[i] - cost[i]if min_net >= 0:return ireturn -1

C++：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int cumSum = 0;int minCumSum = INT_MAX;for (int i=0; i<gas.size(); i++) {cumSum += gas[i] - cost[i];if (cumSum < minCumSum) minCumSum = cumSum;}if (cumSum < 0) return -1;if (minCumSum > 0) return 0;for (int i=gas.size()-1; i>=0; i--) {minCumSum += gas[i] - cost[i];if (minCumSum >=0) return i;}return -1;}
};

135.?分發糖果?

本題涉及到一個思想，就是想處理好一邊再處理另一邊，不要兩邊想著一起兼顧，后面還會有題目用到這個思路?

代碼隨想錄

Python:

class Solution:def candy(self, ratings: List[int]) -> int:n = len(ratings)if n == 1: return 1ans = [1] * n for i in range(1, n): # 從前往后if ratings[i] > ratings[i-1]:ans[i] = ans[i-1] + 1for i in reversed(range(n-1)): # 從后往前if ratings[i] > ratings[i+1]:ans[i] = max(ans[i], ans[i+1]+1)return sum(ans)

C++：

class Solution {
public:int candy(vector<int>& ratings) {if (ratings.size()==1) return 1;vector<int> candyVec(ratings.size(), 1);    for (int i=1; i<ratings.size(); i++) {if (ratings[i] > ratings[i-1]) candyVec[i] = candyVec[i-1] + 1;}for (int i=ratings.size()-2; i>=0; i--) {if (ratings[i] > ratings[i+1]) candyVec[i] = max(candyVec[i], candyVec[i+1]+1);}int ans = 0;for (int c: candyVec) ans += c;return ans;}
};