代码随想录 - Day37 - 贪心算法

376. 摆动序列

1. 排除只有一个数的情况
2. 把差值全部求出来放到dif里，在此过程中顺便去掉差值为0的情况。
3. 如果dif为空，说明里面所有差值为0，那么最长摆动序列只能是1，直接返回
4. 如果dif不为空，把dif[0]放到result里
5. 根据result的最后一个值，判断要不要把接下来的dif[i]放进去（按照正负交替的顺序）
6. 最终得到的result里的值全都是差值，为了返回最长摆动序列，需要给len(result)加1

这道题不同情况有点多，错了三次才改出最终代码

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1
        dif = []
        for i in range(1, len(nums)):
            t = nums[i] - nums[i - 1]
            if t != 0:
                dif.append(t)
        if dif == []:
            return 1
        else:
            result = [dif[0]]
        for i in range(1, len(dif)):
            if result[len(result) - 1] > 0 and dif[i] < 0:
                result.append(dif[i])
            elif result[len(result) - 1] < 0 and dif[i] > 0:
                result.append(dif[i])
        return len(result) + 1

看了一下题解，他是直接在遍历的过程中求差值+比较，我是先统一求差值，再进行比较。
第二种方法是动态规划，目前暂时看不懂，后面做到动态规划题再说

53. 最大子数组和

本来想用数组记录具有最大和的连续子数组，后面发现遇到只有负数的情况就行不通。
还是得用这个方法：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = float('-inf')
        cnt = 0
        for i in range(len(nums)):
            cnt += nums[i]
            if cnt > maxSum:
                maxSum = cnt
            if cnt <= 0:
                cnt = 0
        return maxSum

122.买卖股票的最佳时机 II

关键点在于分解利润。
假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！
那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。
最后将所有的正利润加起来就可以了。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        liRun = []
        for i in range(1, len(prices)):
            t = prices[i] - prices[i - 1]
            if t > 0:
                liRun.append(t)
        return sum(liRun)        

思维要灵活啊，不要傻傻的想着先找个买入点再找个卖出点再循环往复。

55. 跳跃游戏

不拘泥每次跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的。
要注意，数组中每个元素代表的是从该位置可以跳跃的的最大长度，而不是必须跳这个长度。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cover = 0
        if len(nums) == 1:
            return True
        i = 0
        while i <= cover:
            cover = max(i + nums[i], cover)
            if cover >= len(nums) - 1:
                return True
            i += 1
        return False

for循环的写法

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cover = 0
        if len(nums) == 1: return True
        for i in range(len(nums)):
            if i <= cover:
                cover = max(i + nums[i], cover)
                if cover >= len(nums) - 1: return True
        return False