Leetcode热题100个人向题解

定义变量（长度，数组，辅助变量，返回变量等等）
特殊值判定（为空，长度为0，特定样例）直接返回
辅助函数
实现逻辑（循环：满足条件/不满足条件）
函数调用，函数返回

哈希

1.两数之和

暴力法，或者利用dict；

核心思路：d[num]与d[target-num]均存放在dict中，如果不存在就加入到字典

1
2
3
4
5
6
7
def twoSum(List:nums,int:target):
  dict = {}
  for i,num in enumerate(nums):
    if target-num in dict:
      return [d[target-num],i]
    d[num] = i
  return [] # 没找到的情况下

2.字母异位词分组

核心思路：异位词指排序后相同；因此可以以排序后的为key，字符串本身为value

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
  dict = {}
  for s in strs:
    key = ''.join(sorted(s)) # 不确定key直接sort()能不能行，应该是不行的
    if key not in dict:
      d[key] = [s]
    else:
      d[key].append(s)
   ans = []
   for _,v in dict.items():
    ans += v
   return ans

哈希表+简单排序

def quicksort(arr,start,end):
  # 快排，这里指数字；字符串可以通过ord或者其他方式进行排序
  if arr = 0 or start >= end:
    return
  target = arr[start]
  left = start
  right = end
  while left<right:
    # 从右往左，找到比target小的
    while left<right and arr[right] >= target:
      right -= 1
    #交换
    arr[left] = arr[right]
    #从左往右，找到比target大的
    while left<right and arr[left] < target:
      left += 1
    arr[right] = arr[left]
    #基准定位
    arr[left] = target
    quicksort(arr,start,l-1)
    quicksort(arr,l+1,end)

这里可以定义quicksort到字符串，一样的

3.最长连续子序列

循环查看nums[i]的前一位是否在nums里，如果存在说明本身不是开头，直接跳过

def longestConsecutive(self, nums: List[int]) -> int:
  dict = set(nums)
  ans = 0
  if nums == None or len(nums) == 0:
    return 0
  for num in nums:
    if num not in dict:
      # 是开头，长度设置为1，枚举+1在不在
      lenth = 1
      while num+1 in d:
        lenth += 1
        num +=1 
      ans = max(ans,lenth)
   return ans

双指针

4.移动0

不复制数组，将所有的0移动至数组末尾：一次遍历，记录非0个数，并放过去；剩下的补0

def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
    j = 0 # 记录非0个数
    for i in range(len(nums)):
      if nums[i]:
        nums[j] = nums[i]
        j +=1
    for i in range(j,len(nums)):
      nums[i] = 0

另外一种双指针

def moveZeroes(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    slow = 0  # 指向下一个非零元素的位置
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

5.盛水最多的容器

双指针+逼近，两个指针从两侧开始遍历，记录最大盛水值；留下高度高的，移动高度低的

def maxArea(self, height: List[int]) -> int:
  n = len(height)
  l,r = 0,len(height)-1
  ans = 0
  while l<r:
    contain = min(height[l],height[r])*(r-l+1)
    if height[l] < height[r]:
      l += 1
    else:
      r -= 1
    ans = max(ans,contain)
  return ans

6.三数之和

不限制时间，暴力解法；但是要优化：核心思想是找到不重复的nums[i],随后取l,r为i的后一个和n的前一个（即i后的两个端点），然后逼近。

满足条件：满足l小于r时，加入ilr和为0的元素；
指针移动：1. （外侧）nums[i] 和nums[i-1]相同，i后移 2. (内侧)：l累加，重复继续遍历；r累减，重复继续遍历；3.重复情况结束后，l += 1，r -=1 4. 当大于0时说明取大了，（nums已经排序了）r减少；反之l增加

def threeSum(self, nums: List[int]) -> List[List[int]]:
  nums.sort()
  n  = len(nums)
  res  = []
  if len(nums) < 3 or nums == None:
    return []
  for i in range(1,n):
    if (nums[i])>0:
      #特判
      return res
    if i > 0 and nums[i] == nums[i-1]:
      contine#去重
    else:
      l = i +1
      r = n - 1
    if nums[i] + nums[l] + nums[r] = 0:
      res.append([nums[i],nums[l],nums[r]])
      while l<r and nums[l] == nums[l+1]:
        l+=1
      while l<r and nums[r] == nums[r-1]:
        r-=1
      l += 1
      r -= 1
    elif nums[i]+nums[l]+nums[r] > 0:
      r -= 1
    else:
      l += 1
      
    return res

7.接雨水

暴力：首先是借助辅助空间存每个位置的左侧最高和右侧最高，i位置能接雨水的多少应该取决于两者的小值减去当前的高度

def trap(self, height: List[int]) -> int:
        left_ = []
        right_ = []
        max_l = 0
        max_r = 0
        for i in range(0,len(height)):
            max_l = max(height[i],max_l)
            left_.append(max_l)
        print(left_)
        for j in range(len(height)-1,-1,-1):
            max_r = max(height[j],max_r)
            right_.append(max_r)
        print(right_[::-1])
        water = 0
        for k in range(len(height)):
            water += min(left_[k],right_[::-1][k]) - height[k]
        return (water)

此外，优化算法应该是使用栈：按元素进栈，循环判断当前的height和stack栈顶的元素；
入栈：栈为空；或者没有比目前更高的height,或者栈顶出栈之后栈空
出栈：找到更高的高度，接住从栈内要出栈到目前位置中间的雨水：

计算：min(左，右)-bot * i-left-1 ；中间长度；面积

def trap(self, height: List[int]) -> int:
  ans = []
  n = len(height)
  stack = []
  for i in range(n):
    while stack and height[i] > height[stack[-1]]:
      #说明栈不空且当前值大于栈顶，更新bot
      bot = height[stack.pop()]
    if not stack:
      break
    rain = (i-stack[-1]-1)*min(height[stack[-1]],height[i])-bot
    ans += rain
  	#while else
    stack.append(i)
  return res

滑动窗口

滑动窗口应该有答题模板的

8.无重复的最长子串

思路：滑动窗口，考虑是子串而不是子序列，所以在内部进行循环；使用哈希表(dict)

def lengthOfLongestSubstring(self, s: str) -> int:
  ans = 0
  n = len(s)
  d = set()
  r = -1 #外层窗口
  # r起始放在-1是为了i=1时候r+1 = 0
  for i in range(n):
    if i!=0:
      #开始滑动了，因为一开始的遍历以i=1开始
      d.remove(s[i-1])
      while i<n and s[r+1] not in d:
        d.add(s[r+1])
        r += 1
        ans = max(ans,r-i+1)
        # 逻辑：给r递增，当不在d说明不重复，此时d可以更新，r可以累增，i到r之间是不重复的子串
    return ans

9.找到字符串中所有字母的异位词

思路有点不太正经：排序p，对于s的所有长度等于p的子串依次判断

sup = sorted(p)
        ans = []
        for i in range(len(s)-len(p)+1):
            # print(i)
            if sorted(s[i:i+len(p)]) == sup: # 这里用sorted不用set是因为异位的词有可能包含同样的字母 但是个数不一样
                ans.append(i)
        return ans

子串

10.和为K的子数组：

哈希表+前缀和

注意，前缀和的解法只提供了某个位置到当前为止的前缀和等于k，不能准确知道序列

思路：dict：{前缀和：出现的次数}；默认preSum = 0

遍历数组，更新前缀和，如果出现在preSum - k 出现在d中，那就增加次数ans += d[preSum - k]；最后更新当前前缀和

def subarraySum(self, nums: List[int], k: int) -> int:
	hash1 = collection.defaultdict(int)
  preSum = 0
  ans = 0
  hash[0] = 1
  for num in nums:
    preSum += num
    if preSum - k in hash1:
      ans += 1
    hash1[preSum] += 1
  
  return ans

11.滑动窗口最大值

思路：双端队列，栈顶留最大值；ans每次增加的时候增加deq[0]的元素

左出栈：栈不为空且窗口越界

右出栈：新加入的nums[i]大于栈内的栈顶元素，出栈直到只剩下比nums[i]大的值

入栈：出完栈肯定要入的

添加元素：当前下标大于k-1（即形成窗口的时候）开始向ans内添加

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
  n = len(nums)
  deque = collections.deque()
  ans = []
 
  if nums == None or len(nums)==0:
    return 
  
  for i in range(n):
    if deque and deque[-1] > i - k +1:
      deque.popleft()
    while deque and nums[deque[-1]] < nums[i]:
      deque.pop()
    deque.append(i)
    
    if i > i -k +1:
      ans.append(nums[deque[0])
  return ans

12.最小覆盖子串

普通数组

dp偏多

13.最大子数组和

思路：dp，dp[i]表示前i的最大和

dp[i] = dp[i-1] + nums[i]

如果dp[i-1] <0说明nums[i]最大（毕竟加了一个负数）

如果dp[i-1]>0说明最大值应该加上nums[i]本身

def maxSubArray(self, nums: List[int]) -> int:
  n = len(nums)
  dp = [0] * n
  
  if n == 0:
    return 0
  if n == 1:
    return nums[0]
  
  dp[0] = nums[0]
  for i in range(1,n):
    if dp[i-1] > 0:
      dp[i] = dp[i-1] + nums[i]
    else:
      dp[i] = nums[i]
  return max(dp)

14. 合并区间

思路：

先排序

放入第一个区间，递归修改前一个区间；如果重叠：区间的最小值等于相邻区间的最小值，最大值为相邻的最大值；否则直接加入

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
  n = len(intervals)
  ans = []
  intervals.sort(key = lambda x:x[0])
  if n== 1:
     return intervals
  for i in range(n):
    if not ans:
      ans.append(intervals[i])
    else:
      start_bef,end_bef = ans[-1][0],ans[-1][1]
      if intervals[i][0] < end_bef:
        ans[-1][0] = min(intervals[i][0],ans[-1][0])
        ans[-1][1] = max(intervals[-1][1],ans[-1][1])
      else:
        ans.append(intervals[i])
  return ans

15. 轮转数组

思路：右旋转k，相当于后k个拼接到前（n-k）个

n = len(nums)
       step = k % len(nums)
       # 右旋转k，相当于后k个拼接到前（n-k）个
       t = nums[0-step:]+nums[:n-step]
       print(nums,t,k)
       for i in range(len(nums)):
           nums[i] = t[i]

16. 除自身以外的乘积

思路：开辟两个数组：前缀积和后缀积，遍历i时直接将i位置的前缀积和后缀积相乘

def productExceptSelf(self, nums: List[int]) -> List[int]:
   n = len(nums)
   ans = []
   former_ = [1] * n
   latter_ = [1] * n
   for i in range(1,n):
     former_[i] = former_[i-1]*nums[i-1]
   for i in range(1,n):
     latter_[i] = latter_[i+1]*nums[i+1]
   
   for j in range(n):
     ans.append(former_[j]*latter_[j])
   return ans

17. 缺失的第一个正数

思路：首先将所有负数都标记为大于n的数；其次，如果num在n之内，就将原数组的num-1位置标记为负数

返回第一个正数位置的下标+1

def firstMissingPositive(self, nums: List[int]) -> int:
  n = len(nums)
  for i in range(n):
    if nums[i] < 0:
      nums[i] = n+1
  for i in range(n):
    num = abs(nums[i])
    if num < n:
      nums[num-1] = -abs(nums[num-1]) #数组本身做个哈希，处理重复情况；使用abs为了防止负数
  for i in range(n):
    if nums[i]>0:
      return i+1
  return n+1

矩阵

18. 矩阵置0

思路：直接模拟，用两个栈保存x和y为0的坐标，然后循环遍历两个栈的元素使对应的行/列变为0

def setZeroes(self, matrix: List[List[int]]) -> None:
  m,n = len(matrix),len(matrix[0])
  x_sup = []
  y_sup = []
  for i in range(m):
    for j in range(n):
      if matrix[i][j] == 0:
        x_sup.append(i)
        y_sup.append(j)
  while x_sup and y_sup:
    x = x_sup.pop()
    y = y_sup.pop()
    
    for i in range(n):
      matrix[x][i] = 0
    for j in range(m):
      matrix[j][y] = 0

19. 螺旋矩阵

思路：依然是模拟，就规定上下左右四个变量，遍历时注意逆序的两个：从右下到坐下和从左下到左上

注意找每个不变量，以及对应的越界条件

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
  top,bot,left,right = 0,len(matrix),0,len(matrix[0])-1 # bot是行数，right是列数
  res = []
  if not matrix:
    return
  while True:
    for i in range(l,r+1):
      res.append(matrix[top][i])
    top += 1
    if top > bot:
      break
    for i in range(top,bot+1):
      res.append(matrix[i][right])
    right -= 1
    if right < left:
      break
    for i in range(right,left-1,-1):
      res.append(matrix[bot][i])
    bot -= 1
    if bot < top:
      break
    for i in range(bot,top-1,-1):
      res.append(matrix[i][left])
    left +=1
    if left > right:
      break
  return res

20. 旋转图像

思路：旋转图像等于转置之后行转置

def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 旋转90 = 对称+行翻转
        m,n = len(matrix),len(matrix[0])
        for i in range(m):
            for j in range(i+1,n):
                matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]
        for line in matrix:
            line = line.reverse()

21. 搜索二维矩阵II

理论上可以使用for line的做法，下面这个做法作为优化方案：

排除法吧还是叫：从右上角开始找：如果右上角元素比target小，说明同一行都比他小，遍历下一行；如果右上角比target大，说明最后一列都大于target，列往左

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
  i,j = 0,len(matrix[0])-1
  m,n = len(matrix),len(matrix[0])
  
  while i<m and j >=0:
    if matrix[i][j] < target:
      i += 1
    elif matrix[i][j] > target:
      j -= 1
    else:
      return True
  return False

链表

链表题：

可以设置一些变量
dummy节点
快慢指针

22. 相交链表

思路：互相走对方的，如果相交应该最后会相遇，反推一定在相交节点相遇

代码：定义两个链表，随后进入循环->a=b时候跳出->当某一个为空时候走另一个链表

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
      a = headA
      b = headB
      
      while a!=b:
        if a == None:
          a = headB
        else:
          a = a.next
        if b == None:
          b = headA
        else:
          b = b.next
      # 跳出循环，此时a=b
      return a

23. 翻转链表

经典翻转了，挂链

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
  pre = None
  cur = head
  while cur:
    temp = cur.next
    cur.next = pre #拉断
    pre = cur #重组
    cur = temp
  return pre

24. 回文链表

思路：快慢指针找中间，然后翻转后面，依次比较

def isPalindrome(self, head: Optional[ListNode]) -> bool:
   fast = head
   slow = head
   
   while fast and fast.next:
     slow = slow.next
     fast = fast.next.next
   #此时slow是中间
   m = slow
   pre = None
   while m:
     temp = m.next
     m.next = pre
     pre = m
     m = temp
    
   while pre:
     if pre.val != head.val:
       return False
   return True

25. 环形链表

思路：快慢指针判相遇

def hasCycle(self, head: ListNode) -> bool:
  slow = head
  fast = head
  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if fast is slow:
      #判定指针 不能用等于
      return True
   return False

26. 环形链表II

思路：这个链表要求返回入口节点先判相遇，再相遇节点之后从头开始，再次相遇就是相遇节点

if head == None:
            return None
        slow = head
        fast = head
        while slow.next and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            #快慢指针的plus，如果存在环，那么slow到相遇点=起始点到相遇点（两者在相遇点相遇）
            if slow is fast:
                n = head
                while n is not slow:
                    n = n.next
                    slow = slow.next
                return n
        return None

27. 合并两个有序链表

思路：先特判（其中有list为空），然后定义哑节点（dummy）令cur = dummy

在两个链表都有值的情况下（while）判断两个list的val值，用cur来连接其中较小的

然后剩下的补到cur

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
  dummy = ListNode(-1)
  cur = dummy
  if list1 == None:
    return list2
  if list2 == None:
    return list1
  while list1 and list2:
    if list1.val < list2.val:
      cur.next = list1
      list1 = list1.next
    else:
      cur.next = list2
      list2 = list2.next
    cur = cur.next
  if list1:
    cur.next = list1
  if list2:
    cur.next = list2
  return dummy.next # cur操作dummy链表

28. 两数相加

思路：链表模拟题，思路是创建进位carry，在计算时候依次向后遍历，加carry之后继续计算新的carry；用dummy来保存相加之后的节点，用cur来操作链表

def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
  carry = 0
  dummy = ListNode(-1)
  cur = dummy
  # 进入累加的循环
  while l1 or l2 or carry : 
    temp = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
    val = temp % 10
    carry = temp //10
    cur.next = ListNode(val)
    cur = cur.next
    if l1:
      l1 = l1.next
    if l2:
      l2 = l2.next
  return dummy.next

29. 删除链表的倒数第N个节点

思路：快慢指针，快指针先走N步，然后同步向后，快指针到末尾时候慢指针正好到倒数第N个节点，直接删除接到下下个

注意点：返回的是头结点，还是要用dummy来处理；快慢指针可以在dummy的基础上进行操作（因为返回的是

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
  dummy = ListNode(0)
  dummy.next = head
  fast = dummy
  slow = dummy
  for _ in range(n):
    if fast.next:
    	fast = fast.next
    else:
      return head
  while fast and fast.next:
    slow = slow.fast
    fast = fast.next
  slow = slow.next.next
  return dummy.next

30. 两两交换链表中的节点

思路：创建虚拟头结点dummy，令prev = dummy，操作prev

def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
  dummy = ListNode(0)
  dummy.next = head
  
  prev = dummy
  while prev.next and prev.next.next:
    # 分别对应第一个和第二个
    node1 = prev.next
    node2 = prev.next.next
    
    prev.next = node2 #node2提前
    node1.next = node2.next# 接上1->3
    node2.next = node1 # 接上node1
    
    prev = node1#移动到第三个
  return dummy.next

31. K个一组翻转链表

32. 随机链表的复制

# 这个题明天再看
 def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        p=head
        while p:
            new_node=Node(p.val,None,None)
            new_node.next=p.next
            p.next=new_node
            p=new_node.next
        p=head
        while p:
            if p.random:
                p.next.random=p.random.next
            p=p.next.next
        p=head
        dumpnode=Node(-1,None,None)
        cur=dumpnode
        while p:
            cur.next=p.next
            cur=cur.next
            p=p.next.next
        return dumpnode.next

33. 排序链表

思路：归并排序+合并有序链表

def sortList(self, head: ListNode) -> ListNode:
   return sortFunc(head, None)
 
 def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
   if not head:
     return head
   if head.next = tail:
     head.next = None #分离链表
     return head
   slow = fast = head
   while fast != tail:
     fast = fast.next.next
     slow = slow.next
   mid = slow
   return merge(sortFunc(head,mid),sortFunc(mid,tail))
 def merge(head1:ListNode,head2:ListNode):
   dummyHead = ListNode(0)
   # 以下是合并有序的代码
   cur,l1,l2 = dummyHead,head1,head2
   while l1 and l2:
     if l1.val < l2.val:
       cur.next = l1
       l1 = l1.next
     else:
       cur.next = l2
       l2 = l2.next
     if l1:
       cur.next = l1
     if l2:
       cur.next = l2
     return dummyHead.next

34. 合并K个升序链表

思路堆排序小顶堆排序:使用优先队列

总结：和两个一样，之前加入了一些小根堆的建立和优先队列的初始化过程

注意点：pq.put是元组(),需要有两层嵌套

lists要注意移动链表指向

from queue import PriorityQueue
def mergeKLists(self , lists: List[ListNode]) -> ListNode:
  n = len(lists)
  pq = PriorityQueue()
  for i in range(n):
    if lists[i] != None:
      pq.put((val,i))
      lists[i] = lists[i].next
  dummy = ListNode(-1)
  cur = dummy
  while not pq.empty():
    val,index = pq.get()
    cur.next = ListNode(val)
    cur = cur.next
    if lists[index] != None:
      pq.put((val,index)
      lists[index] = lists[index].next
  return dummy.next

35. LRU缓存

思路：哈希表+双向链表

哈希表用来定位，找出缓存在位置；双向链表是记录移动的位置的数据结构，链头是最近使用的

# 我真能自己实现双向LINK吗
class LRUCache(collections.OrderedDict):

    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity


    def get(self, key: int) -> int:
        if key not in self:
            return -1
        self.move_to_end(key)
        return self[key]

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)

二叉树

二叉树以递归、bfs（层序）、栈为主，注意实现；

其中递归主要理解，栈模拟作为思路可以在每一个总结

36. 二叉树的中序遍历

正常中序遍历，这里可能需要说的是不带self的写法（函数卸载里面）

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  self.root = root # 不能少
  res=[]
  def mid_order(root):
    if not root:
      return 
    mid_order(root.left)
    res.append(root.val)
    mid_order(root.left)
    return res
  ans = mid_order(root)
  return ans
#递归的修改位置即为对应的

栈模拟（前中后序通用）

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  res = []
  stack = []
  cur  = root
 # 思路：cur用来定位叶子节点；
 # 中序是左 根 右 因此定位到左叶子直接弹出 cur指向right放在ans取值之后能保证根节点在右子树之前放入
  while stack or cur:
    while cur:
      stack.append(cur)
      cur = cur.left
    cur = stack.pop()
    res.append(cur.val)
    cur = cur.right
  return res

这个模板的前序和后序直接给出:

# 前序，先放入val值 中左右
while stack or cur:
  while cur:
    res.append(cur.val)
    stack.append(cur)
    cur = cur.left
  cur = stack.pop()
  cur = cur.right
return res

# 后序，先放入val值 左右中 -> 中右左
while stack or cur:
  while cur:
    res.append(cur.val)
    stack.append(cur)
    cur = cur.right
  cur = stack.pop()
  cur = cur.left
return res[::-1]

37. 二叉树的最大深度

最大深度指的是左右节点数最大值加+1

def maxDepth(self, root: Optional[TreeNode]) -> int:
  # 递归
  if not root:
    return 0
  return (self.maxDepth(root.left),self.maxDepth(root.right))+1

# 栈模拟，这里的模板是bfs的思想
def maxDepth(self, root: Optional[TreeNode]) -> int:
  if not root:
    return 0
  stack = [root]
  res = 0
  while stack:
    temp = []
    for node in stack:
      if node.left:
        temp.append(node.left)
      if node.right:
        temp.append(node.right)
    stack = temp # 换栈
    res += 1
    # res 添加的条件stack每进入循环一次（说明栈内始终有值）
  return res

38. 翻转二叉树

分为递归和栈

递归思路就是临时变量存左右，然后交换

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
  if not root:
    return 
  left = self.invertTree(root.left)
  right = self.invertTree(root.right)
  # 更改
  self.left, self.right = right,left
  
  return root

迭代思路使用栈，思路：对于每一层的node节点，交换其左右

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
  if not root:
    return 
  stack = [root]
  # 这里不是遍历，也不是计算某个值，所以出栈+修改
  # 如果是计算深度、直径等，要有对应的临时变量来保存和更新
  while stack:
    node = stack.pop()
    if node.left:
      stack.append(node.left)
    if node.right:
      stack.append(node.right)
    node.right,node.left = node.left,node.right
  return root
# 从上到下的翻转

39. 对称二叉树

对称二叉树的核心左右子树对应的值和另一侧的左右子树的位置恰好相反

思路：借助辅助函数递归判断

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
  return is_mirror(root.left,root.right)
  def is_mirror(lroot,rroot):
    if not lroot and not rroot:
      return True
    if not lroot or not rroot:
      return False
    if lroot.val != rroot.val:
      return False
    return is_mirror(lroot.left,rroot.right) and is_mirror(lroot.right,rroot.left)

使用栈模拟：

思路：成对放入左右子树，判断是否相同：

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
  if not root:
    return 
  q = deque()#双端队列
  q.append([(root.left,root.right)])
  while q:
    l,r = q.popleft()#弹出节点
    if not left and not right:
      continue
    if not left or not right or l.val != r.val:
      return False
    q.append((left.left,right.right))
    q.append((left.right,right.left))
  return True

40. 二叉树的直径

思路因为直径可以不包含根节点，所以需要维护一个最大值（之前的左右节点高度和以及当前节点的）

def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
  self.ans = 0
  def dfs(node):
    if not node:
      return 0
    left = dfs(node.left)
    right = dfs(node.right)
    self.ans = max(self.ans,left+right)
    return max(left,right)+1
  dfs(root)
  return self.ans
# 稍微修改就得到了二叉树的最大深度：去掉lr的判断，直接返回max(,) + 1

41. 二叉树的层序遍历

标准bfs +（双端队列）

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
   if not root:
     return 
   q = deque()
   res = []
   
   q.append(root)
   while q:
     #遍历需要临时变量来存储没层的值，如果返回不要求可以不加
     temp=[]
     for _ in range(len(q)):
       # 这里是为了满足按q的长度添加
       node = q.popleft()
       # 先暂时将当层的存到temp
       temp.append(node.val)
       if node.left:
         q.append(node.left)
       if node.right:
         q.append(node.right)
       res.append(temp)
     return ans

可以看出，使用栈/双端队列进行二叉树操作的相关实现基本都是围绕着BFS进行的，包括前面的38 翻转二叉树 ，39 对称二叉树和 37 最大深度。核心思想在于实现目标能否按照层序遍历的思想来。如果能层序遍历得到答案，这套模板基本使用

42. 将有序数组转化为二叉搜索树

思路：递归构建，因为给定了已排序的数组，按照中序遍历思想左中右找到中间节点，在两侧递归调用放入

def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
  def dfs(left,right):
    if left == right:
      return None #退出条件，l=r表示区间长度为0
    m = (left + right) // 2
    return TreeNode(nums[m],dfs(left,m),dfs(m+1,right))# val,left,right
  return dfs(0,len(nums))

43. 验证二叉搜索树

思路：二叉搜索树表示左边小于中间小于右边，递归调用，当满足dfs终止条件直接返回False

def isValidBST(self, root: Optional[TreeNode],left = -inf , right = inf) -> bool:
  if root == None:
    return True #空树是BST
  mid = root.val
  return left < mid < right and isValidBST(root.left,left,mid) and isValidBST(root.right,mid,right)

44. 二叉搜索树的第K小元素

思路：

中序遍历，然后返回k-1位置的元素
dfs，往左走然后判断，走一次k-=1, 判断k 然后往右走

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
  def mid_order(root):
    stack = []
    ans = []
    cur = root
    if not root:
      return 
    while stack or cur:#用or
      while cur:
        stack.append(cur)
        cur = cur.next
      cur = stack.pop()
      ans.append(cur.val)
      cur = cur.next
    return ans
  return ans[k-1]

或者使用dfs

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
  def dfs(root):
    if not root:
      return 
    if root.left:
      dfs(root.left)
    if k == 0:
      return 
    k -= 1
    if k == 0:
      self.ans = root.val
    dfs(root.right)
  
  self.k = k
  dfs(root)
  return self.ans

45. 二叉树的右视图

很明显了，层序遍历的加强版，即只保留每一层的最右侧

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
  if not root:
    return
  q = deque()
  q.append(root)
  res = []
  while q:
    #temp = [] 屏蔽掉是因为此题每一层只输出一个节点
    for i in range(len(q)):
      node = q.popleft()
      if i == len(q) - 1:
        res.append(node.val)
      if node.left:
        q.append(node.left)
      if node.right:
        q.append(node.right)
  return res

46. 二叉树展开为链表

题目是都放在右边

思路：暂存右节点之后，循环调用flatten的左子树和右子树

def flatten(self, root: Optional[TreeNode]) -> None:
  if not root:
    return 
  right = root.right # 
  self.flatten(root.left)
  self.flatten(root.right)
  root.left = None #左子树指向None
  root.right = root.left#右子树指向左子树
  
  node = root
  while node.right:
    node = node.right
  node.right = right#右子树开始
    """
  先扁平化左子树。
  再扁平化右子树。
  将左子树连接到当前节点的右边，左子树的左指针设为 None。
  找到新的右子树的最右节点，将原来的右子树连接到这个最右节点的右边。
  并不是真的链表，就是right变成了next，左子树指向null
  """

47. 前序和中序实现二叉树

思路：二叉树在中序能够定位左子树成员，在前序能够定位根节点

对于同一棵树：前序[0]是根节点，前序[1]是左子树的根节点

根据在前序中找到中序的索引，即可划分为两个子树

def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
  def dfs(inorder,preorder):
    x = preorder[0]
    #x是根节点，每次都是对应子树的根
    node = TreeNode(x)
    idx = inorder.index(x)
    #inx是中序的
    left = inorder[:idx]
    right = inorder[idx+1:]
    node.left = dfs(left) if left else None
    node.right = dfs(right) if right else None
    return node
  if not preorder or nor inorder:
    return
  retuen dfs(inorder,preorder)

48. 路径总和III

路径总和三个一起放过来吧：

路径总和1：根节点到叶子结点的路径满足和等于target；满足就返回true

思路：我习惯记录和为target的路径，使用dfs

首先将根节点入栈，然后更新target = target-val值，通过判断哪target的值来确定path的添加和结束

注意点1：考虑到是到叶子结点，所以在判断target时候需要额外判断是否具有左右子树

然后递归到左右子树,path出栈（避免重复）

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
  if not root:
    return 
  path = []
  res = []
  def dfs(root,targetSum):
    if not root:
      return 
    val = root.val
    path.append(val)
    targetSum -= val
    if targetSum == 0 and not root.left and not root.right:
      res.append(path[:])
    dfs(root.left,targetSum)
    dfs(root.right,targetSum)
    path.pop()#不能忘记出栈
  dfs(root,targetSum)
  if res == []:
    return False
  return True

路径总和2：找出所有路径，从根到叶子节点

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
  res = []
  path = []
  if not root:
    return 
  def dfs(root,tar):
    if not root:
      return
    val = root.val
    path.append(val)
    tar -= val
    if not root.left and not root.right and tar == 0:
      res.append(path[:])
    dfs(root.left,tar)
    dfs(root.right,tar)
    
  dfs(root,targetSum)
  return res

路径总和3：（本题）不一定是到叶子，也不一定从根节点开始，存在即可

思路：因为没有叶子节点的限制，并且需要遍历所有节点：

考虑辅助函数，维护变量res（表示以root为根节点的的满足左右子树和为target的数量）

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
   def dfs(root,target):
     if not root:
       return
     res = 0
     if root.val == target:
       res += 1
     # 判断左右子树,因为当前节点肯定有本身，所以target要减去val
     res += dfs(root.left,target-root.val)
     res += dfs(root.right,target-root.val)
     
     return ret
   if not root:
     return 0
   res = dfs(root,targetSum)
   res += self.dfs(root.left,targetSum)
   res += self.dfs(root.right,targetSum)
   return res

49. 二叉树的最近公共祖先

分类讨论：首先递归判断pq属于左侧还是右侧，根据l和r的情况进行判断

1.如果l和r都没有pq（即l，r都是空），说明左右边都没有pq，返回空

2.如果l和r都不为空，说明两侧都有，此时返回根节点

如果出现在一侧，那么说明该侧根节点是祖先

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
  if not root or p == root or q== root:
    return root
  left = self.lowestCommonAncestor(root.left,p,q)
  right = self.lowestCommonAncestor(root.right,p,q)
  
  if not left:
    return right
  if not right:
    return left
  if not left and not right:
    return root

50. 二叉树中的最大路径和

定义maxGain为节点贡献值，一个思路是：定义并维护最大路径和变量，返回该节点的最大贡献值等于节点贡献值加上左右子树大的贡献值

def maxPathSum(self, root: Optional[TreeNode]) -> int:
  # self.maxSum = 0
  def maxGain(root):
    if not root:
      return 0
    left = maxGain(maxGain(root.left),0)
    right = maxGain(maxGain(root.right),0)
    path_max = node.val + left + right
    self.maxSum = max(path_max,self.maxSum)
    return root.val + max(node.left,root.right)
  maxGain(root)
  return self.maxSum

图

图的遍历一般是bfs，结合矩阵；

主要是回溯

51. 岛屿数量

题干是介绍1和0，被0围绕的1的个数（相邻1算一个）

思路：dfs向四个方向遍历，如果发现1就从此处开始dfs，随后删除岛屿（置0）

图bfs：

base case
操作
遍历

def numIslands(self, grid: List[List[str]]) -> int:
  m = len(grid)
  n = len(grid[0])
  def dfs(x,y):
    # 一定要先写return 是dfs的base case（最小递归）
    if x < 0 or x > m or y < 0 or y > n or grid[x][y] == '0':
        return
    grid[x][y] = '0'
    dfs(x-1,y)
    dfs(x+1,y)
    dfs(x,y-1)
    dfs(x,y+1)
  count = 0
  for i in range(m):
    for j in range(n):
      if grid[i][j] == '1':
        dfs(i,j)
        count+=1
        
  return count

52. 腐烂的橘子

这个题显然是和岛屿不一样的，这个题是扩散模型的bfs

思路：使用队列

node = q.pop()

			for node:

					if 	isNotTraverse:

									push

具体：遍历，记录腐烂橘子的坐标和新鲜橘子的个数

外层循环：min +=1

内层循环：创建队列，循环队列元素，更改橘子状态，维护队列（开始的出队和最后的入队）

def orangesRotting(self, grid: List[List[int]]) -> int:
  m = len(grid)
  n = len(grid[0])
  q = queue()
  
  count = 0
  for i in range(m):
    for j in range(n):
      if grid[i][j] == 1:
        count += 1
      elif grid[i][j] == 2:
        q.append((i,j))
  # q是包含腐烂橘子坐标的序列
  
  minute= 0
  while count >0 and len(q)>0:
    minute += 1
    n = len(q)
    for i in range(n):
      x,y = q.pop(0)
      if isNotBeyong and grid[] == 1:
        grid[x_][y_] = 2
        minute -=1
        q.append((x_,y_))
      
   if count > 0:
   		return -1
   return minute

53. 课程表

好像是个拓扑排序

def canFinish(numCourses, prerequisites):
  graph = {}
  for course,pre in prerequisites:
    if courese not in graph:
      graph[course] = []
    graph[course] .append(pre)
  visted = set()
  def dfs(course):
    if course in visited:#课程前置有重复了
      return False#有环
    visited.add(course)
    if course in graph:
      for i pre in graph[course]:
        if not dfs(pre):
          return False
    visited.remove(course)#全部都能修完
    return True
  for course in range(numCourses):
    if not dfs(course):
      return False
    return True

54. 前缀树

先不看了

回溯

55. 全排列

思路是取出每一个位置的元素，然后递归找其他位置的全排列之后拼接

def permute(self, nums: List[int]) -> List[List[int]]:
   if len(nums) == 1:
     return [nums]
   ans  = []
   for i in range(len(nums)):
     cur = nums[i]
     rest = nums[:i]+nums[i+1:]
     all_rest = self.permute(rest)
     
     for j in all_rest:
       ans.append([cur] + j)
   return ans

56. 子集

返回所有可能的子集

这里有一种有趣的做法，按照二进制来注意右移和与的使用

def subsets(self, nums: List[int]) -> List[List[int]]:
  n  = len(nums)
  ans = []
  temp = []
  for i in range(2**n):
    for j in range(n):
      if (i>>j)&1: #依次判断j位是不是1
        temp.append(nums[j])
    ans.append(temp)
  return ans

57. 电话号码的数字组合

使用队列（题目要求返回数字对应字母的全部组合）

思路：

1.将输入的数字所代表的每一个都入列；

2.将出队的和第二个数字代表的每一个元素组合后入队

……

# 2 3
# a b c 
# ad ae af bd be bf cd ce cf
def letterCombinations(self, digits: str) -> List[str]:
  d ={"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
  if not digits:
    return []
  q = ['']
  for digit in digits:
    for _ in range(len(q)):
      temp = q.pop(0)
      for letter in d[int(digit)]:
        q.append(temp+letter)
  return q
#

58. 组合总和

回溯经典题

思路

res = []
Def backtrack():满足结束条件加入路径；return
满足提前返回的条件；return
对于选择列表内的每个选择: 选；然后更新backtrack路径；撤销选择

# 和为target的数组选其中的元素，返回所有不同组合
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
  if not candidates:
    return []
  res = []
  n = len(candidates)
  def bt(i,tempsum,templist):
    if tempsum == target:
      res.append(templist)
      return
    if temp>target:
      return
    for j in range(len(n)):
      # 挨个选择j
      bt(i,tempsum+candidates[j],templist+[candidates[j]])
      # 剪枝的提前返回相当于撤销
    bt(0,0,[])
    return res

59. 括号生成

给定括号的对数，生成可能的有效的括号组合

思路：

开始提供n个左右括号，base case：l ==0,说明已经左括号用完，只需要添加足够的右括号来闭合，然后添加到res中
递归：分为case1 l=r 此时左括号右括号剩余数量相同，为了闭合只能先添加左括号
Case2 l不等于r 此时左右都可以，但是要保证剩下的右括号大于左括号的数量

def generateParenthesis(self, n: int) -> List[str]:
  res = []
  # bt,start序列，剩余的括号l数量，剩余的括号r数量
  def bt(s,l,r):
    if l == 0:
      res.append(s+')'*r)
      return
    if l == r:
      # 剩余的左等于右，只能先左括号
      gene(s+"(",l-1,r)#左括号少一个
    if l!=r:
      gene(s+"(",l-1,r)#左括号少一个
      gene(s+")",l,r-1)#右括号少一个
  bt("",n,n)
  
  return res

60. 单词搜索

好像是个很经典的回溯

定义dfs的函数入参：dfs(i,j,k) 表示在i,j位置匹配到k；在每一个位置dfs（四个方向）

basecase：数组越界，i,j位置不等于word[k] 或者已经已经遍历到k的字符

def exist(self, board: List[List[str]], word: str) -> bool:
  m,n = len(board),len(board[0])
  def dfs(i,j,k):
    #basecase
    if not 0<= i < m or not 0 <= j <= n or board[i][j] != word[k]:
      return False
    else:
      if k == len(word) -1:
        return True
    #开始dfs
    board[i][j] = ''#已访问的标记
    res = dfs(i-1,j,k+1) or dfs(i,j-1,k+1) or dfs(i+1,j,k+1) or dfs(i,j+1,k+1)
    board[i][j] = word[k]#恢复原来的
    return res

for i in range(m):
  for j in range(n):
    if dfs(i,j,0):
      return True
return True

61. 分割回文串

分割和回文子串的区别是，分割要求加能够恢复为原来的字符串；而回文子串则仅需要时子串就可以

这题和N皇后有点像的，借助judge判断回文，通过judge的结果选择是否添加结果

def partition(self, s: str) -> List[List[str]]:
    # 辅助函数
    def judge(s):
      # 判断s是不是回文
      return s==s[::-1]
    ans = []
    def bt(start,path):
      if start == len(s):
        ans.append(path[:])
        return
      for end in range(start,len(s)):
        if judge(s[start:end+1]):
          path.append(s[start:end+1)
          bt(end+1,path)
          path.pop()#撤销
    bt(0,[])
    return res

62. N 皇后

核心思路和分割回文串差不多，也是辅助函数isvaild来判断能不能放皇后

def solveNQueens(self, n: int) -> List[List[str]]:
  t = [['.' for _ in range(n)] for _ in range(n)]
  # python不能修改字符串，在拼接时候可以''.join
  def isvaild(row,col):
    for i in range(row):
      if chess[i] == col or abs(chess[i]-col) == row-1:
        return False
    return True
  #bt
  def bt(row):
    #base case
    if row==n:
      tmp = []
      for i in range(n):
        tmp.append(''.join(t[i]))
      res.append(tmp)
      return
    for col in range(n):
      #放皇后
      if isvaild(row,col):
        chess[i] = col
        t[row][col] = 'Q'#操作
        bt(row+1)
        t[row][col] = '.'#撤销
     result = []
    chess = [-1] * n
    bt(0)
    return result

二分查找

写在前面：

二分乍一看都会写，但是细节还是很麻烦的：

区间问题

区间包括常见的双闭区间，双开区间，左闭右开区间；

从取值的角度来说，区间的开闭指的是能否以下标的形式取到边界值，如果能，那就是闭区间；反之是开区间。

以一个长度为n的数组nums来说，双闭区间就是[0,n-1],双开区间就是(-1,n),左闭右开就是[0,n)
while进入时候的判断

这里结合开闭区间进行不同情况的讨论，总之是不缺元素的遍历完

[0,n)以左闭右开为例，while l<r 的结束条件是l=r,此时区间没有元素；

如果是while l<=r,结束条件是l=r+1,也可以正常退出，但是会多比较

当然，双闭区间[0,n-1]同理，l<r作为循环条件，当l=r时候会产生区间存在值的情况，所以闭区间的判断应该是<=
不符合区间时候的变更上下界问题

这里仍然结合开闭区间，同时判断m是否需要包含在区间内

对于有些写法，如果 nums[m] > target 或者小于target时，要找不包含m的下一个区间；

对于有序数组，target小于m表示在左侧，更改右侧边界为m，需要+1吗？因为m不是要找的target值，并且右侧是开区间，所以直接令r = m即可；

（这也就是为什么左闭区间要设置为m+1）

63. 搜索插入位置

二分查找标准题目

def searchInsert(self, nums: List[int], target: int) -> int:
  n = len(nums)
  l,r = -1,n-1
  
  while l+1 < r:
    m = (r+l) // 2
    if nums[m] < target:
      l = m
    else:
      r = m
    return r

开区间两侧为-1，n，闭区间两侧为0，n-1, 左闭区右开为0，n
更新边界对于l和m的情况：闭区间对应m+1/m-1；开区间直接为m（因为闭区间可能会取到边界值），开区间不会
结束时返回的下标：双开区间是r，双闭区间都可以（l==r），左闭右开是l

64. 搜索二维矩阵

二维判断+二分查找

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        
        m = len(matrix)
        n = len(matrix[0])
        print(m,n)
        for line in range(m):
            if matrix[line][n-1] == target:
                return True
            elif matrix[line][n-1] < target:
                # 说明在不在本行，可能在下一行
                continue
            else:
              # 左闭右开区间
                l,r = 0,n
                while l < r:
                    mid = (l+r) // 2
                    if matrix[line][mid] < target:
                        l = mid + 1
                    else:
                        r = mid
                if l < n and matrix[line][l] == target:  # 判断是否找到目标值
                    return True
        return False

65. 在排序数组中查找元素的第一个和最后一个位置

（O(logN))

思路：二分改进，传统二分在找到目标之后直接返回下标；改进的话就仍然需要向左或者向右（可以写俩函数）

def searchRange(self, nums: List[int], target: int) -> List[int]:
  l = searchLeft(nums)
  r = searchLeft(nums)
  if len(nums) == 0 or nums[0] > target or nums[-1] < target:
    return [-1,-1]
  def searchLeft(nums):
    l,r = 0,len(nums)-1
    while l <= r:
      m = (r + l)//2
      if nums[m] == target:
        r = m-1
      elif nums[m] > target:
        r = m -1
      else:
        l = m+1
      if nums[l] == target:
        return l
      return -1
    def searchRight(nums):
      l,r = 0,len(nums)-1
      while l <= r:
        m = (r + l)//2
        if nums[m] == target:
          l = m+1
        elif nums[m] > target:
          r = m -1
        else:
          l = m+1
        if nums[r] == targetr
          return r
        return -1

66. 搜索旋转排序数组

旋转数组：指的是从某个开始整体放到前面

比如[1,2,3,4,5] 旋转后变成 [4,5,1,2,3]

思路：二分的变种,因为数组部分有序，且被分为两个部分，所以寻找目标值target可以这样二分：

找到旋转数组的最小值，将列表分为两个部分
在两个部分分别进行二分

def search(self, nums: List[int], target: int) -> int: 
  #1. 旋转数组的最小值
  def findMin(self,nums:List[int]) -> int:
    n = len(nums)
    l,r = 0,n
    while l < r:
      m = (l + r) // 2
      if nums[m] < nums[-1]:
        # 中间值小于最后值，最小值应该在前面
        r = m 
       else:
        # 中间值大于最后，一定在后面
        l = m + 1
     return l
  def partseek(l,r,target):
    n =  len(nums)
    l,r = 0,n
    while l < r:
      m = (l + r )//2
      if nums[m] < target:
        l = m +1
      else:
        r = m
      if nums[l] == target:
        return l
      else:
        return -1


  # 2. 两个部分的二分
  #  [4,5,1,2,3] tar =5 
  minIndex = findMin(nums)
  if target > nums[-1]:
    return partseek(0,minIndex)
  else:
    return partseek(minIndex,n)

67. 寻找旋转排序数组的最小值

# 66中已经实现了
def findMin(self,nums:List[int]) -> int:
  n = len(nums)
  l,r = 0,n
  while l < r:
    m = (l + r) // 2
    if nums[m] < nums[-1]:
      # 中间值小于最后值，最小值应该在前面
      r = m 
     else:
      # 中间值大于最后，一定在后面
      l = m + 1
   return nums[l]

68. 寻找两个正序数组的中位数

# 如果不限制时间复杂度应该可以merge后排序
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = nums1+nums2
        nums.sort()
        if len(nums)%2 == 1:
            return nums[len(nums)//2]
        if len(nums)%2 == 0:
            l = (len(nums)//2)-1
            return (nums[l]+nums[l+1] )/2

栈

69. 有效的括号

思路：简历哈希表，左括号入栈，右括号出栈；如果最后栈为空就说明有效

def isValid(self, s: str) -> bool:
  d = {
    '}':'{',
    ')':'(',
    ']':'['
  }
  stack = []
  for i in s:
    if i in '([{':
      stack.append(i)
    if i in '}])':
      # 如果是右括号，并且对应
      if d[i] == stack[-1] ans stack:
        stack.pop()
      else:
        return False
  if not stack:
    return True
  return False

70. 最小栈

思路：借助辅助栈，记录最小的值（每次入栈都记录当前最小值）

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = [math.inf]


    def push(self, val: int) -> None:
        # 入栈，辅助记录最小值
        self.stack.append(val)
        self.min_stack.append(min(val,self.min_stack[-1]))

    def pop(self) -> None:

        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

71. 字符串解码

计算原子个数既视感

思路：考虑到只有数字和方括号，用栈保存[ ]之内的部分

对于每个字符分为几种情况：

是数字，要考虑连续数字的情况（*10+int），保存到变量
是左括号[ ，记录之前的num和字符集；入栈，清空原来的字符
是右括号] , 标志这一个括号内的结束，出栈计算新的字符集，保存到变量
是字母，字符集拼接进去

def decodeString(self, s: str) -> str:
  current_string = ''
  num = 0
  ans = ''
  stack = []
  for i in s:
    if i in '0123456789':
      num += num*10 + int(i)
    if i.isalpha():
      current_string += i
    if i == '[':
      # 开始记录，先把之前的存进栈
      stack.append((num,current_string))
      char_set = ''
      num = 0
    if i == ']':
      prev_num,prev_string = stack.pop()
      current_string = prev_num*prev_string + current_string
  return ans

72. 每日温度

给出下一天比这当天高的温度

思路：用栈保存最高温度出现的下标，返回下标减去当天的天数

反向遍历

def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
  n = len(temperatures)
  stack = []
  ans = [0] * n
  # 这不是dp
  for i in  range(n-1,-1,-1):
    t = temperatures[i]
    while stack and stack[-1] <= t:
      stack.pop()
    if stack:
      ans[i] =  st[-1] - i
    stack.append(i)

  return ans

如果是正向遍历呢：

每天入栈，当找到一个比栈顶元素大的就出栈，并求出当天i-出栈的那天j作为值返回给ans[j]

ans = [0] * n
stack = []
for i in range(n):
  t = temperatures[i]
  while stack and t > stack[-1]:
    j = stack.pop()
    
    ans[j] = i - j # i是当天，j是刚比他小的天
  stack.append(i)
return ans

73. 柱状图中最大的矩形

堆

74. 数组中的第K大元素

返回数组的第K大（而不是第K个不同）的元素

[3,2,3,1,2,4,5,5,6] -> k = 4 输出为4（而不是3,输出3是第K个不同的元素）

# 思路1：使用heapq建堆；python默认建堆为最小堆，所以取反
# 因为要弹元素，最小堆弹的是小值，所以取反之后弹最小实际上就是弹最大
# 弹出前K-1个
def findKthLargest(self, nums: List[int], k: int) -> int:
  heap = [-x for x in nums]
  # 建堆语法
  heapq.heapify(heap)#堆化，目前堆的首部是最小值
  for i in range(k-1):
    heapq.heappop(heap)
  return (-heap[0])

思路2：改进快排 + 单区间递归

# 考虑到题目实际指的是排序后倒数第K个下标的元素，可以使用改进的快速排序
def quickselect(arr,start,end,k):
  if start==end:
    return arr[start]
  target = arr[start]
  left = start
  right = end
  while left < right:
    # 从后往前找比target小的
    while left < right and nums[right] >= target:
      right -= 1
    nums[left] = nums[right]
    while left < right and nums[left] < target:
      left += 1
    nums[right] = nums[left]
  nums[left] = target
  rank = left - start + 1  # rank表示当前划分的数是第几大的数
    
  if rank == k:  # 如果正好是第K大，返回它
      return arr[left]
  elif rank > k:  # 如果第K大元素在左边部分
      return quickselect(arr, start, left - 1, k)
  else:  # 如果第K大元素在右边部分
      return quickselect(arr, left + 1, end, k - rank)
  #if left == n-k:
  # return nums[left]
  #quicksort(arr,start,left)
  #quicksort(arr,left+1,end)
 # 上述是正常的快排，每次target能正常找到位置;后续两次划分的quicksort递归两个区域；
# 改进之后只需要递归一片区域

75. 前K个高频元素

Counter/Dict统计,改进快排

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
  # 标准字典统计解法
  			d = {}
        for i in nums:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
        # m = max(d.values())
        n = [v for _,v in d.items()]

        s = sorted(n,reverse = True)
        print(s)
        res = []
        for i,v in d.items():
            if v in s[:k]:
                res.append(i)
        return res
      # counter:

改进快排：target所在位置为q,则被划分为start，q-1以及q-1,end这两个区间
注意：快排的思想决定了当划分之后，一个区间一定小于另外一个区间的值，因此判断k和找到位置q的左侧长度即可：如果k小于q-start，则前K一定在左侧；反之需要加上全部的左侧以及缺少的一部分

1	# 代码参考上一题，修改一下即可

76. 数据流的中位数

不行啊数据流！

贪心

77. 买卖股票的最佳时机

思路：维护最小量，更新最大值；返回最大值

或者使用dp

# 方法1
def maxProfit(self, prices: List[int]) -> int:
  temp = prices[0]
  ans = 0
  for i in prices[1:]:
    if i < temp:
      temp = i
    ans = max(ans,i-temp)
  return ans

方法2：dp标准解法

设定dp[i]表示第i天能获取到的利润，dp[i] = max(dp[i-1],prices[i] - minprice)，其中minprice是价格和以往最小价格的最小值

DP方程的推导：不限制函数，不限制一定是相邻天数，主要前一天（或者子问题）能够用同样的方程进行表达就可以

def maxProfit(self, prices: List[int]) -> int:
  dp = [0] * n
  minprice = prices[0]
  for i in range(1,len(prices)):
    minprice = min(prices[i],minprice)
    dp[i] = max(dp[i-1],prices[i] - minprice)
  return max(dp)

78. 跳跃游戏

我位于第一个下标，每个元素表示能跳的最大长度

判断我能不能达到最后一个下标

思路1：记录max_step,如果某下标小于max_step说明改下标位置不能到达

max_step应该是nums[i] + 之前的最大值

def canJump(self, nums: List[int]) -> bool:
  max_step = 0
  for need in nums:
    if max_step < need:
      return False
    max_step = max(max_step,nums[i] + need)

思路2：dp

这里的dp[i]表示i位置能够被覆盖

def canJump(nums):
    n = len(nums)
    dp = [False] * n  # 初始化 dp 数组，全部为 False
    dp[0] = True  # 第一个位置一定可以到达
    
    for i in range(n):
        if dp[i]:  # 如果能到达位置 i
            furthestJump = min(i + nums[i], n - 1)  # 计算从 i 开始可以跳到的最远位置
            for j in range(i + 1, furthestJump + 1):  # 更新从 i 开始可以到达的范围
                dp[j] = True
    
    return dp[-1]  # 返回能否到达最后一个位置

79. 跳跃游戏II

和I的区别在于，II可以视作一个中转站，I只是标记能够跳到某个位置（但是没跳）

II就可以在区间内的任意位置作为起点开始跳

同时保证了跳跃可达，返回的是跳跃次数的最小值

def jump(self, nums: List[int]) -> int:
  ans = 0
  cur_right = 0
  next_right = 0
  for i in range(len(nums)-1):
    next_right = max(nums[i]+i,next_right)
    if i== cur_right:
      cur_right  = next_right# 更新区间
      ans +=1
  return res

80. 划分字母区间

区间合并题

思路：首先创建字典，记录每个元素最后出现在字符的位置;

对于每一个元素，在字典里搜索其出现的位置作为end位置；

如果遍历到end位置，输出区间长度；更新start值

即：变量i是位置索引，start是区间起始，end是区间结束

遍历到i位置的字符c时，判断end有无变化（应该是最大end）

当遍历到end的位置时，将区间长度加入到列表；并且更新start为i+1（因为end是随i进行判断的）

def partitionLabels(self, s: str) -> List[int]:
  last_char = {c:i for i,c in enumerate(s)}
  start = end = 0
  ans = []
  for i,c in enumerate(s):
    end = max(end,last_char[c])
    if end == i:
      ans.append(end-start+1)
      start = i+1
  return ans

动态规划

81. 爬楼梯

经典动态规划题

每次只能爬1或者2个有多少中不同的方法到楼顶（n阶）

dp[i]表示到达i阶梯的方法数

dp[i] = dp[i-1] + dp[i-2]

# 转移方程：第i层只能来源于i-1层或者i-2层
def climbStairs(self, n: int) -> int:
  dp = (n+1) * [0]
  dp[0] = 1
  dp[1] = 1
  for i in range(2,n+1):
    dp[i] = dp[i-1] + dp[i-2]
  return dp[-1]

82. 杨辉三角

给出杨辉三角的前row行（输入为row）

还就是那个dp呀

# 手写一下就知道了，从第二行（0开始）状态转移方程dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
# 注意dp数组的设置：每一行i+1个[1]
# 注意内层循环,j从1开始
def generate(self, numRows: int) -> List[List[int]]:
  dp = [[1]*(i+1) for i in range(numRow) ]
  for i in range(2,numRows):
    for j in range(1,i):
      dp[i][j] = dp[i-1][j-1]+dp[i-1][j]
  return dp

83. 打家劫舍

不能连续偷两家

考虑最后一天：设置dp[i] 为第i天投的最高金额

dp[i] = dp[i-1],dp[i-2]+nums[i-1]

即

最后一天偷:dp[i-1]
最后一天不偷：nums[i-1]+前天的dp[i-2]

之中的最大值

def rob(self, nums: List[int]) -> int:
  dp = [0] * len(nums)+1)
  dp[0] = 0
  dp[1] = nums[0]
  for i in range(2,len(nums)+1):
    dp[i] = dp[i-1] + dp [i-2] + nums[i-1]
  return dp[-1]

84. 完全平方数

思路: dp，如果一个数是完全平方数，那么这个数i仅需要1个（本身）即可，dp[i] = 1; 如果不是完全平方数，那么尝试分解数，从1到根号i , 维护最小使用的dp值

def numSquares(self, n: int) -> int:
  dp = [0] * (n+1)
  for i in range(1,n+1):
    if i**0.5%1==0:
      #根号i是整数
      dp [i] = 1
    else:
      min_ = float('inf')
      j = 1
      while j*j < i:
        # 尝试dp[i-j*j]
        min_ = min(min_,dp[i-j*j])
        j += 1
      dp[i] = min_ + 1
    return dp[-1]

85. 零钱兑换

思路: dp，设置dp[j] 为装满容量为j的背包所需要的最少硬币个数

（全都是1也就最多amont个，所以硬币个数不会超过amount+1)

注意本题不是连续的dp赋值，而是动态赋值：遍历所有硬币coin，给定从coin开始的金额，依次向后遍历金额，判断dp[j]和使用当前金币的那个小，并维护这个小值

初始化数组，初始化边界dp
转移方程：dp[j] = min (dp[j] ,dp[j-coin]+1)

def coinChange(self, coins: List[int], amount: int) -> int:
  dp = [0] + [amount+1] * len(coins)
  for coin in coins:
    for j in range(coin,amount+1):
      dp[j] = min(dp[j],dp[j-coin]+1)
  return dp[-1]

86. 单词拆分

思路：遍历字符，如果遍历到某个位置在字典中存在，那么说明到这个位置之前的字符是能够被表示的

细节思路：两层循环（约等于双指针），外层i和内层j，判断i:j是否在字典中

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
  n = len(s)
  dp = [False] * (n+1) 
  dp[0] = True
  for i in range(n):
    for j in range(i+1,n+1):
      if dp[i] and s[i:j] in wordDict:
        dp[j] = True
  return dp[-1]

其实还有一个思路是，把所有在字典里的字符都替换成空，看最后是不是空字符串

for i in wordDict:
    if i in s:
       s = s.replace(i,"")

return True if (s=="") else False

87. 最长递增子序列

给定整数数组nums，找到最长严格递增子序列的长度

字面意思：如果相邻的两个数后者大于前者，即为严格递增

dp[i] 表示到达i位置时，(以num[i]) 结尾的最长严格递增序列长度

通过对i位置的二重循环进行判断：

外层为当前元素i
内层 j 为小于i的所有位置

当内层 j 一直发现前方的小于 i 时，i 位置的 dp 值设置为长度（通过dp控制）

其中dp i 应该为 dp[i] 和以j结尾的dp值+1的较大者

def lengthOfLIS(self, nums: List[int]) -> int:
  n = len(nums)
  dp = [1] * (n)
  for i in range(n):
    for j in range(i):
      if nums[j] < nums[i]:
        dp[i] = max(dp[i],dp[j]+1)
  return max(dp)

88. 乘积最大子数组

思路：因为两个相乘有可能会是负值，所以需要记录每个遍历过程中的最小值和最大值，在下一次遍历时候使用最大值和最小值重新计算

设置无穷小dp数组
max min 和 ans的设置初值
状态转移方程：dp[i] 应该是max_cur 和 dp[i-1]中的最大者

其中，每次遍历要重新计算

def maxProduct(self, nums: List[int]) -> int:
  dp = [float('-inf') ]* len(nums)
  max_temp = max_temp = nums[0]
  dp[0] = nums[0]
  for i in range(1,len(nums)):
    max_cur,min_cur = max_temp,max_temp#更新
    max_temp = max(max_cur*nums[i],nums[i],min_cur*nums[i])
    min_temp = min(max_cur*nums[i],nums[i],min_cur*nums[i])
    # max_t,min_t = max(),min()
    dp[i] = max(max_temp,dp[i-1])
 return dp[-1]

89. 分割等和子集

这个是分割成两个等和子集（不是多个）可以的话返回True

思路：先判断和是不是偶数，不是直接返回false

然后建立dp,dp[j]表示能否凑到和为 j 的布尔值

（和硬币有点像，dp[j]当表示硬币个数时值等于dp[j]和用了一个硬币之后的dp值+1的min值）

需要判断dp[target]是否为True，target为目标值的一半（和//2)

def canPartition(self, nums: List[int]) -> bool:
  target = sum(nums)//2
  if sum(nums)%2 == 1 or len(nums)<2:
    return False
  dp = [True] + [False] * target
  for i in range(len(nums)):
    for j in range(target,nums[i]-1,-1):
      dp[j] = dp[j] or dp[j-nums[i]]#dp j加上nums[i]正好是target
  return dp[target]

90. 最长有效括号

思路：栈匹配括号+匹配成功的标记，然后计算最长1的长度

def longestValidParentheses(self, s: str) -> int:
    stack = []
    temp = ['0'] * len(s)
    for i,c in enumerate(s):
        if c == '(':
            stack.append(i)
        else:
            if stack:
                j = stack.pop()
                temp[i],temp[j] = '1','1'
    print(temp)
    t = ''.join(temp)
    split1 = t.split("0")
    len_max = 0
    for i in split1:
        if len(i) > len_max:
            len_max = len(i)
    return (len_max)

多维DP

这类题有特点 1. 有状态转移 2. 或者是匹配两个不同/相同长度的某个位置

比较经典的是LCS

91. 不同路径

机器人只能往下或者往右；

返回到右下角一共有多少条不同的路径

比较经典的二维dp，因为边界处只能有一个方向，所以j = 0 和 i = 0的地方要设置为1

其他区域的取值应该来源于来自上方和来自左边的值

def uniquePaths(self, m: int, n: int) -> int:
        res = [[0] * n for _ in range(m)]
        for i in range(m):
            res[i][0] = 1
        for j in range(n):
            res[0][j] = 1
        for i in range(1,m):
            for j in range(1,n):
                res[i][j] = res[i-1][j] + res[i][j-1]
        return (res[-1][-1])

92. 最小路径和

给定一个网格区域，找出从左上到右下的路径使得路径上的和最小

（只能向下或者向右）

明确的是，这题应该是动态规划（不同路径）然后加一个路径和的限制

所以基本上还是dp的老套路

dp [i] [j]表示到达 grid[i] [j] 的最小路径和
dp [i] [j] 来源于上方或者左边的值
边界只能来源于一侧
路径和的变化和不同路径的变化主要在于dp[i] [j] 存的内容不一样

def minPathSum(self, grid: List[List[int]]) -> int:
  m,n = len(grid),len(grid[0])
  dp = [[0]*n for i in range(m)]
  dp[0][0] = grid[0][0]
  for i in range(1,n):
    #对于每一列，x=0时候只能来源于上侧
    dp[0][i] = dp[0][i-1] + grid[0][i]
  for j in range(1,m):
    #对于每一行，j=0时候只能来源于上册
    dp[j][0] = dp[j-1][0] + grid[j][0]
  for i in range(m):
    for j in range(n):
      grid[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
  return dp[-1][-1]

93. 最长回文子串

沿用判断子串的方法，找到所有回文子串返回最长的

def longestPalindrome(self, s: str) -> str:
        def judge(l,r,strs):
            while l>=0 and r<len(strs) and strs[l] == strs[r]:#大于等于！
                r += 1
                l -= 1
            return strs[l+1:r]
        ans = []
        if len(s)==1:
            return s
        for i in range(len(s)):
            single = judge(i,i,s)
            multi = judge(i,i+1,s)
            ans.append(single)
            ans.append(multi)
        a = sorted(ans,key=lambda i :len(i))
        return (a[-1])

94. 最长公共子序列

思路：动态规划（二维DP）

设置dp[i] [j] 为 text1 匹配到 text2的最长长度，这里分为两种情况

对于遍历到的text1[i]和text2[j]:

相等，此时将前一个位置的长度+1（即i-1,j-1)
不相等，此时应该选择1或者2中前一个位置和当前位置的最大值

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
  # 注意边界text1和text2的0不会匹配任何公共子序列，所以dp[0][:]和dp[:][0]均等于0
  m,n = len(text1),len(text2)
  dp = [[0] * (n+1) for _ in range(m+1)]
  # 初值可以不用额外在定义了，这个赋值已经包括了
  for i in range(m):
    for j in range(n):
      if text1[i] == text2[j]:
        dp[i][j] == dp[i-1][j-1]+1
      else:
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
  return dp[-1][-1]

95. 编辑距离

word1转化为word2的最小次数

dp[i][j]表示w1变成w2的最少次数，其中边界情况是i或者j有一个为空，此时最小次数是字符的长度(遍历到位置)

思路：

考虑到w1转化为w2只有三种情况：

增加（表示i增加），这种情况下匹配到的应该w1的i和w2的j-1；此时+1即可
删除（表示i删除），这种情况下匹配到的是w1的i和w2的j-1，此时+1也能变到（+1是步骤）
修改（i修改），因为修改的情况下i和j都没匹配，匹配的是i-1和j-1；所以i-1，j-1 的LCS + 1（修改的操作本身）即为dp [i] [j]

如果word1[i] == word2[j]相同，则去上个步骤和本次步骤中匹配的最小值

实现：

def minDistance(self, word1: str, word2: str) -> int:
  if not word1 or not word2: return max(len(word1), len(word2))
  m ,n = len(word1),len(word2)
  dp = [[0]*(n+1) for _ in range(m+1)]
 for i in range(m):
      dp[i][0] = i  
 for j in range(n):
      dp[0][j] = j
  for i in range(m):
    for j in range(n):
      if word1[i] == word[j]:
        dp[i][j] = dp[i-1][j-1]
      else:
        delete1 = dp[i][j-1] +1
        add1 = dp[i-1][j] +1 
        change1 = dp[i-1][j-1] +1
        dp[i][j] = min(delete1,add1,change1)
  return dp[-1][-1]

技巧

96. 只出现一次的数字

除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素

按位异或，相同的异或为0，0异或等于数等于数本身（1异或数等于数取反）

def singleNumber(self, nums: List[int]) -> int:
       ans = nums[0]
       for i in range(1,len(nums)):
           ans ^= nums[i]
       return (ans)

97. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素

思路：1. 快排返回中间值 2. 函数调用排序返回中间值 3. 摩尔投票

# 主要写摩尔投票
def majorityElement(self, nums: List[int]) -> int:
  # 思路就是，vote = 0时候就让当前数为众数；如果和众数相同就vote+1；否则-1；选举新的众数
  vote = 0
  for i in nums:
    if vote == 0:
      mass = i
    if i == mass:
      vote +=1
    else:
      vote -=1
  return mass

98. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

思路：1. 排序（就纯排序）快排是原地的 2. 一次遍历，用ptr保存变量值

def sortColors(self, nums: List[int]) -> None:
  ptr = 0
  n = len(nums)
  for i in range(n):
    if nums[i] == 0:
      nums[ptr],nums[i] = nums[i],nums[ptr] 
      ptr +=1
  for i in range(ptr,n):
    if nums[i] == 1:
      nums[i],nums[ptr] = nums[ptr],nums[i]
   # 交换完剩下全都是2，都在后面
  return nums

99. 下一个排列

返回字典序更大的下一个排列

思路：从右往左找第一个左边小于右边的下标（要点：相邻，且左小于右）分别是i,j

特点：此时右侧严格递减

从右往左找比nums[i]大的数然后交换,此时j到n应该是倒序最大，我们在生成下一个排列时应该是从小开始，所以逆序nums[j:]

def nextPermutation(self, nums: List[int]) -> None:
  n = len(nums)
  index = n -2 # 最后一个是n-1，因为保证相邻两个数的向右（i，i+1)不越界
  while i >=0 and nums[i] >= nums[i+1]: #找小
    i -= 1
  if i >= 0:
    j = n-1
    while j < n and nums[j] <= nums[i]:#找大
      j -= 1
    nums[j],nums[i] = nums[i],nums[j]
  #nums = nums[i] + nums[i+1:][::-1]
  l,r = i+1,n-1
  while l<r:
    nums[l],nums[r] = nums[r],nums[l]
    l+=1
    r-=1

100. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

# 如果不限制，那么可以排序寻找连续相同值；可以一次遍历输出计数为2的值
# 限制nums不修改，并且额外空间等于O(1)
# 改进二分查找，鸽巢原理：l到m中如果有多余半数的元素，说明多余的元素在该区间
def findDuplicate(self, nums: List[int]) -> int:
  l,r = 1,len(nums)
  while l<r:
    m = (l+r)//2:
    count = sum( left <= num <= m for num in nums)
    # nums内落在l,m的个数
    if count>m-l+1:
      r = m # 这里包含m，因为重复的元素可能是m
    else:
      l = m+1
    return l