算法题day36(补5.22日卡)
一、刷题:
1.leetcode题目 1005. K 次取反后最大化的数组和 - 力扣(LeetCode)(easy)
解决:
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:nums[i] = -nums[i]k -= 1if k== 0:return sum(nums)if k>0:if k%2==0:return sum(nums)if k%2 == 1:nums[-1] = - nums[-1]return sum(nums)
2.leetcode题目 134. 加油站 - 力扣(LeetCode)(medium)
解决:
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:cur_sum = 0start = 0if sum(gas) < sum(cost):return -1for i in range(len(gas)):cur_sum += gas[i] - cost[i]if cur_sum<0:start = i +1cur_sum = 0return start
3.leetcode题目 135. 分发糖果 - 力扣(LeetCode)(hard)
解决:
感觉这道hard题不太像hard题。
class Solution:def candy(self, ratings: List[int]) -> int:candies = [1] *len(ratings)for i in range(1,len(ratings)):if ratings[i]>ratings[i-1] :candies[i] = candies[i-1] + 1for i in range(len(ratings)-2,-1,-1):if ratings[i]>ratings[i+1] and candies[i] <= candies[i+1]:candies[i] = candies[i+1] + 1return sum(candies)