博客

# 代码随想录训练营第III期--034--python


#  1005.K次取反后最大化的数组和 
# 学习了一个很巧妙的想法，每次将最小的数字的符号转换了
class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()
        while k!=0:
            nums[0] = -nums[0]
            k -= 1
            nums.sort()

        return sum(nums)

#  134. 加油站
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        cs = ss = start = 0
        for i in range(len(gas)):
            cs += gas[i] - cost[i]
            ss += gas[i] - cost[i]
            if cs < 0:
                start = i + 1
                cs = 0 
        if ss < 0: return -1
        return start 

#  135. 分发糖果  
    def candy(self,rating):
        n = len(rating)
        left = [0] * n 
        for i in range(n):
            if i>0 and rating[i] > rating[i-1]:
                left[i] = left[i - 1] + 1
            else:
                left[i] = 1

        right = ret = 0
        for i in range(n-1, -1, -1):
            if i<n-1 and rating[i] > rating[i+1]:
                right += 1
            else:
                right = 1
            ret += max(left[i], right)

        return ret