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

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

简单到我不敢相信。

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

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

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

题解

class Solution:def maxProfit(self, prices: List[int]) -> int:result = 0for i in range(1, len(prices)):result += 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 Truei = 0while i <= cover:cover = max(i+nums[i],cover)if cover >= len(nums)-1:return Truei += 1return False

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

代码随想录

45.跳跃游戏II

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

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

class Solution:def jump(self, nums: List[int]) -> int:curdistance = 0count = 0nextdistance = 0for i in range(len(nums)-1):nextdistance = max(i+nums[i],nextdistance)if i == curdistance:curdistance = nextdistancecount +=1return 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 = headcur = dummy#这个细节有问题while cur.next is not None:if cur.next.val == val:cur.next = cur.next.next#这个细节有问题else:cur = cur.nextreturn dummy.next

 707. Design Linked List

插入节点的时候，记得创建temp变量来存储对应的节点

还有需要记得index 会不会溢出

class ListNode(object):def __init__(self,val):self.val = valself.next = None
class MyLinkedList(object):def __init__(self):self.dummy_head = ListNode(0)self.size = 0def get(self, index):""":type index: int:rtype: int"""#注意if index <0 or index >= self.size :return -1cur = self.dummy_headfor i in range(index+1):cur = cur.nextreturn cur.valdef 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:returncur = self.dummy_headnewNode = ListNode(val)for i in range(index):cur = cur.nexttemp = cur.nextcur.next = newNodenewNode.next = temp self.size += 1def deleteAtIndex(self, index):""":type index: int:rtype: None"""#注意if index < 0 or index >= self.size:returncur = self.dummy_headfor i in range(index):cur = cur.nextcur.next = cur.next.nextself.size -=1

206.反转链表

还比较简单，记得起来怎么写

class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:dummy = Nonecur = headpre = dummywhile cur is not None:temp = cur.nextcur.next = prepre = curcur = tempreturn pre