算法day32|122，55，45

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

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(len(prices)-1):
            diff = prices[i+1]-prices[i]
            if diff > 0:
                profit += diff
            else:
                profit += 0
        return profit

简单到我不敢相信。

本题解法很巧妙，大家可以看题思考一下，在看题解。

局部最优：收集每天的正利润，全局最优：求得最大利润。

局部最优可以推出全局最优，找不出反例，试一试贪心！

题解

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        for i in range(1, len(prices)):
            result += max(prices[i] - prices[i - 1], 0)
        return result

代码随想录

二刷：（未ac）

var maxProfit = function(prices) {
    let result = 0
    for(let i = 1;i<prices.length;i++){
        result += Math.max(prices[i]-prices[i-1],0)
    }
    return result
};

55. 跳跃游戏

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cover = 0
        #如果nums里面只有一个数，总是能到达终点的
        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

还挺难理解的，就是说，局部最优，每次都走最大的。看这个图。一切就明白了 

代码随想录

js:(未ac)

var canJump = function(nums) {
    let cover = 0
    if(nums.length === 1) return true
    //i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。
    for(let i = 0;i<= cover;i++){
        cover = Math.max(nums[i]+i,cover)
        if(cover >= nums.length-1){return true}
    }
    return false
};

45.跳跃游戏II

class Solution:
    def jump(self, nums: List[int]) -> int:
        curdistance = 0
        count = 0
        nextdistance = 0
        for i in range(len(nums)):
            nextdistance = max(i+nums[i],nextdistance)
            if i == curdistance:
                if curdistance !=len(nums)-1:
                    count +=1
                    curdistance = nextdistance
                    if nextdistance >=len(nums)-1:
                        break
                else:
                    break
        return count 

好难理解，我不太能理解反正就是。。。

class Solution:
    def jump(self, nums: List[int]) -> int:
        curdistance = 0
        count = 0
        nextdistance = 0
        for i in range(len(nums)-1):
            nextdistance = max(i+nums[i],nextdistance)
            if i == curdistance:
                curdistance = nextdistance
                count +=1
        return count 

二刷（确实很难理解）

需要知道我们使用贪心算法，所以我们贪心的是少步数

局部最优：找步数最少，如果它已经走到了最大范围，但是还没有到达结果，只能多加一步，只能更新下一步，没有办法了，最优了，步数最少了。

然后这时候更新一下下一步最大范围，如果下一步最大范围已经到达终点，直接跳出循环。

var jump = function(nums) {
    let current = 0
    let next = 0
    let count = 0
    for(let i = 0;i<nums.length;i++){
        next = Math.max(nums[i]+i,next)
        if(i === current){
            if(current < nums.length-1){
                count ++
                current = next
                if(next >= nums.length-1){
                    break
                }
            }else break
        }
    }
    return count
    
};

复习

203.移除链表元素

细节错误：

忘记创建虚拟头节点

然后需要遍历到最后一个元素的前一个元素

然后还需要判断head是否为空，如果为空的话，就return一个空值

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        #循环这个链表
        if head is None:
            return 
        dummy = ListNode(0)
        dummy.next = head
        cur = dummy
        #这个细节有问题
        while cur.next is not None:
            if cur.next.val == val:
                cur.next = cur.next.next
            #这个细节有问题
            else:
                cur = cur.next
        return dummy.next

class ListNode(object):
    def __init__(self,val):
        self.val = val
        self.next = None
class MyLinkedList(object):
 
    def __init__(self):
        self.dummy_head = ListNode(0)
        self.size = 0
 
    def get(self, index):
        """
        :type index: int
        :rtype: int
        """
        #注意
        if index <0 or index >= self.size :
            return -1
        cur = self.dummy_head
        for i in range(index+1):
            cur = cur.next
        return cur.val
             
    def addAtHead(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.addAtIndex(0,val)
        
 
    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.addAtIndex(self.size,val)
        
 
    def addAtIndex(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        #注意
        if index > self.size:
            return
        cur = self.dummy_head
        newNode = ListNode(val)
        for i in range(index):
            cur = cur.next
        temp = cur.next
        cur.next = newNode
        newNode.next = temp 
        self.size += 1
        
            
        
 
    def deleteAtIndex(self, index):
        """
        :type index: int
        :rtype: None
        """
        #注意
        if index < 0 or index >= self.size:
            return
        cur = self.dummy_head
        for i in range(index):
            cur = cur.next
        cur.next = cur.next.next
        self.size -=1

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = None
        cur = head
        pre = dummy
        while cur is not None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre