代码随想录刷题第三十四天| 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果

代码随想录刷题第三十四天

K次取反后最大化的数组和 (LC 1005)

题目思路：

代码实现：

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-=1

        if k%2==1:
            nums[-1] = -nums[-1]
        
        result = sum(nums)
        return result

加油站 (LC 134)

题目思路：

代码实现：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curSum = 0
        totalSum = 0
        start = 0
        for i in range(len(gas)):
            curSum+=gas[i]-cost[i]
            totalSum+=gas[i]-cost[i]
            if curSum<0:
                curSum=0
                start=i+1
        if totalSum<0:
            return -1
        return start

分发糖果 (LC 135)

题目思路：

代码实现：

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candy0 = [0 for _ in range(len(ratings))]
        candy1 = [0 for _ in range(len(ratings))]
        candy0[0] = 1
        candy1[len(ratings)-1] = 1

        for i in range(1,len(ratings)):
            if ratings[i] > ratings[i-1]:
                candy0[i] = candy0[i-1]+1
            else:
                candy0[i] = 1
        
        for i in range(len(ratings)-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                candy1[i] = candy1[i+1]+1
            else:
                candy1[i] = 1
        sum1 = 0
        for i in range(len(candy0)):
            sum1+=max(candy0[i], candy1[i])
        
        return sum1