Leetcode DAY 34: K次取反后最大化的数组和 and 加油站 and 分发糖果

• 1005.K次取反后最大化的数组和

class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:nums = sorted(nums, key = abs, reverse = True)for i in range(len(nums)):if nums[i] < 0:nums[i] = -nums[i]k -= 1else:continueif k == 0:return sum(nums)if k > 0:if k % 2 == 0:return sum(nums)else:nums[-1] = -nums[-1]return sum(nums)

• 134. 加油站

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {// 累加i ~ i+1 的剩余的汽油 < 0 说明要从当前i的下一个位置起始  // 如果累加每一趟剩余汽油 < 0 说明不存在int cursum = 0;int totalsum = 0;int start = 0;for(int i = 0; i < gas.size(); i++) {cursum += gas[i] - cost[i];totalsum += gas[i] - cost[i];if(cursum < 0) {start = i + 1;cursum = 0; //清零}}if(totalsum < 0) {return -1;}return start;}
};

• 135. 分发糖果

• class Solution {
  public:int candy(vector<int>& ratings) {vector<int> candy(ratings.size(), 1);//先从左往右 比较 右边是否比左边大for(int i = 0; i < ratings.size() - 1; i++) {if(ratings[i] < ratings[i + 1]) {candy[i + 1] = candy[i] + 1;}}for(int i = ratings.size() - 1; i > 0; i--) {if(ratings[i - 1] > ratings[i]) {candy[i - 1] = max(candy[i - 1], candy[i] + 1);}}int res = 0;for(int i = 0; i < candy.size(); i++) {res += candy[i];}return res;}
  };