代码随想录算法训练营第三十六天（贪心算法篇）

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

题目链接：1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

思路

（给自己的的忠告：做一道题之前一定要冷静思考后再“下键盘”，不要一有想法就开始敲，更不要依赖测试用例，为它们【量身打造】代码，极大可能只是“拆了东墙补西墙”！要掌握大方向，从整体出发。)

如果存在负数，应先反转绝对值最大的数，因此先把数组按绝对值大小从高到低排序。然后，从前往后看数的正负性，先翻所有负数（所以要遍历整个数组，负数可能因为绝对值小在数组末位），如果翻完后还没用完K次，或者数组中全是正数，就翻绝对值最小的正数（即数组最后一个）。之所以按绝对值大小排序，而不是直接排序，是因为后者无法确定更新后的数组中绝对值最小的正数在哪里，不一定是遇到的第一个正数，可能前面反转后的负数的绝对值更小！按绝对值大小排序，如果遇到负数，会直接从前往后的顺序反，而遇到正数，只用反数组最后一个。）

后面还想到了更简单一点的代码，即每次重新排序，将最小的数翻过来，直到翻完K次为止。但代码简单了，计算机运行可不简单，因为要排序K次。

代码实现

class Solution(object):
    def largestSumAfterKNegations(self, nums, k):
        nums.sort(key = lambda x: abs(x), reverse = True)
        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] *= -1
                k -= 1
        if k%2 == 1: # 如果剩下的K次是偶数，相当于没翻。
            nums[i] = - nums[i]

        return sum(nums)

class Solution(object):
    def largestSumAfterKNegations(self, nums, k):
        i = 0
        while i < k:
            nums.sort()
            nums[0] *= -1
            i += 1           
        return sum(nums)

134. 加油站?

题目链接：https://leetcode.cn/problems/gas-station/

思路

写了一个暴力代码，从每一个位置试，结果通过案例只有33/40，后面的都超时了。。。

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        start = 0
        while start <= len(gas):
            newgas = gas[start:] + gas[0:start]
            newcost = cost[start:] + cost[0:start]
            cum = newgas[0]
            for i in range(len(gas)):    
                if i == len(newgas) - 1 and cum - newcost[i]>=0:
                    return start  
                if  i == len(newgas) - 1 and cum - newcost[i]<0:
                    start +=1
                    break        
                elif cum - newcost[i] < 0:
                    start += 1
                    break
                else:
                    cum -= newcost[i]
                    cum += newgas[i+1]
        return -1

使用贪心算法。如果cost总和大于gas总和，那肯定无法跑完一圈。每次都累计当前加油站剩余的汽油量gas[i] - cost[i],当累积量小于0时，说明从[0,i]区间的任意一个站点都不能作为起始点，因此起始点从当前位置的后一个开始看，累积量重置为0。

代码实现

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

        return start