【Leetcode 第二轮刷题日记】LeetcodeTOP100+高频题整理_leetcode top100

前言

刷完第一轮已经4月了，第一轮刷了大概200多道题。本来还打算第一轮就好好刷400题的，但是发现时间好像不是很充足，所以这一轮就集中刷专题版剑指offer+第一版剑指offer+高频整理题（100道左右），加起来应该200题不到，很多第一轮都刷过的。
下面的题目都是我从这几个地方整理来的：

1、一直跟这个大佬的博客学习，整理的非常好: LeetCode算法题高频整理(精华篇 100道题左右).
2、Leetcode热题100道，最精华的题目了，必须刷道滚瓜烂熟: LeetCode 热题 HOT 100.
3、听朋友说这里面的题经常考: 腾讯精选练习 50 题.

目录当中有这些题的来源，出现频次越高，差不多就知道哪些题是精华了，应该是200道题不到，一定要刷到滚瓜烂熟。

一些笔记

链表笔记

1、如果操作可能会改变链表的表头，应该声明指向链表head的dummy节点，最后返回dummy.next；（LeetCode82）;

dummy = ListNode(-1, head)
rear = head
# 然后对新链表进行操作
1
2
3

2、求链表的倒数节点，一般用快慢指针的思路；（ Leetcode 19）

3、下面两句是不一样的

 while cur and cur.next:
 while cur.next and cur:
1
2

4、翻转链表（剑指offerII 024、Leetcode 25、Leetcode445）

def reverseList(self, head: ListNode) -> ListNode:
  dummy = ListNode(-1)
  p = head
  while p:
      temp = p.next
      p.next = dummy.next
      dummy.next = p
      p = temp
  return dummy.next
1
2
3
4
5
6
7
8
9

5、环形链表一般是用快慢指针做的（LeetCode142）

6、找到链表的中间节点/将链表分割为两部分（Leetcode 234、LeetCode143）

# 第一种写法：奇数时slow指向中间节点，偶数时指向后半部分第一个节点，常用于回文链表中
slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# 偶数个节点 fast=null slow=后半部分第一个节点
# 奇数个节点 fast=链表最后一个节点 slow=中间节点
if fast: slow = slow.next  # 无论奇偶slow都是后半部分第一个节点

# 第二种写法，在找到中间节点之后，如果需要将这个链表从中间断开，那么就用这种写法。
slow, fast = head, head.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# 偶数个节点 fast=链表最后一个节点 slow指向前半部分节点的最后一个
# 奇数个节点 fast=null slow指向中间节点
# 从中间断开这个链表  得到head 和 mid两个新链表
# 奇数的时候head链表=前一半节点+中间节点；mid链表=后一半节点 
# 偶数的时候head链表=前一半节点；mid链表=后一半节点
mid = slow.next
slow.next = None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

7、合并两个有序链表（LeetCode21）

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
     if not list1: return list2
     if not list2: return list1
     dummy = ListNode(-1)
     rear = dummy
     p, q = list1, list2
     while p and q:
         if p.val <= q.val:
             rear.next = p
             p = p.next
         else:
             rear.next = q
             q = q.next
         rear = rear.next
     rear.next = p if p else q
     return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8、链表排序-归并排序（LeetCode148）

def merge(self, left, right):  # 合并两个有序链表
     dummy = ListNode(-1)
     rear = dummy
     p, q = left, right
     while p and q:
         if p.val <= q.val:
             rear.next = p
             p = p.next
         else:
             rear.next = q
             q = q.next
         rear = rear.next
     rear.next = p if p else q
     return dummy.next 
     
 def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
     if not head or not head.next: return head
     # 找到链表中点
     slow, fast = head, head.next
     while fast and fast.next:
         slow = slow.next
         fast = fast.next.next
     # 偶数个节点 fast=链表最后一个节点 slow指向前半部分节点的最后一个
     # 奇数个节点 fast=null slow指向中间节点

     # 把链表切成两部分，再对这俩个部分进行排序
     mid = slow.next
     slow.next = None
     left, right = self.sortList(head), self.sortList(mid)

     # 最后将两个排序链表合并为一个有序链表
 	    return self.merge(left, right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

9、双向链表相关操作(面试高频题：Leetcode143 LRU缓存)

在p节点后面插入节点node：

node.next = p.next
p.next.pre = node
node.pre = p
p.next = node
1
2
3
4

删除node节点：

node.pre.next = node.next
node.next.pre = node.pre
1
2

10、普通的直接硬写的题目：Leetcode24；技巧性的题目：Leetcode160、Leetcode23；

树笔记

这7个模板模板如果不是很清楚的话，可以看下面的几个视频，都是我看的比较好的二叉树遍历模板视频讲解：

二叉树的DFS代码讲解: 【专题讲解】 二叉树的前中后序非递归遍历 leetcode 94 144 145.

二叉树的BFS代码讲解: Tree-Python(广度优先遍历BFS)(1).

1、前序遍历DFS模板

# 1、递归写法
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if not root: return []
    res = []
    def dfs(root):
        if not root: return 
        self.res.append(root.val)
        dfs(root.left)
        dfs(root.right)
    dfs(root)
        return self.res
# 2、迭代写法
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if not root: return []
     stack, res = [], []
     cur = root
     while stack or cur:
         while cur:
             res.append(cur.val)
             stack.append(cur)
             cur = cur.left
         cur = stack.pop()
         cur = cur.right
     # 结束while循环 stack=[] cur=None
     return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2、中序遍历DFS模板

# 1、递归写法
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
     if not root: return []
     self.res = []
     def dfs(root):
         if not root: return 
         dfs(root.left)
         self.res.append(root.val)
         dfs(root.right)
     dfs(root)
     return self.res
# 2、迭代写法
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if not root: return []
    stack, res = [], []
    cur = root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        res.append(cur.val)
        cur = cur.right
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3、后序遍历DFS模板

# 1、递归写法
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if not root: return []
    self.res = []
    def dfs(root):
        if not root: return 
        dfs(root.left)
        dfs(root.right)
        self.res.append(root.val)
    dfs(root)
    return self.res
# 2、迭代写法
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if not root: return []
    stack, res = [], []
    cur = root
    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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

翻转二叉树（后序遍历）
LeetCode226. 翻转二叉树.

def invertTree(self, root: TreeNode) -> TreeNode:
    if not root: return None
    def dfs(root):
        if not root: return None
        left = dfs(root.left)
        right = dfs(root.right)
        root.left, root.right = root.right, root.left
        return root
    return dfs(root)
1
2
3
4
5
6
7
8
9

4、层次遍历BFS模板

# 1、分层打印
def levelOrder(self, root: TreeNode) -> List[List[int]]:
    if not root: return []
    res, queue = [], [root]
    while queue:
        arr, size = [], len(queue)
        for _ in range(size):
            cur = queue.pop(0)
            arr.append(cur.val)
            if cur.left: queue.append(cur.left)
            if cur.right: queue.append(cur.right)
        res.append(arr)
    return res   # [[3],[9,20],[15,7]]
# 2、不分层打印
def levelOrder(self, root: TreeNode) -> List[List[int]]:
    if not root: return []
    res, queue = [], [root]
    while queue:
        cur = queue.pop(0)
        res.append(cur.val)
        if cur.left: queue.append(cur.left)
        if cur.right: queue.append(cur.right)
    return res  # [3,9,20,15,7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5、在函数a的函数b中使用函数a的遍历，这个遍历最好用self. 让他变成全局变量
6、下面两种添加方式一样

res = [1,2]
res.append(3) -> res = [1,2,3]
res += [3] -> res = [1,2,3]
1
2
3

7、求二叉树的最大深度适合用前序来做，最大高度适合用后序来做

二叉树深度: 指从根节点到该节点的最长简单路径边的条数
二叉树高度：指从该节点到叶子节点的最长简单路径边的条数

# 二叉树最大深度  前序
def maxDepth(self, root: Optional[TreeNode]) -> int:
     if not root: return 0
     left = self.maxDepth(root.left)
     right = self.maxDepth(root.right)
     return max(left, right) + 1
1
2
3
4
5
6

8、idx = list.index(val) 返回list中值为val的index下标

一、链表篇（14）

1.1、删除链表元素

LeetCode237. 删除链表中的节点（ 腾讯）

LeetCode237. 删除链表中的节点.

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next
1
2
3
4
5
6
7
8

LeetCode19. 删除链表的倒数第 N 个结点（ ⭐️⭐️⭐️高频、剑指II、HOT100）

LeetCode19. 删除链表的倒数第 N 个结点.

要点：首先，删除倒数第N个节点，肯定是可能会删除头节点的，所有一定要用dummy节点；其实要想到快慢指针的思路，差不多就解出来了。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(-1, head)
        slow, fast = dummy, head
        for i in range(n):  # 快指针往前走n步
            fast = fast.next
        while fast:  # 快慢指针一起走
            fast = fast.next
            slow = slow.next
        # 快指针走向链表外 慢指针刚好走到倒数第n个节点的前一个节点
        slow.next = slow.next.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

相同的类型还有找链表的中心节点，也是用快慢指针，慢指针每次走一步，快指针每次走两步，快指针走到末尾节点了，满指针也就走到了中间节点了。

LeetCode82. 删除排序链表中的重复元素 II（⭐️⭐️高频、剑指II）

LeetCode82. 删除排序链表中的重复元素 II.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        dummy = ListNode(-1, head)
        pre, cur = dummy, head
        # 注意这里的cur and cur.next和cur.next and cur是不一样的
        # 加入cur是因为下面的特殊情况[1,2,3,3,3] 最后cur=None 这里的while就会报错
        while cur and cur.next:
            if cur.val == cur.next.val:
                while cur.val == cur.next.val:
                    cur = cur.next
                    # 特殊情况 [1,2,3,3,3] 到最后cur.next=None 报错
                    if not cur.next: break 
                pre.next = cur.next
                cur = pre.next
            else:
                pre, cur = cur, cur.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.2、翻转/旋转链表

剑指 Offer II 024. 反转链表（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）

剑指 Offer II 024. 反转链表.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 头插法
        dummy = ListNode(-1)
        p = head
        while p:
            temp = p.next
            p.next = dummy.next
            dummy.next = p 
            p = temp
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode25. K 个一组翻转链表（难）（⭐️高频）

LeetCode25. K 个一组翻转链表.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverse(self, start, end):
        pre, cur = None, start
        while cur != end:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next: return head
        dummy = ListNode(-1)
        rear = dummy
        k_start, k_end = head, head
        while k_end:
            for i in range(k):
                if not k_end:  # 不足k步 直接插在尾部
                    rear.next = k_start
                    return dummy.next
                k_end = k_end.next
            # 找到k步 翻转这k步 再尾插到当前链表中
            rear.next = self.reverse(k_start, k_end)
            rear = k_start  # 翻转之后此时末尾节点是k_start
            # 下一组
            k_start = k_end
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

LeetCode61. 旋转链表（腾讯）

旋转数组：先整体逆序，再前k个逆序，最后k后面逆序

LeetCode61. 旋转链表.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 1 2 3 4 5 6 7   k=3
        if not head: return None
        def reverse(a, b):
            # 翻转从a节点到b节点
            dummy = ListNode(-1)
            cur = a
            while cur != b:
                temp = cur.next
                cur.next = dummy.next
                dummy.next = cur
                cur = temp
            return dummy.next
        # 计算链表长度
        p = head
        length = 0
        while p:
            length += 1
            p = p.next
        # 如果k>length 取余
        if k > length: k %= length
        if k == 0: return head  # [1] k=99 取余k=0
        dummy = ListNode(-1)
        rear = dummy
        # 整个链表逆序
        rear.next = reverse(head, p)
        # print(rear)  # -1 7 6 5 4 3 2 1

        # 0-k逆序
        a, b = rear.next, rear.next
        for i in range(k):
            b = b.next
        rear.next = reverse(a, b)
        # # print(rear)  # -1 5 6 7
        # print(a)  # 7
        # print(b)  # 4 3 2 1

        rear = a    # rear = 7
        # 把k->末尾逆序
        a = b
        while b:
            b = b.next
        rear.next = reverse(a, b)  # rear=7 1 2 3 4
        # print(dummy) # -1 5 6 7 1 2 3 4 
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

1.3、交换链表节点

LeetCode24. 两两交换链表中的节点（⭐️高频）

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        dummy = ListNode(-1)
        pre, cur = head, head.next 
        rear = dummy  # 新链表尾节点
        while cur:
            # 两两交换位置
            temp = cur.next
            cur.next = pre
            pre.next = temp
            # 接到新链表末尾
            rear.next = cur
            rear = pre
            # 下一组
            pre = temp
            cur = temp.next if temp else None  # 防止temp=None temp.next报错
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.4、环形/相交/回文链表

LeetCode141. 环形链表（腾讯）

LeetCode141. 环形链表，判断一个链表是否有环，直接双指针搞定，很简单：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:、
        # 快慢指针，如果存在环 那么快慢指针一定会相交
        if not head or not head.next: return False
        slow, fast = head, head
        while fast and fast.next:  
            slow = slow.next
            fast = fast.next.next
            if slow == fast: return True  # 防止一开始满足条件
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode142. 环形链表II（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）

LeetCode142. 环形链表II.
这道题更像是一道数学题，题解：力扣官方题解.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这两道题也可以用hash表来做，直接秒：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        hash_set = set()
        p = head
        while p:
            if p not in hash_set:
                hash_set.add(p)
                p = p.next
            else:
                return p
        return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode160.相交链表（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）

LeetCode142. 环形链表II.

这道题非常的巧妙，题解：力扣官方题解.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB: return None
        p, q = headA, headB
        while p != q:
            p = headB if not p else p.next
            q = headA if not q else q.next
        return p
1
2
3
4
5
6
7
8
9
10
11
12
13

同样hash表也可以直接秒杀：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        hash_set = set()
        p = headA
        while p:
            hash_set.add(p)
            p = p.next
        q = headB
        while q:
            if q in hash_set: return q
            q = q.next
        return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode234.回文链表（⭐️⭐️⭐️高频、剑指II、HOT100）

234. 回文链表.

第一种思路是用栈存储前面一半的节点（用快慢指针找中点），再每次pop栈顶节点和后面一般节点比较：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head: return True
        stack = []
        slow, fast = head, head
        # 把前面一半的节点值存入栈中 
        while fast and fast.next:
            stack.append(slow.val)
            slow = slow.next
            fast = fast.next.next
        # 链表有奇数个节点 中间奇数位不需要比较 slow向后移一位
        if fast: slow = slow.next
        while slow:
            # 后一半节点一个个的和栈顶元素比较
            if slow.val != stack.pop():
                return False
            slow = slow.next
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第二种思路，边找中点边将前一半节点逆序，然后再将前一半节点和后一半节点比较：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head: return True
        dummy = ListNode(-1)
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            # 前半段节点逆序 头插法
            temp = slow.next
            slow.next = dummy.next
            dummy.next = slow
            slow = temp
        if fast: slow = slow.next
        p = dummy.next
        while p and slow:
            if p.val != slow.val: return False
            p = p.next
            slow = slow.next
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.5、链表合并

LeetCode2: 两数相加（⭐️腾讯 HOT100）

LeetCode2: 两数相加.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p, q = l1, l2
        dummy = ListNode(-1, l1)
        rear = dummy
        # 不考虑进位 直接相加
        while p and q:
            p.val += q.val
            rear = p
            p = p.next
            q = q.next
        if q:
            rear.next = q
        # 下面考虑进位
        pre, cur = dummy.next, dummy.next.next
        while cur:
            if pre.val >= 10:
                cur.val += 1
                pre.val %= 10
            pre = cur
            cur = cur.next
        # 考虑末位进位
        if pre.val >= 10:
            pre.val %= 10
            pre.next = ListNode(1)
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

LeetCode445: 两数相加II（⭐️⭐️⭐️高频、剑指II、HOT100）

LeetCode445: 两数相加II.
这道题和上一题的区别就是最高位的顺序相反，所以在上一题的基础上加个逆序就解决了：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverse(self, l1):
        dummy = ListNode(-1)
        p = l1
        while p:
            temp = p.next
            p.next = dummy.next
            dummy.next = p
            p = temp
        return dummy.next
    def add(self, l1, l2):
        dummy = ListNode(-1, l1)
        p, q = l1, l2
        rear = dummy
        while p and q:   # 不考虑进位 直接相加
            p.val += q.val
            rear = p
            p = p.next
            q = q.next
        if q:
            rear.next = q
        pre, cur = dummy.next, dummy.next.next
        while cur:   # 考虑进位
            if pre.val >= 10:
                cur.val += 1
                pre.val %= 10
            pre = cur
            cur = cur.next
        if pre.val >= 10:  # 末位进位
            pre.val %= 10
            pre.next = ListNode(1)
        return dummy.next
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        l1 = self.reverse(l1)
        l2 = self.reverse(l2)
        l1 = self.add(l1, l2)
        return self.reverse(l1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

LeetCode21: 合并两个有序链表（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）

LeetCode21: 合并两个有序链表.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1: return list2
        if not list2: return list1
        dummy = ListNode(-1)
        rear = dummy
        p, q = list1, list2
        while p and q:
            if p.val <= q.val:
                rear.next = p
                p = p.next
            else:
                rear.next = q
                q = q.next
            rear = rear.next
        rear.next = p if p else q
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

LeetCode23: 合并K个排序链表（⭐️⭐️高频、HOT100 腾讯）

第一个想法就是直接两两链表进行合并，发现很简单，代码也能通过：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def merge_two_list(self, l1, l2):
        if not l1: return l2
        if not l2: return l1
        dummy = ListNode(-1)
        rear = dummy
        p, q = l1, l2
        while p and q:
            if p.val <= q.val:
                rear.next = p
                p = p.next
            else:
                rear.next = q
                q = q.next
            rear = rear.next
        rear.next = p if p else q
        return dummy.next 
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists: return
        if len(lists) == 1: return lists[0]
        merge_list = lists[0]
        for i in range(1, len(lists)):
            merge_list = self.merge_two_list(merge_list, lists[i])
        return merge_list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

但是时间复杂度有点高，而且这道题是很多大厂都很喜欢考察的一道题，单单会这种简单方法应该是过不了关的，所以再学一种堆排序的思路：把K个链表的首元素先建立一个最小堆，这样堆顶元素就是最小值， 拿下来，放入最终链表中，然后看看这个最小值来自哪个链表， 把该链表接下来的一个元素加入到堆里面去，直到堆为空即可。

LeetCode23: 合并K个排序链表.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists or len(lists) == 0: return
        if len(lists) == 1: return lists[0] 
        dummy = ListNode(-1)
        rear = dummy
        heap = []
        # 存储lists中所有链表的第一个节点值以及对应的链表idx
        for idx in range(len(lists)):
            if lists[idx]:
                # lists[idx]存放的是第idx个链表的head节点
                heapq.heappush(heap, (lists[idx].val, idx))  
                lists[idx] = lists[idx].next
        while heap:
            # pop出堆顶元素  最小值,链表idx
            min_val, idx = heapq.heappop(heap)
            # 将最小值接到最终链表尾部
            rear.next = ListNode(min_val)
            rear = rear.next
            # 如果这个idx链表不为空，再从这个链表中取出最小值 放入堆中
            if lists[idx]:
                heapq.heappush(heap, (lists[idx].val, idx))
                lists[idx] = lists[idx].next  # 头节点向后移一位
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

1.6、重排链表

LeetCode148: 排序链表（⭐️⭐️⭐️高频、剑指II、HOT100）

第一下脑海里想到打就是用堆排序，再重建链表，直接秒：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = head
        heap = []
        dummy = ListNode(-1)
        rear = dummy
        while p:
            heapq.heappush(heap, p.val)
            p = p.next
        while heap:
            rear.next = ListNode(heapq.heappop(heap))
            rear = rear.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

但是想想还是优点讨巧，这和直接遍历，再sort，再排序有什么区别，所以还是老老实实用归并排序写：
LeetCode148: 排序链表.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def merge(self, left, right):
        dummy = ListNode(-1)
        rear = dummy
        p, q = left, right
        while p and q:
            if p.val <= q.val:
                rear.next = p
                p = p.next
            else:
                rear.next = q
                q = q.next
            rear = rear.next
        rear.next = p if p else q
        return dummy.next 
        
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        # 找到链表中点
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 偶数个节点 fast=链表最后一个节点 slow指向前半部分节点的最后一个
        # 奇数个节点 fast=null slow指向中间节点

        # 把链表切成两部分，再对这俩个部分进行排序
        mid = slow.next
        slow.next = None
        left, right = self.sortList(head), self.sortList(mid)

        # 最后将两个排序链表合并为一个有序链表
        return self.merge(left, right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

LeetCode143: 重排链表（⭐️⭐️高频、剑指II）

LeetCode143: 重排链表.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverse(self, head):
        dummy = ListNode(-1)
        p = head
        while p:
            temp = p.next
            p.next = dummy.next
            dummy.next = p
            p = temp
        return dummy.next
    def reorderList(self, head: ListNode) -> None:
        if not head or not head.next: return head
        # 找中点
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 中间切断
        new_head = slow.next
        slow.next = None
        # 后半部分逆序
        new_head = self.reverse(new_head)
        # 交叉插入新链表中
        dummy = ListNode(-1)
        rear = dummy
        p, q = head, new_head
        while p and q:
            rear.next = p
            rear = p
            p = p.next
            
            rear.next = q
            rear = q
            q = q.next
        rear.next = p if p else q
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

1.7、LRU缓存

LeetCode146. LRU 缓存（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）

LeetCode146. LRU 缓存.

b站视频讲解.

class ListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.pre = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity  
        self.cur_size = 0
        # 初始化hashmap key:key  val:ListNode  方便get函数直接获取O(1)
        self.ListNodeMap = dict()
        # 初始化双向链表 新建头尾节点
        self.head = ListNode(-1, -1)
        self.tail = ListNode(-1, -1)
        self.head.next = self.tail
        self.tail.next = self.head
        
    def get(self, key: int) -> int:
        # hash map -> O(1)
        if key in self.ListNodeMap:
            node = self.ListNodeMap[key]
            self.moveToHead(node)
            return node.val
        else: return -1

    def put(self, key: int, value: int) -> None:
        # 双向链表 -> O(1)
        if key in self.ListNodeMap:
            node = self.ListNodeMap[key]
            node.val = value
            self.moveToHead(node)
        else:
            node = ListNode(key, value)
            self.ListNodeMap[key] = node
            self.addToHead(node)

    def moveToHead(self, node):
        # remove from cur pos
        node.pre.next = node.next
        node.next.pre = node.pre
        # insert into self.head next
        node.next = self.head.next
        self.head.next.pre = node
        node.pre = self.head
        self.head.next = node
    
    def addToHead(self, node):
        self.cur_size += 1
        # add node to self.head next
        node.next = self.head.next
        self.head.next.pre = node
        node.pre = self.head
        self.head.next = node
        # check capacity
        if self.cur_size > self.capacity:
            deleteNode = self.tail.pre
            deleteNode.pre.next = self.tail
            self.tail.pre = deleteNode.pre
            self.cur_size -= 1
            self.ListNodeMap.pop(deleteNode.key)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

二、树篇（26）

本章题目总结：

1. 层次遍历的题目比较简单，基本上弄得层次遍历的题目都是可以秒杀的
   最后那道牛客的题有点东西：判断是否是完全二叉树的题，。

2. 中序遍历：这部分的题目呢总是和二叉搜索树相关，一般用非递归容易写，特别是设计节点的一些操作，比如需要找到当前节点前一个节点的题，用非递归好写点。
   最后两题有点意思：一个二叉搜索树转成双向链表；一个累加树（倒中序right->mid->left）

3. 二叉搜索树相关：二叉搜索树的题目一般会用到两个性质：1、中序遍历=升序；2、root.val>root.left.val and root.val < root.right.val（左子树都小于当前节点，右子树都大于当前节点）
   上面的中序遍历是用到性质一，下面的两道题一般是用性质2：一道是求二叉搜索树的最近公共祖先，一道是判断某个数组是不是某个二叉搜索树的后续遍历结果
   这部分这两道题都需要注意下。

4. 前序遍历：这里的题目基本是都是用前序遍历的递归框架解决的：

   def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
       if not root: return
       def dfs(root):
           # 递归出口
           if not root: return 
           # 当前层处理逻辑 一般有判断当前层是否是叶子节点....
           # 递归调用左右子树
           dfs(root.left)
           dfs(root.right)
       dfs(root)
       return self.res
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11

   需要注意的是：这里需要返回什么？是否可以在preorderTraversal设置一个self.res全局变量，在dfs用self.res调用即可？这要看是否会在preorderTraversal调用自身，如果需要调用自身，那么你在preorderTraversal中每次都会重新定义这个全局变量，那么就不能在preorderTraversal中定义这个全局变量。如路径总和3，不过大部分情况下还是可以定义的。
   这部分的题目需要格外注意的是：leetcode437路径总和3

5. 后序遍历：这部分可以和后面的递归专题一起合起来看，联系很紧密
   这部分的题目应该是树专题中比较难也是比较最要的部分，一道要全弄懂。
   leetcode236可以说是树章节的王者，非常常考，也比较难，一定要掌握啊。另外leetcide124也稍微注意下。

6. 树的递归：Leetcode572挺特别的一道题，和一般的递归想法不一样；

7. 二叉树的修改构造：两道题都挺经典的，尤其是序列化与反序列化那道题，面试非常高频。必须掌握。

8. 技巧性题：这道题是HOT100的题，很经典，一定要掌握：LeetCode114. 二叉树展开为链表

2.1、二叉树前序遍历

LeetCode257.二叉树的所有路径（⭐️高频）

LeetCode257: 二叉树的所有路径.

def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
    if not root: return []
    res = []
    def dfs(root, path):
        # 递归出口
        if not root: return None
        # 当前节点处理逻辑
        if not root.left and not root.right: 
            res.append(path + str(root.val))
        dfs(root.left, path + str(root.val) + '->')
        dfs(root.right, path + str(root.val) + '->')
    dfs(root, '')
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 129.求根到叶子节点数字之和（⭐️⭐️高频、剑指II）

这道题和上道题差不多。
LeetCode 129.求根到叶子节点数字之和.

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if not root: return 0
        self.res = 0
        def dfs(root, cur):
            # 递归出口
            if not root: return None
            # 当前节点处理逻辑
            if not root.left and not root.right:
                self.res = self.res+cur*10+root.val
            dfs(root.left, cur*10+root.val)
            dfs(root.right, cur*10+root.val)
        dfs(root, 0)
        return self.res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode617. 合并二叉树（⭐️Hot100）

LeetCode617. 合并二叉树

def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
    # 先序遍历
    # 递归返回的是合并后树（当前节点root1和root2合并后的树）
    # 3个递归出口
    # 如果传进来root1和root2都为空 返回空
    if not root1 and not root2: return None
    # 一个为空 就返回另一个
    if not root1: return root2
    if not root2: return root1
    
    # 处理当前层逻辑
    # 两个都不为空 
    root1.val += root2.val

    # root1.left
    root1.left = self.mergeTrees(root1.left, root2.left)
    # root1.right
    root1.right = self.mergeTrees(root1.right, root2.right)
    # 返回当前这颗合并后的树
    return root1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode113.路径总和II（⭐️高频）

这道题有一个简单变式 LeetCode112.路径总和I.，很简单直接秒

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
    if not root: return False
    self.flag = False
    def dfs(root, cur):
        # 递归出口
        if not root: return 
        # 当前节点处理逻辑
        if not root.left and not root.right:
            if cur-root.val == 0: self.flag=True
        dfs(root.left, cur-root.val)
        dfs(root.right, cur-root.val)
    dfs(root, targetSum)
    return self.flag
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode113.路径总和II.

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    if not root: return []
    self.res = []  # 注意这里的变量要self. 让它变成全局变量
    def dfs(root, path, cur):
        # 递归出口
        if not root: return
        # 处理当前层逻辑
        if not root.left and not root.right:
            if cur-root.val == 0:
                path.append(root.val)
                self.res.append(path)
        # append 和 +[] 是一样的
        dfs(root.left, path+[root.val], cur-root.val)
        dfs(root.right, path+[root.val], cur-root.val)
    dfs(root, [], targetSum)
    return self.res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode437.路径总和 III（⭐️难 Hot100）

LeetCode437. 路径总和 III.

视频讲解.

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
    # 求以root为根节点的树里节点值之和等于targetSum的路径个数 
    if not root: return 0
    def dfs(node, cur_sum):
        # 以node为根节点的的树里节点值之和等于targetSum且起始节点为node的路径个数
        # 递归出口 
        if not node: return 0
        res = 0
        # 处理当前层逻辑
        if node.val == cur_sum: 
            res += 1
        res += dfs(node.left, cur_sum-node.val)
        res += dfs(node.right, cur_sum-node.val)
        return res
    res = dfs(root, targetSum)
    res += self.pathSum(root.left, targetSum)
    res += self.pathSum(root.right, targetSum)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.2、二叉树中序遍历

LeetCode98.验证二叉搜索树（⭐️⭐️高频、HOT100）

LeetCode98.验证二叉搜索树.

def isValidBST(self, root: TreeNode) -> bool:
    if not root: return False
    stack, cur = [], root
    pre = float('-inf')
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        if cur.val <= pre:
            return False
        pre = cur.val
        cur = cur.right
    return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14

剑指 Offer 54. 二叉搜索树的第k大节点（⭐️高频）

剑指 Offer 54. 二叉搜索树的第k大节点.

def kthLargest(self, root: TreeNode, k: int) -> int:
    stack, cur = [], root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.right
        cur = stack.pop()
        k -= 1
        if k == 0: return cur.val
        cur = cur.left
1
2
3
4
5
6
7
8
9
10

Leetcode230. 二叉搜索树中第K小的元素（⭐️腾讯）

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

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        if not root or k < 0: return -1
        stack, cur = [], root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            k -= 1
            if k == 0: return cur.val
            cur = cur.right
1
2
3
4
5
6
7
8
9
10
11
12

剑指offer36: 二叉搜索树与双向链表（⭐️高频）

剑指offer36: 二叉搜索树与双向链表.

    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
        # right = next   left = pre
        if not root: return None
        stack, cur = [], root
        pre, head = None, None
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            # 找到头节点 最小节点
            if pre == None: head = cur
            else:
                pre.right = cur  # 中间节点转为双向链表
                cur.left = pre
            pre = cur  # 向后移动
            cur = cur.right
        # 找到末尾节点 因为while循环出来cur=None
        p = head
        while p.right: 
            p = p.right
        # 首尾相连 形成循环双向链表
        p.right = head
        head.left = p
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Leetcode.538. 把二叉搜索树转换为累加树（⭐️Hot100）

Leetcode.538. 把二叉搜索树转换为累加树.

def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
   # 反中序  右根左
   if not root: return None
   stack, cur = [], root
   pre = None
   while stack or cur:
       while cur:
           stack.append(cur)
           cur = cur.right
       cur = stack.pop()
       if pre != None: 
           cur.val += pre.val
       pre = cur
       cur = cur.left
   return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.3、二叉树后序遍历

Leetcode104. 二叉树的最大深度（⭐️HOT100 腾讯）

Leetcode104. 二叉树的最大深度.

def maxDepth(self, root: Optional[TreeNode]) -> int:
     if not root: return 0
     left = self.maxDepth(root.left)
     right = self.maxDepth(root.right)
     return max(left, right) + 1
1
2
3
4
5

LeetCode226. 翻转二叉树（⭐️HOT100）

LeetCode226. 翻转二叉树.

def invertTree(self, root: TreeNode) -> TreeNode:
    if not root: return None
    def dfs(root):
        if not root: return None
        left = dfs(root.left)
        right = dfs(root.right)
        root.left, root.right = root.right, root.left
        return root
    return dfs(root)
1
2
3
4
5
6
7
8
9

Leetcode110. 判断是否是平衡二叉树（⭐️高频）

Leetcode110. 判断是否平衡二叉树.

这道题是求高度的题，最好是用后序遍历的方法，当然前序遍历也能做，但是前序遍历计算了根节点的高度，还要计算根节点的左子树高度、右子树高度，这就有很多的重复计算了，记住，计算高度用后序遍历，计算深度用前序遍历。

def isBalanced(self, root: TreeNode) -> bool:
    if not root: return True
    def dfs(root):
        # 函数返回：以root为根节点的这棵树是否是平衡二叉树
        # 递归出口
        if not root: return 0
        # 边求高度边判断
        left = dfs(root.left)
        # 如果当前节点左子树不是平衡二叉树 那么以当前节点为根节点的树也不是平衡二叉树
        if left == -1: return -1
        # 如果当前节点右子树不是平衡二叉树 那么以当前节点为根节点的树也不是平衡二叉树
        right = dfs(root.right)
        if right == -1: return -1
        # 左右子树都是平衡二叉树 再判断当前节点是不是平衡二叉树 如果是的话返回-1
        # 不是的话返回以当前节点为根节点的子树高度
        # 当前层逻辑
        return max(left, right)+1 if abs(left-right)<=1 else -1
    return dfs(root) != -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode543.二叉树的直径 （⭐️⭐️高频、HOT100）

LeetCode543.二叉树的直径.

def diameterOfBinaryTree(self, root: TreeNode) -> int:
    if not root: return 0
    self.max_count = 1  # 最大节点个数
    def dfs(root):
        # 函数返回：以root为根节点这颗树的最大直径
        # 递归出口
        if not root: return 0
        # 左子树最大节点个数
        left = dfs(root.left)
        # 右子树最大节点个数
        right = dfs(root.right)
        # 当前层逻辑
        # root这颗树的最大节点个数=左子树最大节点个数+右子树最大节点个数+1
        self.max_count = max(self.max_count, left+right+1) 
        # 往上走root作为子树的最大节点个数
        return max(left, right) + 1
    dfs(root)
    return self.max_count - 1  # 最大直径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode124.二叉树中的最大路径和（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）

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

和上面那题差不多。

def maxPathSum(self, root: Optional[TreeNode]) -> int:
    if not root: return 0
    self.max_path_sum = float('-inf')
    def dfs(root):
        # 函数返回：以root为根节点的这棵树的最大路径和  
        # 注意返回root这课树的最大路径和它必须是向上的  也就是只能选择左子树或者右子树其中一个
        # 如果都是选的话 那么这棵树就是横向的了
        # 递归出口
        if not root: return 0
        # 调用左子树 求左子树最大路径和
        left = max(dfs(root.left), 0)
        # 调用右子树 求右子树最大路径和
        right = max(dfs(root.right), 0)
        # 更新整棵树的最大路径和
        self.max_path_sum = max(self.max_path_sum, left+right+root.val)
        # 处理当前节点 向上返回 以root为根节点的最大路径和=max(左，右)+root
        return max(left, right) + root.val
    dfs(root)
    return self.max_path_sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Leetcode236. 二叉树的最近公共祖先（⭐️⭐️⭐️⭐️⭐️最经典 高频、HOT100 腾讯）

这道题应该是二叉树最重要的一道题，很多公式都会考察，题目难度也比较高，一定要理解透，争取拿到就能秒杀。

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

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 
    # 典型的后序遍历
    # 函数返回：当前以root节点为根节点的树p或q的最近公共祖先
    # 递归出口1 空树了就不需要继续找了
    if not root: return None
    # 递归出口2 当前节点是p或者q 返回root 
    if root == p or root == q: return root
    # 去左右子树找p和q的最近公共祖先
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    # 处理当前节点的逻辑
    # 如果都不为空 那么root就是p和q的最近公共祖先
    if left and right: return root
    # 都为空 就返回None
    elif not left and not right: return None
    # left不为空  pq都在left 返回left
    # left为空    pq都在right 返回right
    else: return left if left else right  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.4、二叉树层次遍历

LeetCode199.二叉树的右视图（⭐️⭐️高频、剑指II）

LeetCode199.二叉树的右视图.

def rightSideView(self, root: TreeNode) -> List[int]:
    if not root: return []
    res, queue = [], [root]
    while queue:
        size = len(queue)
        for i in range(size):
            cur = queue.pop(0)
            if i == (size-1):
                res.append(cur.val)
            if cur.left: queue.append(cur.left)
            if cur.right: queue.append(cur.right)
    return res
1
2
3
4
5
6
7
8
9
10
11
12

剑指 Offer II 044. 二叉树每层的最大值（⭐️剑指II）

剑指 Offer II 044. 二叉树每层的最大值.

def largestValues(self, root: TreeNode) -> List[int]:
    if not root: return []
    res, queue = [], [root]
    while queue:
        size = len(queue)
        for i in range(size):
            # 这里也可以写arr 后面再用max(arr),但是这里为了节省空间 空间复杂度为O(1)
            if i == 0: max_val = float('-inf')
            cur = queue.pop(0)
            max_val = max(max_val, cur.val)
            if cur.left: queue.append(cur.left)
            if cur.right: queue.append(cur.right)
        res.append(max_val)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode103.二叉树的锯齿形层序遍历（⭐️高频）

LeetCode103.二叉树的锯齿形层序遍历.

def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
    if not root: return []
    res, queue = [], [root]
    i = 0
    while queue:
        arr, size = [], len(queue)
        for _ in range(size):
            cur = queue.pop(0)
            arr.append(cur.val)
            if cur.left: queue.append(cur.left)
            if cur.right: queue.append(cur.right)
        if i % 2 == 0: res.append(arr)  # 偶数行正序 
        else: res.append(arr[::-1])     # 奇数行逆序
        i += 1
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Leetcode101. 对称二叉树（⭐️⭐️高频、HOT100）

Leetcode101. 对称二叉树.

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    if not root: return True
    queue = [root]
    while queue:
        arr, size = [], len(queue)
        for i in range(size):
            cur = queue.pop(0)
            # 这里如果出现空 就加入‘#’
            if not cur: arr.append('#')
            else: arr.append(cur.val)
            if cur:
                queue.append(cur.left)
                queue.append(cur.right)
        if arr != arr[::-1]: return False
    return True 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

牛客.判断一棵树是否是完全二叉树（⭐️高频）

牛客.判断一棵树是否是完全二叉树.

下面不设限制，不管左子树和右子树是否为空，都加入queue中，如果是不是完全二叉树，那么在遍历到第一个None节点后，一定会再次遍历到下一个非None节点的，所以会return Fasle；而如果是完成二叉树的话，遍历到一个None节点后，后面queue的所有节点都是None，所以都会执行continue语句，最终结束循环返回True。这道题思路太棒了，这个continue简直用的太牛了！

class Solution:
    def judgeIt(self , root: TreeNode) -> List[bool]:
        print(self.isfull(root))   # [1,2,3,4] True   [1,3,2,#,5] False
        # write code here
    def isfull(self, root):
        if not root: return True
        flag = False
        queue = [root]
        while queue:
            cur = queue.pop(0)
            if not cur: 
                flag = True
                # 结束当前循环，不再执行后续的3行代码，继续进入while循环执行下一次循环
                continue
            if flag: return False
            queue.append(cur.left)
            queue.append(cur.right)
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.5、二叉搜索树

Leetcode235. 二叉搜索树的最近公共祖先（⭐️高频 腾讯）

Leetcode235. 二叉搜索树的最近公共祖先.

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root: return None
    if root == p or root == q: return root
    while root:
        if root.val  > p.val and root.val > q.val: 
            root = root.left
        elif root.val < p.val and root.val < q.val:
            root = root.right
        else: return root
1
2
3
4
5
6
7
8
9

剑指offer33: 二叉搜索树的后序遍历序列（⭐️高频）

剑指offer33: 二叉搜索树的后序遍历序列.

def verifyPostorder(self, postorder: List[int]) -> bool:
     if not postorder: return True
     # 找到第一个比root更大的节点i  root=后序最后一个节点
     for i in range(len(postorder)):
         if postorder[i] > postorder[-1]: break
     # i左边是左子树  i右边是右子树
     left = postorder[:i]
     right = postorder[i:-1]
     # 判断左子树是不是都比根节点小 右子树是不是都比根节点大
     for x in left:
         if x > postorder[-1]: return False
     for x in right:
         if x < postorder[-1]: return False
     # 再判断左子树和右子树是否满足条件
     return self.verifyPostorder(left) and self.verifyPostorder(right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.6、二叉树的修改构造

LeetCode105.从前序和中序遍历构造二叉树（⭐️⭐️⭐️高频、剑指II、HOT100）

LeetCode105.从前序和中序遍历构造二叉树.

b站讲解.

def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    if not preorder or not inorder: return None
    def dfs(preorder, inorder):
        if not preorder or not inorder: return None
        root = TreeNode(preorder[0])
        index = inorder.index(root.val)
        left = dfs(preorder[1:index+1], inorder[:index])
        right = dfs(preorder[index+1:], inorder[index+1:])
        root.left, root.right = left, right
        return root
    return dfs(preorder, inorder)
1
2
3
4
5
6
7
8
9
10
11

Leetcode 297.二叉树的序列化与反序列化（⭐️⭐️经典 高频、HOT100）

Leetcode 297.二叉树的序列化与反序列化.

    def serialize(self, root):
        """Encodes a tree to a single string. 
        前序遍历
        :type root: TreeNode
        :rtype: str
        """
        self.res = []
        def dfs(root):
            if not root: self.res.append('#')
            else:
                self.res.append(str(root.val))
                dfs(root.left)
                dfs(root.right)
        dfs(root)
        return ' '.join(self.res)  # str    1 2 # # 3 4 # # 5 # #

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        data = list(data.split(" "))  # ['1', '2', '#', '#', '3', '4', '#', '#', '5', '#', '#']
        def dfs():
            if data[0] == '#':
                data.pop(0)
                return None
            else:
                cur = TreeNode(data.pop(0))
                cur.left = dfs()
                cur.right = dfs()
                return cur
        return dfs()
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2.7、二叉树的递归思维

LeetCode572.另一个树的子树（⭐️高频）

LeetCode572.另一个树的子树

def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
    # 判断树root是否包含树subRoot
    def isSameTree(tree1, tree2):
        # 比较两棵树是否相同
        if not tree1 and not tree2: return True
        if not tree1 or not tree2: return False
        if tree1.val == tree2.val:
            return isSameTree(tree1.left, tree2.left) and isSameTree(tree1.right, tree2.right)
        else: return False
    if not root and not subRoot: return True
    if not root or not subRoot: return False
    # 两个都不为空
    # root是否和subRoot相等
    if isSameTree(root, subRoot): return True

    # root和subRoot不等 再看看root.left或者root.right是否和subRoot相等 
    return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.8、其他

LeetCode114. 二叉树展开为链表（技巧性题⭐️难 Hot100）

本来最简单的代码先前序遍历，将节点保存起来，再遍历创建链表，题目就很简单了，但是需要O(n)的空间复杂度。面试的时候肯定不能写成这样（实在写不出来也没办法，就写这个吧）。下面这种偏技巧性的思路，可以O(1)的空间复杂度，但是不容易想到。面试想到哪个用哪个吧。

LeetCode114. 二叉树展开为链表.

这道题有点技巧性 视频讲解.

def flatten(self, root: TreeNode) -> None:
     """
     Do not return anything, modify root in-place instead.
     """
     while root:
         if root.left:
             temp = root.left    # temp=2
             # 找到左子树的最右侧节点  4
             while temp.right:
                 temp = temp.right
             # 找到左子树最右侧节点 将其接到root的右子树之前  4->5之前
             temp.right = root.right
             # 再将root的左子树放到root右子树上  2—>1之后
             root.right = root.left 
             # root左子树为空  1的左子树为空
             root.left = None
         # 这就完成了将234插入道1和5之间了，也就是完成了第一步
         # 下面继续root=root.right  root=2 再一步步向下完成同样的操作
         root = root.right
     return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、回溯、DFS、BFS篇（10）

3.1、回溯

3.1.1、组合问题

LeetCode39: 组合总和（⭐️⭐️经典 HOT100）

LeetCode39. 组合总和

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
      # 无重复数字 找到所有和为target的不同组合
      # 同一个数字可以无限制重复被选取
      if not candidates: return []
      def dfs(start, path, res, candidates, target):
          if target == 0: 
              res.append(copy.deepcopy(path))
              return
          # 这里不加start的话就会每次都从头遍历 start就保证每次都从start位置开始遍历
          # 就会出现223 232的情况 就会重复了
          for i in range(start, len(candidates)):
              # 剪枝 小于target就不用进去了  因为target-candidates[i]肯定不等于0
              if candidates[i] <= target:
                  # 设置现场
                  path.append(candidates[i])
                  # 下一层的start=i 说明当前数字在后面dfs时还可以使用 允许一个数字重复使用
                  # 如 223  
                  dfs(i, path, res, candidates, target-candidates[i])
                  # 恢复现场
                  path.pop()
      path, res = [], []
      # candidates.sort()  没有重复数字 不用sort
      dfs(0, path, res, candidates, target)
      return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

LeetCode40: 组合总和II（⭐️⭐️⭐️经典 高频、HOT100）

LeetCode40: 组合总和II

 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
     if not candidates: return []
     def dfs(start, path, res, candidates, target):
         if target == 0: 
             res.append(copy.deepcopy(path[:]))
             return   # 不需要再向下找了
         # start防止出现116 161的现象
         for i in range(start, len(candidates)):
             if candidates[i] <= target:
                 # 一个数字在一个组合当中只能使用一次，所以i不能进入dfs 
                 # 否则同一个数就在这个组合当中出现两次了
                 # 防止出现112的情况
                 if i>start and candidates[i] == candidates[i-1]: 
                     continue
                 path.append(candidates[i])
                 # dfs的循环内是在一个组合
                 # 当前数字只能用一次（每个数字在每个组合中只能使用一次） 后面dfs不能使用 
                 # 防止出现225的情况
                 dfs(i+1, path, res, candidates, target-candidates[i])
                 path.pop()
     start = 0
     path, res = [], []
     # 这种集合中有重复数字都要sort
     candidates.sort()
     dfs(start, path, res, candidates, target)
     return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

LeetCode17. 电话号码的字母组合(⭐️HOT100）

LeetCode17. 电话号码的字母组合

def letterCombinations(self, digits: str) -> List[str]:
     if not digits: return []
     mapp = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno',
             '7':'pqrs', '8':'tuv', '9':'wxyz'}
     def dfs(index, path, res):
         if index == len(digits):
             res.append(''.join(path))
             return
         letters = mapp[digits[index]]
         for letter in letters:
             path.append(letter)
             dfs(index+1, path, res)
             path.pop()
     index = 0
     path, res = [], []
     dfs(index, path, res)   
     return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.1.2、子集问题

LeetCode78：子集（⭐️⭐️⭐️经典 高频、Hot100 腾讯）

LeetCode78. 子集

def subsets(self, nums: List[int]) -> List[List[int]]:
     if not nums: return []
     def dfs(start, path, res, nums):
         # 不需要任何判断 进来了就肯定是它的子集
         res.append(copy.deepcopy(path))
         for i in range(start, len(nums)):
             path.append(nums[i])
             # i+1：防止出现112 223的情况
             dfs(i+1, path, res, nums)
             path.pop()
     start = 0
     path, res = [], []
     dfs(start, path, res, nums)
     return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode90：子集II（⭐️⭐️⭐️经典 高频、Hot100）

LeetCode90：子集II

和组合总和II一样的思路

 class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []
        def dfs(start, path, res, nums):
            res.append(copy.deepcopy(path))
            for i in range(start, len(nums)):
                if i>start and nums[i] == nums[i-1]: continue
                path.append(nums[i])
                dfs(i+1, path, res, nums)
                path.pop()
        start = 0
        path, res = [], []
        nums.sort()
        dfs(start, path, res, nums)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode491: 递增子序列（⭐️高频）

LeetCode491: 递增子序列

 def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []
        def dfs(start, path, res, nums):
            if len(path) >= 2:
                res.append(copy.deepcopy(path))
                # 注意这里没有return了 因为子序列还可以继续向下找
            used = []  # 每一层都有一个used
            for i in range(start, len(nums)):
                # 去重操作 这里不能和子集一样sort 子序列要求是不能改变原始的相对位置
                # 所以这里用一个set来存放当前层已经用过哪些元素
                # 第二个条件保证递增
                if nums[i] in used or (len(path)>0 and path[-1]>nums[i]): continue 
                path.append(nums[i])
                used.append(nums[i])
                dfs(i+1, path, res, nums)
                path.pop()
        start = 0
        path, res = [], []
        dfs(start, path, res, nums)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.1.3、全排列问题

LeetCode46. 全排列（⭐️⭐️经典 HOT100 腾讯）

LeetCode46. 全排列

def permute(self, nums: List[int]) -> List[List[int]]:
     # 不包含重复数字的全排列
     if not nums: return []
     # 用used来全场记录我当前的排列用到了哪些元素  
     # 如果用了的话就continue 因为排列是不能重复的
     def dfs(path, res, nums, used):
         if len(path) == len(nums):
             res.append(copy.deepcopy(path))
             return
         for i in range(len(nums)):
             if nums[i] in used: continue
             path.append(nums[i])
             used.append(nums[i])
             dfs(path, res, nums, used)
             path.pop()
             used.pop()
     path, res = [], []
     used = []
     dfs(path, res, nums, used)
     return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode47: 全排列II（⭐️⭐️⭐️经典 高频、HOT100）

LeetCode47: 全排列II

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 包含重复数字的全排列
        if not nums: return []
        def dfs(path, res, nums, used):
            if len(path) == len(nums):
                res.append(copy.deepcopy(path))
                return
            for i in range(len(nums)):
                if used[i] == True:
                    continue
                if i>0 and nums[i]==nums[i-1] and used[i-1] == True:
                    continue
                path.append(nums[i])
                used[i] = True
                dfs(path, res, nums, used)
                path.pop()
                used[i] = False
        path, res = [], []
        # 注意这里的去重为什么用False这种形式 而不用set集合记录的形式
        # 因为这里的序列是可能有重复数字的 并不唯一 所以数字是不能代表某个位置数的
        used = [False for _ in range(len(nums))]
        nums.sort()
        dfs(path, res, nums, used)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.1.4、切割问题

LeetCode93: 复原IP地址（⭐️高频）

这道题需要注意下，一下子还真不一定写的对
LeetCode93: 复原IP地址

    def restoreIpAddresses(self, s: str) -> List[str]:
        if len(s)<4 or len(s)>12 or not s: return []
        def isMeeting(patch):
            # 长度不能小于1或者大于3
            if len(patch)<1 or len(patch)>3: return False
            # 长度大于1时不能以0开头
            if len(patch)>1 and patch[0]=='0': return False
            # 长度等于3时不能大于255
            if len(patch) == 3:
                count = int(patch[0])*100 + int(patch[1])*10 + int(patch[2]) 
                if count>255: return False
            return True
        def dfs(start, path, res, s, depth):
            if depth == 3:
                if isMeeting(s[start:]):
                    res.append('.'.join(path+[s[start:]]))
                    return
            for i in range(start, len(s)):
                if isMeeting(s[start:i+1]):
                    path.append(s[start:i+1])
                    dfs(i+1, path, res, s, depth+1)
                    path.pop()
        start = 0
        path, res = [], []
        depth = 0
        dfs(start, path, res, s, depth)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3.2、DFS和BFS

3.2.1、网格类问题

LeetCode200: 岛屿数量（⭐️⭐️⭐️经典 高频、HOT100）

LeetCode200: 岛屿数量

def numIslands(self, grid: List[List[str]]) -> int:
    if not grid: return 0
    row, col = len(grid), len(grid[0])
    def dfs(i, j):
        if i<0 or j<0 or i>=row or j>=col or grid[i][j] == '0': 
            return 
        grid[i][j] = '0'
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)

    res = 0
    for i in range(row):
        for j in range(col):
            if grid[i][j] == '1':
                res += 1
                dfs(i, j)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LeetCode695: 岛屿的最大面积（⭐️高频）

LeetCode695: 岛屿的最大面积

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
     if not grid: return 0
     row, col = len(grid), len(grid[0])
     def dfs(i, j):
         if i<0 or j<0 or i>=row or j>=col or grid[i][j]==0: return 0
         grid[i][j] = 0
         area = 1
         area += dfs(i+1, j)
         area += dfs(i-1, j)
         area += dfs(i, j+1)
         area += dfs(i, j-1)
         return area
     res = 0
     for i in range(row):
         for j in range(col):
             if grid[i][j] == 1:
                 res = max(res, dfs(i, j))
     return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode79. 单词搜索（⭐️HOT100）

LeetCode79. 单词搜索

def exist(self, board: List[List[str]], word: str) -> bool:
     row, col = len(board), len(board[0])
     if not row or not col: return False
     def dfs(i, j, index):  # 找第board[i][j]  找第word[index]个数
         if i<0 or i>=row or j<0 or j>=col or board[i][j] != word[index]: 
             return False
         if index == len(word)-1:  # 找到
             return True
         # index找到  找第index+1个数
         board[i][j] = ''  # 避免进入下一个dfs 这里又找一遍
         res = dfs(i+1,j,index+1) or dfs(i-1,j,index+1) or dfs(i,j+1,index+1) or dfs(i,j-1,index+1)
         board[i][j] = word[index]  # dfs完了 这里要恢复  之后可能还会遍历这里  
         return res
     for i in range(row):
         for j in range(col):
             if dfs(i, j, 0):  # 只要找到一个 就return true
                 return True
     return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.2.2、括号问题

LeetCode22. 括号生成（⭐️HOT100）

LeetCode22. 括号生成

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(left, right, path, res, n):
            # left: 左括号个数  right: 右括号个数
            # 递归出口 生成n对括号
            if left == n and right == n:
                res.append(path)
                return
            # 遍历当前层 相当于模板中的for
            # 条件1：左括号最多有n个 才能添加左括号
            if left < n:
                dfs(left+1, right, path+'(', res, n)
            # 条件2：左括号个数必须大于右括号个数才能添加右括号
            if left > right:
                dfs(left, right+1, path+')', res, n)
        left = right = 0
        path, res = '', []
        dfs(left, right, path, res, n)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.2.3、图问题

LeetCode207. 课程表（HOT100 难）

LeetCode207. 课程表

视频讲解1
视频讲解2

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 判断是否是有向无环图
        indegree = [0 for _ in range(numCourses)]  # 入度表
        # idx=0的列表存放着节点0的出度边对应的节点
        adjacency = [[] for _ in range(numCourses)]  # 邻接表
       
        # 填充连接表和入度表
        for node1, node2 in prerequisites:
            # node1: 接受  node2: 发出
            indegree[node1] += 1
            adjacency[node2].append(node1)
        
        queue = []  # 把入度为0的节点压入队列
        for i in range(len(indegree)):
            if indegree[i] == 0: queue.append(i)
        
        while queue:
            pop_node = queue.pop(0)
            numCourses -= 1
            for next_node in adjacency[pop_node]:
                indegree[next_node] -= 1
                if indegree[next_node] == 0: queue.append(next_node)
        return True if numCourses == 0 else False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

四、数组和哈希表

4.1、重建数组（高频）

适合用来删除数组中不符合要求的元素，如：删除0、输出有序数组中重复数字、删除指定数字target。

LeetCode283.移动零（HOT100）

LeetCode283.移动零

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        non_zero_index = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[non_zero_index] = nums[i]
                non_zero_index += 1
        for i in range(non_zero_index, len(nums)):
            nums[i] = 0
1
2
3
4
5
6
7
8
9
10
11
12

Leetcode26. 删除有序数组中的重复项（腾讯）

Leetcode26. 删除有序数组中的重复项

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        cur_idx = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                nums[cur_idx] = nums[i]
                cur_idx += 1
        return cur_idx
1
2
3
4
5
6
7
8

4.2、双指针

剑指offer21.调整数组顺序使奇数位于偶数前面（高频）

剑指offer21.调整数组顺序使奇数位于偶数前面

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        if len(nums) == 0 or len(nums) == 1: return nums
        left, right = 0, len(nums) - 1
        while left < right:
            while left < right and nums[left] % 2 == 1: left += 1
            while left < right and nums[right] % 2 == 0: right -= 1
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
        return nums
1
2
3
4
5
6
7
8
9
10
11

LeetCode11. 盛最多水的容器（HOT100 腾讯）

LeetCode11. 盛最多水的容器

class Solution:
    def maxArea(self, height: List[int]) -> int:
        if len(height) < 2: return 0
        left, right = 0, len(height) - 1
        max_v = 0
        while left < right:
            cur_v = min(height[left], height[right]) * (right - left)
            if cur_v > max_v:
                max_v = cur_v
            # 木桶效应 希望有更大的v 就必须移动较小边
            # 因为短的那边无法再优化了 如果此时不动短的，移动高的，两根柱子的距离又越来越小，那面积就更小了
            # 只有移动短的那边，虽然两者的距离短了，但可能还可以从高度上找回来 才有可能继续优化找到更大的water
            if height[left] < height[right]: left += 1
            else: right -= 1
        return max_v
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode15.三数之和（高频 HOT100 腾讯）

简单前题： LeetCode167. 两数之和 II - 输入有序数组

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        res = []
        while left < right:
            cur_sum = numbers[left] + numbers[right]
            if cur_sum == target: 
                return [left+1, right+1]
            elif cur_sum > target: right -= 1
            else: left += 1
1
2
3
4
5
6
7
8
9
10

LeetCode15.三数之和

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3: return []
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if nums[i] > 0: break  # nums[i]>0 后面也必>0 不存在相加为0的组合
            if nums[i] == nums[i-1] and i > 0: continue  # 剪枝 排除重复元素
            left = i + 1
            right = len(nums) - 1
            target = 0 - nums[i]
            while left < right:
                cur_sum = nums[left] + nums[right]
                if cur_sum == target and [nums[i], nums[left], nums[right]] not in res: 
                    res.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                elif cur_sum > target: right -= 1
                else: left += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode16.最接近的三数之和（腾讯）

LeetCode16.最接近的三数之和

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) < 3: return 0
        nums.sort()
        res = nums[0] + nums[1] + nums[2]
        for i in range(len(nums)-2):
            left, right = i + 1, len(nums) - 1
            while left < right:
                cur_sum = nums[i] + nums[left] + nums[right]
                if abs(cur_sum - target) < abs(res - target):
                    res = cur_sum
                # 等于的话 不用比了 
                if cur_sum == target: return cur_sum  
                elif cur_sum < target: left += 1
                else: right -= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode88.合并两个有序数组（高频 腾讯）

LeetCode88.合并两个有序数组

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        while m > 0 and n > 0:
            if nums1[m-1] > nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        # 如果nums2有剩余 n>0 直接插入nums1  没有剩余不执行nums[:0]
        nums1[:n] = nums2[:n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode75. 颜色分类（难 很有特点的一道双指针题 HOT100）

LeetCode75. 颜色分类
视频讲解

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # [0, p0) == 0   [p0, i) == 1  (p2, len(nums)-1] == 2
        p0, p2 = 0, len(nums) - 1  # 初始化三个区间都为空
        i = 0
        while i <= p2:   # i<=p2说明还有元素没看到
            if nums[i] == 0:
                nums[i], nums[p0] = nums[p0], nums[i]
                i += 1
                p0 += 1
            elif nums[i] == 1:
                i += 1
            else:
                nums[i], nums[p2] = nums[p2], nums[i]
                p2 -= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode4.寻找两个正序数组的中位数（难 没解开 高频 HOT100 腾讯）

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

1

4.3、哈希表

LeetCode217. 存在重复元素（腾讯）

LeetCode217. 存在重复元素

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        if len(nums) < 2: return False
        mapp = set()
        for i in range(len(nums)):
            if nums[i] not in mapp:
                mapp.add(nums[i])
            else: return True
        return False
1
2
3
4
5
6
7
8
9

LeetCode1.两数之和（高频 HOT100）

这道题第一想法是双指针，但是一看数组无序且这里不能排序，打扰了…

LeetCode1.两数之和

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_map = {nums[0]: 0}
        for i in range(1, len(nums)):
            if (target - nums[i]) in hash_map: return [i, hash_map[target-nums[i]]]
            hash_map[nums[i]] = i
1
2
3
4
5
6

LeetCode128.最长连续序列（高频 HOT100）

LeetCode128.最长连续序列

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_set = set(nums)  # {1, 2, 3, 100, 4, 200}
        max_len = 0
        for i in range(len(nums)):
            # 如果nums[i]-1以已经在集合中，那么这个数一定被数过了
            # 如果不在集合中，那么以该数为起点开始数
            if (nums[i]-1) not in nums_set:
                cur_start = nums[i]
                cur_len = 1
                while (cur_start + 1) in nums_set:
                    cur_start += 1
                    cur_len += 1
                max_len = max(max_len, cur_len)
        return max_len 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.4、原地哈希

模板

模板一：0 <= i <= len(nums)-1 时 0<= nums[i] <= len(nums)-1

# 实例 输入：[2, 3, 1, 0, 2, 5, 3]   输出：[0, 1, 2, 3, 2, 5, 3]
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # res = set(),这里具体情况具体分析  
        for i in range(len(nums)):
            # 如果nums[i]为任意数的话 
            while nums[i] != i:
                if nums[nums[i]] == nums[i]: 
                    # 操作,这里具体情况具体分析
                    # res.add(nums[i])
                    # break
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
        # 这段是查找异常的数字 nums[i] != i 
        for i in range(len(nums)):
            if nums[i] != i: return nums[i]
        # return res,这里具体情况具体分析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

模板二：0 <= i <= len(nums)-1 时 1<= nums[i] <= len(nums)

# 实例 输入：[3,1,3,4,2]   输出：[1, 2, 3, 4, 3]
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
    # def _swap(nums, index1, index2):
        #     nums[index1], nums[index2] = nums[index2], nums[index1]
        # res = set() 具体情况具体分析
        for i in range(len(nums)):
            while nums[i]-1 != i:
                if nums[nums[i]-1] == nums[i]:
                    # 具体情况具体分析
                    # res.add(nums[i])
                    # break
                # nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]  会陷入死循环
                # nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]  可以成功执行
                # 下面这种包在函数中写的写法 两种顺序都是成功的 建议用这种写法
                _swap(nums, i, nums[i]-1)
                # _swap(nums,nums[i]-1, i)
        # 这段是查找异常的数字 nums[i]-1 != i 
        for i in range(len(nums)):
            if nums[i]-1 != i: return nums[i]
        # return len(nums) 具体情况具体分析   

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

剑指offer03.数组中重复的数字（经典 高频）

长度为n的数组 存放0~n-1范围的数字，原地hash 让第i个位置存储i

剑指offer03.数组中重复的数字

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        # 长度为n的数组 存放0~n-1范围的数字  
        # 原地hash 让第i个位置存储i
        if len(nums) < 2: return -1
        for i in range(len(nums)):
            while nums[i] != i:
                # 如果当前的数和下标不对等 就找到了重复
                if nums[i] == nums[nums[i]]:
                    return nums[i]
                # 顺序只能这样
                nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode41.缺失的第一个正数（高频）

LeetCode41.缺失的第一个正数

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 时间复杂度O(n) 空间复杂度O(1)
        # 0的位置存放1  1放2...
        if len(nums) == 0: return 1
        for i in range(len(nums)):
            # 这里0放1 1放2 且nums数组元素没有限制条件 那么nums[i]需要限制范围
            while 1 <= nums[i] <= len(nums) and nums[i] - 1 != i:
                if nums[i] == nums[nums[i]-1]: break
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
        for i in range(len(nums)):
            if i+1 != nums[i]:
                return i + 1
        return len(nums) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.5、滑动窗口

LeetCode209.长度最小的子数组（高频）

LeetCode209.长度最小的子数组

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_len = float('inf')
        start, win_sum, wim_len = 0, 0, 0
        for end in range(len(nums)):
            # end往后移
            win_sum += nums[end]
            # start往前移 知道不满足条件
            while win_sum >= target:
                win_len = end - start + 1
                min_len = min(min_len, win_len)
                win_sum -= nums[start]
                start += 1
        return 0 if min_len == float('inf') else min_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode3. 无重复字符的最长子串（HOT100）

LeetCode3. 无重复字符的最长子串

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = 0
        max_len = 0
        mapp = set()
        for end in range(len(s)):
            while s[end] in mapp:
                mapp.remove(s[start])
                start += 1
            max_len = max(max_len, end-start+1)
            mapp.add(s[end])
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode76. 最小覆盖子串（HOT100）

LeetCode76. 最小覆盖子串

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        def isContains(window_dict, temp_dict):
            # 判断当前窗口的dict是否包含t的dict
            for each_key in temp_dict:
                if window_dict[each_key] < temp_dict[each_key]: return False
            return True
        temp_dict = defaultdict(int) # 存放t中的所有元素 key:val
        window_dict = defaultdict(int)  # 存放当前窗口所有元素
        for i in range(0, len(t)):
            temp_dict[t[i]] += 1
        start = 0
        min_len = float('inf')
        res = ""
        for end in range(len(s)):
            if s[end] in temp_dict:
                window_dict[s[end]] += 1   
            while isContains(window_dict, temp_dict):
                if min_len > (end - start + 1):
                    min_len = end - start + 1
                    res = s[start:end+1]
                if s[start] in window_dict:
                    window_dict[s[start]] -= 1
                start += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

4.6、旋转模拟

这类题目实实在在的模拟旋转过程，不涉及高深的算法，但是很考察代码功底。

LeetCode48. 旋转图像（HOT100）

LeetCode48. 旋转图像

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
             1、矩阵转置        2、行逆序
        1 2 3          1 4 7            7 4 1
        4 5 6   ->     2 5 8    ->      8 5 2
        7 8 9          3 6 9            9 6 3
        """
        n = len(matrix)
        for i in range(n):
            for j in range(i+1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] 
        # print(matrix)  [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
        for i in range(n):
            matrix[i][:] = matrix[i][::-1]
        return matrix  #  [[7,4,1],[8,5,2],[9,6,3]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode54. 螺旋矩阵（腾讯）

LeetCode54. 螺旋矩阵

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        m, n = len(matrix), len(matrix[0])
        # 四个边界 从左上角开始  x坐标轴向右 y坐标轴向下
        left, right, top, bottom = 0, n-1, 0, m-1
        count = 0
        while count < m*n:
            # 向右走
            for i in range(left, right+1):
                if count < m*n:
                    res.append(matrix[top][i])
                    count += 1
            top += 1
            # 向下走
            for i in range(top, bottom+1):
                if count < m*n:
                    res.append(matrix[i][right])
                    count += 1
            right -= 1
            # 向左走
            for i in range(right, left-1, -1):
                if count < m*n:
                    res.append(matrix[bottom][i])
                    count += 1
            bottom -= 1
            # 向上走
            for i in range(bottom, top-1, -1):
                if count < m*n:
                    res.append(matrix[i][left])
                    count += 1
            left += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

LeetCode59.螺旋矩阵II（高频 腾讯）

和上题差不多
LeetCode59.螺旋矩阵II

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        res = [[0 for _ in range(n)]for _ in range(n)]
        left, right, top, bottom = 0, n-1, 0, n-1
        count = 1
        while count <= n*n:
            # 向右走
            for i in range(left, right+1):
                if count <= n*n:
                    res[top][i] = count 
                    count += 1
            top += 1
            # 向下走
            for i in range(top, bottom+1):
                if count <= n*n:
                    res[i][right] = count 
                    count += 1
            right -= 1
            # 向左走
            for i in range(right, left-1, -1):
                if count <= n*n:
                    res[bottom][i] = count
                    count += 1
            bottom -= 1
            # 向上走
            for i in range(bottom, top-1, -1):
                if count <= n*n:
                    res[i][left] = count
                    count += 1
            left += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

LeetCode498.对角线遍历（难 高频）

对角线遍历规律：

1. 每一条对角线上横坐标和纵坐标的总和不变， 并且每一条对角线都是总和加1，也就是递增， 总和会从0开始增到m+n-2， m是矩阵的行数， n是矩阵的列数；
2. 当遍历对角线的时候，如果是从下往上走， 那么横坐标递减到0，而纵坐标递增到最大， 如果是从上往下走，纵坐标递减到0，横坐标递增到最大

LeetCode498.对角线遍历

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        # 每一个对角线的i+j相等 且 i + j < m+n-2 
        # 奇对角线 从下往上走 行i从最大->0  列j从0->最大   
        # 偶对角线 从上往下走 行i从0->最大  列j从最大->0
        m, n = len(mat), len(mat[0])
        cur_sum = 0
        res = []
        while cur_sum <= m+n-2:
            # 奇对角线 从下往上走 行i从最大->0  列j从0->最大（列=cur_sum-行）  
            # 左上半部分 最大行位cur_sum 右下半部分最大行为m-1
            if cur_sum < m: i = cur_sum
            else: i = m - 1
            j = cur_sum - i
            while i >= 0 and j <= n - 1:
                res.append(mat[i][j])
                i -= 1
                j += 1
            cur_sum += 1

            # 偶对角线 从上往下走 行i从0->最大  列j从最大->0（列=cur_sum-行） 
            # 左上半部分 最大列为cur_sum 右下半部分 最大列为n-1
            if cur_sum < n: j = cur_sum
            else: j = n - 1
            i = cur_sum - j
            while i <= m - 1 and j >= 0:
                res.append(mat[i][j])
                i += 1
                j -= 1
            cur_sum += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

4.7、其他

Leetcode7. 整数反转（腾讯）

Leetcode7. 整数反转

class Solution:
    def reverse(self, x: int) -> int:
        if x == 0: return 0
        if x > 0:
            flag = 1 
            s = str(x)
        else:
            flag = -1
            s = str(x)[1:]
        s = s[::-1]
        zero_index = 0
        for i in range(len(s)):
            if s[i] == '0': zero_index += 1
            else: break
        res = flag * int(s[zero_index:])
        return res if -2**31 <= res <= 2**31-1 else 0  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Leetcode43. 字符串相乘（腾讯）

Leetcode43. 字符串相乘

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == '0' or num2 == '0': return '0'
        num1, num2 = num1[::-1], num2[::-1]
        res = [0 for _ in range(len(num1)+len(num2)+1)]
        for i in range(len(num1)):
            for j in range(len(num2)):
                res[i+j] += int(num1[i]) * int(num2[j])
        for i in range(len(res)-1):
            res[i+1] += res[i] // 10
            res[i] %= 10
        while res and res[-1] == 0:
            res.pop()
        return ''.join(map(str, res[::-1]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Leetcode169. 多数元素（高频 HOT100 腾讯）

投票法
Leetcode169. 多数元素

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        res = nums[0]
        count = 1  
        for i in range(1, len(nums)):
            if count == 0:
                res = nums[i]
            # 如果是当前数字是目标数+1 不是目标数-1
            count += (1 if res == nums[i] else -1)
        return res
1
2
3
4
5
6
7
8
9
10

LeetCode31.下一个排列（高频 HOT100）

LeetCode31.下一个排列

文字讲解

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 从后往前 找到第一个升序的位置
        i = len(nums) - 2
        while i >= 0 and nums[i+1] <= nums[i]: 
            i -= 1
        # 从后往前 找到第一个比nums[i]大的数
        if i >= 0:
            j = len(nums) - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        print(nums[i+1:])
        # [i+1,end) 必然是降序 翻转 就是升序
        start, end = i + 1, len(nums) - 1
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

LeetCode8. 字符串转换整数（高频 腾讯）

LeetCode8. 字符串转换整数 (atoi)

class Solution:
    def myAtoi(self, s: str) -> int:
        if len(s) == 0: return 0
        MIN = -2**31
        MAX = 2**31-1

        # 丢弃前后空格
        s = s.strip()
        if len(s) == 0: return 0
        
        # 负数情况
        flag = False
        if s[0] == '-':
            flag = True
            s = s[1:]
        elif s[0] == '+':
            s = s[1:]
        res = 0
        for c in s:
            if '0' <= c <= '9':
                res = res * 10 + int(c)
            else: break
        if flag == True: res *= -1

        if res > MAX: return MAX
        if res < MIN: return MIN
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

五、二分查找（9）

模板

二分查找模板： 视频讲解

写法1:

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 异常判断
        if len(nums) == 0: return -1
        if nums[0] > target or nums[-1] < target : return -1
        # 开始搜， 事先假定target在闭区间[begin, end]
        left, right = 0, len(nums) - 1
        # 开始二分查找，这里使用排除法， 先排除不可能的区间，那么看循环结束条件变了
        # 注意此时不能有等于了，因为我们这里是排除不可能区间
        # 那么当begin==end的时候，此时只剩下一个元素，要么是我们要的，要么不是，但此时要退出，不用再找，已经得到结果
        while left < right:
            mid = left + (right - left) // 2   # 取左中位数
            # 这里不能判断等于的情况，因为我们用的排除思维，只需要排除目标一定不在的元素区间
            # 此时说明目标元素一定不在mid及其左边，排除掉
            if nums[mid] < target: left = mid + 1
            # 这是nums[mid] >= target的情况，说明目标在mid及左边, 往左缩小
            else: right = mid
        # 退出循环，要么找到，要么没找到，如果找到的话，left和right都指向它了
        return left if nums[left] == target else -1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

写法2：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 异常判断
        if len(nums) == 0: return -1
        if nums[0] > target or nums[-1] < target : return -1
        # 开始搜， 事先假定target在闭区间[begin, end]
        left, right = 0, len(nums) - 1
        # 开始二分查找，这里使用排除法， 先排除不可能的区间，那么看循环结束条件变了
        # 注意此时不能有等于了，因为我们这里是排除不可能区间
        # 那么当begin==end的时候，此时只剩下一个元素，要么是我们要的，要么不是，但此时要退出，不用再找，已经得到结果
        while left < right:
            mid = left + (right - left + 1) // 2    # 取右中位数
            # 这里不能判断等于的情况，因为我们用的排除思维，只需要排除目标一定不在的元素区间
            # 此时# 说明一定在左边了，此时排除掉mid及其右边
            if nums[mid] > target: right = mid - 1
            # 这是nums[mid] <= target的情况，# 说明在mid及其右边，所以排除掉左边
            else: left = mid 
        # 退出循环，要么找到，要么没找到，如果找到的话，left和right都指向它了
        return left if nums[left] == target else -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

写法3：这种写法不常用 只在leetcode33.搜索旋转排序数组中用到

def BinarySearch(nums, target):
	# 异常判断
	if len(nums) == 0:  return -1
	if target < nums[0] or target > nums[-1]: return -1

	# 开始搜， 注意我们假定target在一个闭区间[begin, end], 那么一开始的搜索范围
	begin, end = 0, len(nums) - 1         # 这个end最后一个元素所在位置，这时候搜索值肯定在这个闭区间中
	
	# 开始二分查找
	while begin <= end:   # [begin, end] 这里要注意是小于等于，当begin==end，区间[begin, end]依然有效
		
		mid = begin + (end - begin) // 2  # 这里要防止溢出现象，还有种更优雅的写法 mid = begin + ((end - begin) >> 1)

		if num[mid] == target:   # 这里找到目标值了, 返回位置
			return mid
		elif nums[mid] > target: # 说明target在mid左边，这时候搜索范围变为[begin, mid-1], 始终保持闭区间搜索
			end = mid - 1
		else:    # 说明target在mid右边， 这时候搜索范围[mid+1, end], 始终保持闭区间搜索
			begin = mid + 1
	
	# 退出循环的时候，说明没有找到元素，返回-1
	return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总结：

1. 第一种适合找元素的左边界；第二种适合找右边界

5.1、正常二分

LeetCode69.x的平方根（⭐️高频）

LeetCode69.x的平方根

def mySqrt(self, x: int) -> int:
     # 找小于等于x的平方根的最大值 找右边界
     left, right = 0, x//2+1
     while left < right:
         mid = left + (right - left + 1) // 2
         if mid * mid > x:
             right = mid - 1
         else:
             left = mid
     return left
1
2
3
4
5
6
7
8
9
10

LeetCode34.在排序数组中查找元素的第一个和最后一个位置（⭐️⭐️⭐️经典 高频、HOT100）

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

def searchRange(self, nums: List[int], target: int) -> List[int]:
     # 先找左边界 再找右边界
     res = [-1, -1]
     if not nums: return res
     left, right = 0, len(nums) - 1
     while left < right:
         mid = left + (right - left) // 2
         if nums[mid] < target:
             left = mid + 1
         else: 
             right = mid
     if nums[left] == target: res[0] = left
     left, right = 0, len(nums) - 1
     while left < right:
         mid = left + (right - left + 1) // 2
         if nums[mid] > target:
             right = mid - 1
         else:
             left = mid
     if nums[left] == target: res[-1] = left
     return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.2、二维矩阵类

LeetCode74.搜索二维矩阵（⭐️高频）

LeetCode74.搜索二维矩阵

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    # 二维转一维
    row, col = len(matrix), len(matrix[0])
    if row == 0 or col == 0: return False
    left, right = 0, row * col - 1
    while left < right:
        mid = left + (right - left) // 2
        if matrix[mid//col][mid%col] < target:
            left = mid + 1
        else:
            right = mid
    return matrix[left//col][left%col] == target
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode240.搜索二维矩阵II（⭐️⭐️高频、HOT100）

这道题虽然不是用传统的二分模板来做的，但是里面的思想其实还是上面二分模板的思想，一次次的排除不可能的区域，最后剩下的要么是最终的答案要么没有答案。

LeetCode240.搜索二维矩阵II

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    # 从右上角开始搜索 
    if len(matrix) == 0: return False
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target: return True
        elif matrix[row][col] > target: col -= 1
        else: row += 1
    return False
# 这道题也可以左下角开始搜索
1
2
3
4
5
6
7
8
9
10

5.3、旋转数组类

LeetCode33.搜索旋转排序数组（⭐️⭐️⭐️经典 难 高频、HOT100 腾讯）

唯一一道用到模板3的题目

LeetCode33.搜索旋转排序数组

def search(self, nums: List[int], target: int) -> int:
    if not nums: return -1
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target: return mid
        elif nums[mid] > nums[right]:  
            # 左边有序
            if nums[left] <= target and target < nums[mid]:   # target在左边 不包括mid
                right = mid - 1
            else:
                left = mid + 1
        else:
            # 右边有序
            if nums[mid] < target and target <= nums[right]:   # 在右边  不包括mid
                left = mid + 1
            else:
                right = mid - 1
    return -1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LeetCode153.搜索旋转数组的最小值（⭐️⭐️难 高频）

LeetCode153.搜索旋转数组的最小值

b站视频讲解

这道题技巧性优点重啊

def findMin(self, nums: List[int]) -> int:
     if len(nums) == 1: return nums[0]
     # 数组元素不重复
     left, right = 0, len(nums) - 1
     while left < right:
         mid = left + (right - left) // 2
         # [3,4,5,1,2]  
         # mid>right 说明[left,mid]是单调递增的，[mid+1,right]可能单调递减可能不单调 
         # 所以最小值肯定不在[left,mid]中  
         if nums[mid] > nums[right]:
             left = mid + 1
         else:
             right = mid
     return nums[left]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这道题还有道进阶题：数组元素重复。有重复元素，如果是连续的话，是没有关系的，这个模板还是可以找到最小元素，但是如果有重复元素，且分在mid左边两边，如：[1,0,1,1,1]

154. 寻找旋转排序数组中的最小值 II

视频讲解

def findMin(self, nums: List[int]) -> int:
     if len(nums) == 1: return nums[0]
     left, right = 0, len(nums) - 1
     while left < right:
         mid = left + (right - left) // 2
         if nums[mid] > nums[right]:
             left = mid + 1
         elif nums[mid] == nums[right]:
             # 没有任何意义 只是为了让程序不错的继续运行下去
             # 因为mid=right,即使right就是最小值且right-=1,此时最小值也还在数组中=mid
             right -= 1
             continue
         else:
             right = mid
     return nums[left]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.4、找极大、极小值

LeetCode162.寻找峰值/极大值（⭐️高频）

LeetCode162.寻找峰值
视频讲解

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # 方法1、直接返回最大值 O(n) 找到1个极值
        # 方法2、贪心 O(n)  找到所有极值
        if len(nums) < 2: return 0
        pre, cur = 0, 0
        res = []
        # nums 看成 [-无穷大] + nums + [无穷大]
        for i in range(1, len(nums)):
            cur = nums[i] - nums[i-1]
            # 极大值
            if cur < 0 and pre >= 0:
                res.append(i-1)
                pre = cur
            # # 极小值
            # if cur > 0 and pre < 0:
            #     res.append(i-1)
            #     pre = cur
            
            # # 极值
            # if (cur < 0 and pre >= 0) or (cur > 0 and pre < 0):
            #     res.append(i-1)
            #     pre = cur
        if cur > 0: res.append(len(nums)-1)
        return res[0]

        # 方法3、二分法 O(logn)  找到某个极值
        # 这道题之所以可以用二分 主要是因为nms[-1] = nums[n] = -∞
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[mid+1]:
                left = mid + 1
            else:
                right = mid 
        return left 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

5.5、其他

寻找两个正序数组的中位数（⭐️⭐️⭐️经典 难 HOT100）

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

题目视频讲解
题目精彩文字讲解

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 对两个数组同时用二分法  中位数=特殊的找两个数组第k小的元素 
        # 每次一半一半的删除，找第k小，那我一次就可以排除掉k/2的元素
        def getKth(start1, end1, start2, end2, k):
            len1, len2 = end1 - start1 + 1, end2 - start2 + 1
            # 让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
            if len1 == 0:
                return nums2[start2+k-1]
            if len2 == 0:
                return nums1[start1+k-1]
            if k == 1:
                return min(nums1[start1], nums2[start2])
            i = start1 + min(len1, k//2) - 1
            j = start2 + min(len2, k//2) - 1

            if nums1[i] > nums2[j]:
                return getKth(start1, end1, j+1, end2, k-(j-start2+1))
            else:
                return getKth(i+1, end1, start2, end2, k-(i-start1+1))
        m, n = len(nums1), len(nums2)
        left = (m+n+1) // 2
        right = (m+n+2) // 2
        # 将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k
        return (getKth(0, m-1, 0, n-1, left) + getKth(0, m-1, 0, n-1, right)) / 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

LeetCode287. 寻找重复数（⭐️HOT100）

LeetCode287. 寻找重复数

题解

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left, right = 1, len(nums) - 1
        while left <= right:
            count = 0
            mid = left + (right - left) // 2
            for i in range(len(nums)):
                if nums[i] <= mid:
                    count += 1
            if count > mid:
                right = mid - 1
            else:
                left = mid + 1
        return left
1
2
3
4
5
6
7
8
9
10
11
12
13
14

六、栈和队列（9）

6.1、普通栈

LeetCode20 有效的括号（⭐️⭐️⭐️基础题 经典 高频、HOT100 腾讯）

LeetCode20 有效的括号

def isValid(self, s: str) -> bool:
      if not s: return True
      mapp = {'(': ')', '[': ']', '{': '}'}
      stack = []
      for i in range(len(s)):
          if s[i] in mapp:  # 左括号
              stack.append(s[i])
          else:  # 右括号
              # 如果此时stack没有括号了 reture False
              if not stack: return False
              # 出栈匹配  
              top = stack.pop()
              # 不匹配 return False
              if mapp[top] != s[i]:
                  return False
      # 最后栈不为空 左括号太多了 return False
      return True if not stack else False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode155. 最小栈（⭐️⭐️基础题 高频、HOT100 腾讯）

LeetCode155. 最小栈

class MinStack:
    def __init__(self):
        self.stack = []
        # 维护最小元素 一直append更小的元素 minStack[-1]就是最小元素
        self.minStack = [] 

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.minStack:
            self.minStack.append(val)
        else:
            min_value = min(val, self.minStack[-1])
            self.minStack.append(min_value)

    def pop(self) -> None:
        self.stack.pop()
        self.minStack.pop()

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


    def getMin(self) -> int:
        return self.minStack[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

LeetCode232. 用栈实现队列（⭐️基础题 高频）

LeetCode232. 用栈实现队列

视频讲解

class MyQueue:

    def __init__(self):
        # 栈：先进后出
        # 队列：先进先出
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        self.stack_in.append(x)

    def pop(self) -> int:
        if self.stack_out:
            return self.stack_out.pop()
        else:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()

    def peek(self) -> int:
        if self.stack_out:
            return self.stack_out[-1]
        else:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out[-1]


    def empty(self) -> bool:
        return not self.stack_in and not self.stack_out 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

LeetCode394. 字符串解码（⭐️经典 Hot100）

LeetCode394. 字符串解码

def decodeString(self, s: str) -> str:
    # 括号匹配的问题->第一想法就应该是栈（最值问题除外 最值问题很可能是dp）
    stack = []
    res = ""
    multi = 0
    for c in s:
        if 'a' <= c <= 'z':
            res += c  
        elif '0' <= c <= '9':
            multi = multi * 10 + int(c)  # 重复次数
        elif c == '[':
            # 把当前重复次数 和 当前马上要重复元素前面的所有字母压入栈
            stack.append([multi, res])  
            multi, res = 0, ''
        else:
            # 重复次数  前面的字母
            cur_multi, last_res = stack.pop()
            res = last_res + cur_multi * res
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6.2、单调栈（每一题都要掌握）

LeetCode739. 每日温度（⭐️Hot100）

LeetCode739. 每日温度

def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    # 实质：找到右侧第一个比当前元素大的数
    length = len(temperatures)
    if length == 0: return []
    if length == 1: return [0]
    stack = []   # 单调递减栈
    res = [0] * length
    for i in range(length):
        # 栈不为空 且 开始上升
        while stack and temperatures[i] > temperatures[stack[-1]]:
            # 找到第一个大于栈顶的原素  res赋值  出栈
            res[stack.pop()] = i - stack[-1]
        # stack为空直接入栈  降序直接入栈
        stack.append(i)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

下面的几道题差不多就是739的进阶版本了。

LeetCode84. 柱状图中最大的矩形（⭐️⭐️⭐️经典 难 高频、HOT100）

LeetCode84. 柱状图中最大的矩形

视频讲解

def largestRectangleArea(self, heights: List[int]) -> int:
     # 本质：找每个元素左右两边第一个比它小的元素
     #      当前元素的高已经确定  找到当前元素往后的第一个比它小的数  再结合单调递增栈
     #      就找到了当前元素左右两边第一个比它小的数了  一减就是宽   宽x高就是当前元素为高的最大面积
     if not heights: return 0
     if len(heights) == 1: return heights[0]
     stack = []  # 维护单调递增栈
     heights = [0] + heights + [0]    # 在index=0和末尾插入0
     max_area = 0  
     for i in range(len(heights)):
         # 不满足单调栈 就找到栈顶原始右边第一个比它小的数
         while stack and heights[i] < heights[stack[-1]]:
             h = heights[stack.pop()]
             # if not stack: break  # 这里不可能  栈里永远会有一个0  
             w = i - stack[-1] - 1
             max_area = max(max_area, h * w)
         # 栈为空 或 满足单调栈 入栈
         stack.append(i)
     return max_area
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LeetCode85. 最大矩形（⭐️⭐️经典 难 HOT100）

这道题基本就是上题一样的解法
LeetCode85. 最大矩形

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        def get_heights(arr, heights):  
            # 根据上一层的heights求当前层的heights
            for i in range(len(arr)):
                if arr[i] == '0':
                    heights[i] = 0
                else:
                    heights[i] += 1
            return heights
        def largestRectangleArea(heights):
            # 求柱状图中最大的矩形 和84一模一样
            stack = []  # 单调递增栈
            maxArea = 0
            heights = [0] + heights + [0]
            for i in range(len(heights)):
                while stack and heights[i] < heights[stack[-1]]:
                    h = heights[stack.pop()]
                    w = i - stack[-1] - 1
                    maxArea = max(maxArea, h*w)
                stack.append(i)
            return maxArea
        # 把二维矩形才成一个个的一位矩形 判断最大面积
        max_area = 0
        for i in range(len(matrix)):
            if i == 0:
                heights = list(map(int, matrix[i]))
            else:
                heights = get_heights(matrix[i], heights)
            
            cur_row_max_area = largestRectangleArea(heights)
            max_area = max(max_area, cur_row_max_area)
        return max_area
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

LeetCode42. 接雨水（⭐️⭐️⭐️经典 难 高频、HOT100）

LeetCode42. 接雨水

视频讲解 42. 接雨水 Trapping Rain Water 【LeetCode 力扣官方题解】

def trap(self, height: List[int]) -> int:
     # 木头效应：每个位置接到的最多雨水=(min(左侧第一个大于，右侧第一个大于)-当前位置的高度) * 宽度
     # 问题就转换为如何求左侧第一个和右侧第一个高于当前元素的位置
     if not height: return 0
     if len(height) <= 2: return 0
     stack = []   # 维护一个单调递减栈  存储柱子的下标
     res = 0
     for i in range(len(height)):
         # 找到右侧第一个比当前元素大的  左边第一个刚好在单调栈中
         while stack and height[i] > height[stack[-1]]:
             cur = height[stack.pop()]  # 当前元素的高度
             if not stack: break
             h = min(height[stack[-1]], height[i]) - cur
             res += h * (i - stack[-1] - 1)
         # 栈为空 或 满足单调栈 入栈
         stack.append(i)
     return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

6.3、单调队列

Leetcode239. 滑动窗口最大值（⭐️⭐️⭐️经典 难 高频 HOT100）

Leetcode239. 滑动窗口最大值

文字题解

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
     # 单调递减的双端队列  队首是当前区间的最大元素 
     # 每次加入元素 将队列小于这个元素的所有元素移出
     if not nums: return []
     queue = []  # 单调递减队列
     res = []    
     for i in range(len(nums)):
         # 队列不为空 且当前元素大于队尾元素
         while queue and nums[queue[-1]] < nums[i]:
             # 删除队尾元素
             queue.pop()  
         # 当前元素加入
         queue.append(i)
         # 判断窗口大小 判断队首元素还在不在窗口之内
         # 通过i的值来判断当前窗口的状态
         if i - queue[0] + 1 > k:
             queue.pop(0)
         # 窗口形成之后，队首元素就是每个窗口的最大值
         # 窗口没形成就判断值 append 进queue即可
         # 通过i的值来判断当前窗口的状态
         if i + 1 >= k:
             res.append(nums[queue[0]])
     return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

七、排序（5）

7.1、堆排序

笔记

适合解决前k个、第k个这种不需要整个数组排序，只用排一部分的题目。

堆排序特点：

1. 完全二叉树+所有父节点val>子节点val
2. 节点i的父节点=（i-1）// 2，两个子节点c1=2i+1、c2=2i+2

视频讲解堆排序.

自己实现堆排序（堆排序手撕）：

# 最大堆
def heapify(tree, n, i):  # tree[i]为根节点的子树进行堆排序
            c1 = 2 * i + 1
            c2 = 2 * i + 2
            max_index = i  # 小顶堆这里改下
            if c1 < n and tree[c1] > tree[max_index]:  # 小顶堆这里改下
                max_index = c1
            if c2 < n and tree[c2] > tree[max_index]:
                max_index = c2
            if max_index != i:
                tree[max_index], tree[i] = tree[i], tree[max_index]
                # max_index和i作了交换，所以max_index分支需要重新整理为大顶堆
                heapify(tree, n, max_index)
def build_heap(tree, n):   # 从parent->0节点分别进行一次堆排序 就建立了这个树的堆
    last_node = n - 1  
    parent = (last_node - 1) // 2 
    for i in range(parent, -1, -1):
        heapify(tree, n, i)
def heap_sort(tree, n):
    build_heap(tree, n)
    for i in range(n-1, -1, -1):
        tree[i], tree[0] = tree[0], tree[i]
        heapify(tree, i, 0)
heap_sort(nums, len(nums))   # [3,2,1,5,6,4]
print(nums)  #  [1, 2, 3, 4, 5, 6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

调包实现：

heapq.heapify(nums)   # 第一种掉包排序实现（建立最小堆）
hp = []
for num in nums:      # 第二种掉包堆排序实现（建立最小堆）
    heapq.heappush(hp, num)   # push进一个元素 堆还是维护小顶堆

min_val = heapq.heappop()  # 弹出堆顶元素（最小值） 堆还是维护小顶堆
1
2
3
4
5
6

LeetCode215.数组中的第K个最大元素（⭐️⭐️⭐️高频、HOT100 腾讯）

LeetCode215.数组中的第K个最大元素

def findKthLargest(self, nums: List[int], k: int) -> int:
    # 1、堆排序手写实现 
    #    小顶堆  第k大、前k大建小顶堆；第k小、前k小建大顶堆
    def heapify(tree, n, i):
        c1, c2 = 2 * i + 1, 2 * i + 2
        min_idx = i
        if c1 < n and tree[c1] < tree[min_idx]:
            min_idx = c1
        if c2 < n and tree[c2] < tree[min_idx]:
            min_idx = c2
        if min_idx != i:
            tree[i], tree[min_idx] = tree[min_idx], tree[i]
            heapify(tree, n, min_idx)
    def build_heap(tree, n):
        last_node = n - 1
        parent = (last_node - 1) // 2
        for i in range(parent, -1, -1):
            heapify(tree, n, i)
    hp = nums[:k]
    build_heap(hp, k)
    for i in range(k, len(nums)):
        if nums[i] > hp[0]:
            hp[0] = nums[i]
            heapify(hp, k, 0)
    return hp[0]
    
    # 2、堆排序掉包实现
    #    第k大、前k大建小顶堆；第k小、前k小建大顶堆
    hp = nums[:k]
    heapq.heapify(hp)  # 建堆
    # 遍历k后面的树 如果发现比堆顶元素大 那么就把堆顶元素换掉
    for i in range(k, len(nums)):
        # 小顶堆最终保存前k大的数  
        if nums[i] > hp[0]:
            heapq.heappop(hp)  # pop出堆顶元素 堆还是维护小顶堆
            heapq.heappush(hp, nums[i])  # push进一个元素 堆还是维护小顶堆
    return hp[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

面试题 17.14. 最小K个数（⭐️高频）

面试题 17.14. 最小K个数

    def smallestK(self, arr: List[int], k: int) -> List[int]:
        # 1、手撕最大堆
        if k == 0 or len(arr) == 0: return []
        def heapify(tree, n, i):
            c1, c2 = 2*i+1, 2*i+2
            max_idx = i
            if c1 < n and tree[c1] > tree[max_idx]:
                max_idx = c1 
            if c2 < n and tree[c2] > tree[max_idx]:
                max_idx = c2
            if max_idx != i:
                tree[max_idx], tree[i] = tree[i], tree[max_idx]
                heapify(tree, n, max_idx)
        def build_heap(tree, n):
            last_node = n - 1
            parent = (last_node - 1) // 2
            for i in range(parent, -1, -1):
                heapify(tree, n, i)
        hp = arr[:k]
        build_heap(hp, k)
        for i in range(k, len(arr)):
            # 大顶堆 最终保留最小的k个数 
            if arr[i] < hp[0]:
                hp[0] = arr[i]
                heapify(hp, k, 0)
        return hp
            
        # 2、调包 小顶堆 取反 转换为大顶堆
        if len(arr) == 0 or k == 0: return []
        # 最小堆  存储-x 
        hp = [-x for x in arr[:k]]
        heapq.heapify(hp)
        for i in range(k, len(arr)):
            # 小顶堆最终保留前k大的数（-x）
            # 也就保存了前k小的数（x）
            if -arr[i] > hp[0]:
                heapq.heappop(hp)
                heapq.heappush(hp, -arr[i])
        return [-x for x in hp]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

Leetcode347. 前 K 个高频元素（⭐️⭐️HOT100）

Leetcode347. 前 K 个高频元素

这道题掉包不是很好搞

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
     if k == 0 or len(nums) == 0: return []
     def heapify(tree, n, i):
         c1, c2 = 2 * i + 1, 2 * i + 2
         min_idx = i
         if c1 < n and tree[c1][1] < tree[min_idx][1]:
             min_idx = c1
         if c2 < n and tree[c2][1] < tree[min_idx][1]:
             min_idx = c2
         if min_idx != i:
             tree[i], tree[min_idx] = tree[min_idx], tree[i]
             heapify(tree, n, min_idx)
     def build_heap(tree, n):
         last_node = n - 1
         parent = (last_node - 1) // 2
         for i in range(parent, -1, -1):
             heapify(tree, n, i)
     mapp = defaultdict(int)
     for i in range(len(nums)):
         mapp[nums[i]] += 1
     arr = list(mapp.items())  # [(1, 3), (2, 2), (3, 1)]
     # 前k个树建立小顶堆
     hp = arr[:k]
     build_heap(hp, k)
     # pop出前面小的数  剩下在hp中的k个数就是最大的前K个数
     for i in range(k, len(arr)):
         if arr[i][1] > hp[0][1]:
             hp[0] = arr[i]
             heapify(hp, k, 0)
     return [x[0] for x in hp]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

7.2、快排

笔记

快排手撕

def Quick_Sort(self, nums: List[int]) -> str:
     # 思想：小于idx的数放在idx左边  大于idx的数放在idx右边
     def quick_sort(nums, left, right):
         # 如果只有一个元素了，返回
         if left >= right: return 
         temp = left  # 中轴  下面交换过程中中轴的数不变
         i, j = left, right
         while i < j:
             # 从右边找比中轴小的数
             while i < j and nums[j] > nums[temp]:  
                 j -= 1
             # 从左边找比中轴大的数  
             while i < j and nums[i] <= nums[temp]:
                 i += 1
             # 交换
             nums[i], nums[j] = nums[j], nums[i]
         # 把中轴放到有序的位置上， 使得左边的元素小于中轴，右边的元素大于中轴 i=j
         nums[temp], nums[i] = nums[i], nums[temp]
         # 递归中轴左边和中轴右边快排
         quick_sort(nums, left, i-1)
         quick_sort(nums, i+1, right)
     a = [3, 2, 5, 9, 1]
     quick_sort(a, 0, len(a)-1)
     return a  # [1, 2, 3, 5, 9]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Leetcode179. 最大数（⭐️高频）

这道题有个相似的前提 剑指 Offer 45. 把数组排成最小的数

def minNumber(self, nums: List[int]) -> str:
    if not nums: return ""
    def quick_sort(nums, left, right):
        if left >= right: return 
        temp, i, j = left, left, right
        # 从小到大排列
        while i < j:
            # 右边碰到比它大  j-=1
            while i < j and (nums[j]+nums[temp]) > (nums[temp]+nums[j]):
                j -= 1
            # 左边碰到比它小  i+=1
            while i < j and (nums[i]+nums[temp]) <= (nums[temp]+nums[i]):
                i += 1
            nums[i], nums[j] = nums[j], nums[i]
        nums[temp], nums[i] = nums[i], nums[temp]
        quick_sort(nums, left, i-1)
        quick_sort(nums, i+1, right)
    nums = list(map(str, nums))   # [10,2] -> ['10', '2']
    quick_sort(nums, 0, len(nums)-1)
    return ''.join(nums)  # ["10","2"] -> "102"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Leetcode179. 最大数

    def largestNumber(self, nums: List[int]) -> str:
        if not nums: return ""
        def quick_sort(nums, left, right):
            if left >= right: return 
            temp, i, j = left, left, right
            while i < j:
                # 从大到小排列(比的是第一个数字的大小)
                # 右边碰到比它小  j-=1
                while i < j and (nums[j]+nums[temp]) < (nums[temp]+nums[j]):
                    j -= 1
                # 左边碰到比它大  i+=1
                while i < j and (nums[i]+nums[temp]) >= (nums[temp]+nums[i]):
                    i += 1
                nums[i], nums[j] = nums[j], nums[i]
            nums[temp], nums[i] = nums[i], nums[temp]
            quick_sort(nums, left, j-1)
            quick_sort(nums, j+1, right)
        nums = list(map(str, nums))   # [10,2] -> ['10', '2']
        quick_sort(nums, 0, len(nums)-1)
        non_zero_loc = 0
        while non_zero_loc < len(nums)-1 and nums[non_zero_loc] == '0':
            non_zero_loc += 1
        return ''.join(nums[non_zero_loc:])  # ["10","2"] -> "102"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7.3、归并排序

笔记

核心是分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。归并排序将分治的思想体现得淋漓尽致。

一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。

归并手撕

def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
     def merge(left, right):
         # 合并两个有序数组
         m, n = len(left), len(right)
         merge_arr = [0 for _ in range(m+n)]
         # 从后往前遍历，进行合并
         while m and n:
             if left[m-1] > right[n-1]:
                 merge_arr[m+n-1] = left[m-1]
                 m -= 1
             else:
                 merge_arr[m+n-1] = right[n-1]
                 n -= 1
         if m:
             merge_arr[:m] = left[:m]
         if n:
             merge_arr[:n] = right[:n]
         return merge_arr
     def merge_sort(nums):
         if len(nums) <= 1: return nums
         mid = len(nums) // 2
         left = merge_sort(nums[:mid])
         right = merge_sort(nums[mid:])
         return merge(left, right)
     nums = [4,2,3,6,1,7]
     nums = merge_sort(nums)   
     print(nums)  # [1, 2, 3, 4, 6, 7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

归并排序的典型应用就是链表排序。

LeetCode148: 排序链表（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def merge(self, left, right):
        dummy = ListNode(-1)
        rear = dummy
        p, q = left, right
        while p and q:
            if p.val <= q.val:
                rear.next = p
                p = p.next
            else:
                rear.next = q
                q = q.next
            rear = rear.next
        rear.next = p if p else q
        return dummy.next 
        
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        # 找到链表中点
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 偶数个节点 fast=链表最后一个节点 slow指向前半部分节点的最后一个
        # 奇数个节点 fast=null slow指向中间节点

        # 把链表切成两部分，再对这俩个部分进行排序
        mid = slow.next
        slow.next = None
        left, right = self.sortList(head), self.sortList(mid)

        # 最后将两个排序链表合并为一个有序链表
        return self.merge(left, right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

八、动态规划（33）

视频讲解：理解动态规划

8.1、普通动规系列

LeetCode343. 整数拆分（⭐️高频）

LeetCode343. 整数拆分

def integerBreak(self, n: int) -> int:
    if n < 3: return 1
    # dp[i]表示当前第i个数能拆成k（k>=2）个数的和，这k个数的最大乘积
    dp = [0 for _ in range(n+1)]
    dp[1] = 1
    dp[2] = 1
    for i in range(3, n+1):
        for j in range(1, i):
            # 1、直接拆成2个数   最大乘积=j*(i-j)
            # 2、拆成2个以上的数 最大乘积=j*dp[i-j]
            dp[i] = max(dp[i], j*(i-j), j*dp[i-j])
    return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode70. 爬楼梯（⭐️Hot100 腾讯）

LeetCode70. 爬楼梯

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2: return n
        # dp[i]表示爬到i阶有dp[i]种方法
        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n+1):
            # 第i阶可以来自i-1阶梯再走一步 或 i-2阶梯再走两步
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11

LeetCode96. 不同的二叉搜索树(思路清奇）

LeetCode96. 不同的二叉搜索树

视频讲解

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2: return n
        # dp[i]表示爬到i阶有dp[i]种方法
        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n+1):
            # 第i阶可以来自i-1阶梯再走一步 或 i-2阶梯再走两步
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11

8.2、路径规划系列

LeetCode62. 不同路径（⭐️Hot100 腾讯）

LeetCode62. 不同路径

def uniquePaths(self, m: int, n: int) -> int:
    if m == 0 or n == 0: return 0
    # dp[i][j]表示到达第i-1行第j-1列位置的路径个数
    dp = [[0 for _ in range(n)]for _ in range(m)]
    for i in range(m): dp[i][0] = 1
    for j in range(n): dp[0][j] = 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10

LeetCode63. 不同路径 II（⭐️高频）

LeetCode63. 不同路径 II

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
     m, n = len(obstacleGrid), len(obstacleGrid[0])
     if m == 0 or n == 0 or not obstacleGrid: return 0
     # dp[i][j]表示到达第i-1行第j-1列位置的路径个数
     dp = [[0 for _ in range(n)]for _ in range(m)]
     for i in range(m):
         # 如果出现一个障碍 后面就不用比较了 全是0
         if obstacleGrid[i][0] == 1: break
         dp[i][0] = 1
     for j in range(n):
         # 如果出现一个障碍 后面就不用比较了 全是0
         if obstacleGrid[0][j] == 1: break
         dp[0][j] = 1
     for i in range(1, m):
         for j in range(1, n):
             # 如果当前位置出现障碍，当前位置路径个数=0
             if obstacleGrid[i][j] == 1: dp[i][j] = 0
             # 否则 正常计算
             else: dp[i][j] = dp[i-1][j] + dp[i][j-1]
     return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode64.最小路径和（⭐️⭐️⭐️高频 Hot100）

LeetCode64.最小路径和

def minPathSum(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    if m == 0 or n == 0 or not grid: return 0
    # dp[i][j]表示从左上角到达grid[i][j]位置的路径总和最小值
    dp = copy.deepcopy(grid)
    for i in range(1, m): 
        dp[i][0] += dp[i-1][0]
    for j in range(1, n):
        dp[0][j] += dp[0][j-1]
    for i in range(1, m):
        for j in range(1, n):
            # 当前位置最小路径和=min(左边最小路径和，上面最小路径和)+当前位置值
            dp[i][j] += min(dp[i-1][j], dp[i][j-1])
    return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode221. 最大正方形（Hot100）

LeetCode221. 最大正方形

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        # dp[i][j]表示以(i,j)为右下角形成的正方形的最大边长是多少
        dp = [[0 for _ in range(n)]for _ in range(m)]
        max_edge = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        # 为什么是min?
                        # 当前位置的元素值等于三个相邻位置的元素中的最小值加 1
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    max_edge = max(max_edge, dp[i][j])
        return max_edge ** 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

8.3、打家劫舍系列

LeetCode198. 打家劫舍（⭐️⭐️Hot100）

LeetCode198. 打家劫舍

def rob(self, nums: List[int]) -> int:
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    if len(nums) == 2: return max(nums[0], nums[1])
    # dp[i]表示前i家能抢的最高金额
    dp = [0 for _ in range(len(nums))]
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        # 1、不抢第i家 那么前i家抢的最高金额=前i-1抢的最高金额
        # 2、抢第i家，那么前i家抢的最高金额=前i-1家抢的最高金额+第i家的金额
        dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode213. 打家劫舍 II（⭐️⭐️高频）

LeetCode213. 打家劫舍 II

class Solution:
    def helper(self, nums: List[int]) -> int:
        # 正常数组：LeetCode198. 打家劫舍
        if not nums: return 0
        if len(nums) == 1: return nums[0]
        if len(nums) == 2: return max(nums[0], nums[1])
        dp = [0 for _ in range(len(nums))]
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        return dp[-1]

    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0]
        if len(nums) == 2: return max(nums[0], nums[1])
        # 不抢头 不抢尾
        nums1 = self.helper(nums[1:-1])
        # 不抢头 抢尾
        nums2 = self.helper(nums[1:])
        # 抢头 不抢尾
        nums3 = self.helper(nums[:-1])
        return max(nums1, nums2, nums3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

LeetCode337. 打家劫舍 III（⭐️树形dp Hot100）

LeetCode337. 打家劫舍 III

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: TreeNode) -> int:
        if not root: return 0
        def robTree(root):
            if not root: return [0, 0]
            left = robTree(root.left)
            right = robTree(root.right)

            # 如果不偷当前层root 那么考虑左右孩子
            # 返回左孩子最大偷窃金额+右孩子最大偷窃金额
            val1 = max(left) + max(right)
            # 如果偷当前层root 那么左右孩子都不能偷
            val2 = root.val + left[0] + right[0]
            # [不偷当前节点最终偷到的最大金额, 偷当前节点最终偷到的最大金额]
            return [val1, val2]
        return max(robTree(root))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

8.4、股票问题系列

121、122、714、309是同一类问题；123、188是同一类问题。

LeetCode.121 买卖股票的最佳时机（⭐️⭐️Hot100 腾讯）

只能完成一次交易，且同一天只能进行买入或者卖出

LeetCode.121 买卖股票的最佳时机

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 只交易一次
        if len(prices) < 2: return 0
        # dp[i][0]表示第i天未持股状态下所获最大利润
        # dp[i][1]表示第i天持股状态下所获最大利润
        dp = [[0 for _ in range(2)] for _ in range(len(prices))]
        dp[0][0], dp[0][1] = 0, -prices[0]
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
            # 如果是dp[i-1][0]-prices[i] 说明昨天没持股就有利润了 说明之前有过交易 不符合题意 
            # 所以这里要写-prices[i] 表面昨天没有持股且没有利润 所以当前利润为0-prices[i]
            dp[i][1] = max(-prices[i], dp[i-1][1])
        # 第i天不持股最大利润肯定大于持股最大利润
        return dp[-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode.122. 买卖股票的最佳时机 II（⭐️⭐️ 腾讯 HOT100）

可以完成多次交易，但是同一时刻只能持有一只股

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

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 可以完成多次交易，但是同一时刻只能持有一只股
        if len(prices) < 2: return 0
        # dp[i][0]表示第i天未持股状态下所获最大利润
        # dp[i][1]表示第i天持股状态下所获最大利润
        dp = [[0 for _ in range(2)]for _ in range(len(prices))]
        dp[0][0], dp[0][1] = 0, -prices[0]
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
            # 因为可以买卖多次，所以昨天没持股的情况下是可能会有利润的 
            # 所以用dp[i-1][0]-prices[i]得到昨天没持股，今天持股的最大利润
            dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
        # 第i天不持股最大利润肯定大于持股最大利润
        return dp[-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode714.买卖股票的最佳时机含手续费 — 这个包含了I II（⭐️⭐️⭐️高频）

可以无数次交易 同时最多只能持有一支股票 且每完成一次交易需要支付手续费（在II的基础上加了一个扣除手续费的操作）
LeetCode714.买卖股票的最佳时机含手续费

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        # 可以无数次交易 同时最多只能持有一支股票  且每完成一次交易需要支付手续费
        if len(prices) < 2: return 0
        # dp[i][0]表示第i天未持股状态下所获最大利润
        # dp[i][1]表示第i天持股状态下所获最大利润
        dp = [[0 for _ in range(2)]for _ in range(len(prices))]
        dp[0][0], dp[0][1] = 0, -prices[0]
        for i in range(1, len(prices)):
            # 这里每完成一次交易多加了一个扣除交易费的操作
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]-fee)
            # 这里和II一样
            dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
        return dp[-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode309.最佳买卖股票时机含冷冻期（⭐️⭐️⭐️高频 Hot100）

交易无数次但是同时只能持有一只股票且当天卖出股票后第二天无法买入股票（冷冻期）

LeetCode309.最佳买卖股票时机含冷冻期

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 可以交易无数次 但是同时只能持有一只股票且当天卖出股票后第二天无法买入股票 求最大利润
        if len(prices) < 2: return 0
        # dp[i][0]表示第i天未持股状态下所获最大利润
        # dp[i][1]表示第i天持股状态下所获最大利润
        dp = [[0 for _ in range(2)]for _ in range(len(prices))]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
            # 今天要买入的话就一定要考虑到冷冻期问题
            dp[i][1] = max(dp[i-2][0]-prices[i], dp[i-1][1])
        return dp[-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode.123. 买卖股票的最佳时机 III（⭐️难）

最多总共完成2次交易 同时最多只能完成一次交易

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

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 最多总共完成2次交易 同时最多只能完成一次交易
        if len(prices) < 2: return 0
        # dp[i][j][k]表示第i天 持股状态为j 交易次数为k的情况下所获的最大利润
        # i=0~(len(price)-1)  j: 0不持股 1持股   k: 0次交易 1次交易 2次交易
        dp = [[[0 for _ in range(3)]for _ in range(2)]for _ in range(len(prices))]
        dp[0][0][0] = 0
        dp[0][1][0] = -prices[0]
        dp[0][0][1] = dp[0][0][2] = dp[0][1][1] = dp[0][1][2] = float('-inf') # 不可能事件
        for i in range(1, len(prices)):
            dp[i][0][0] = 0 
            dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0]+prices[i])
            dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1]+prices[i])
            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0]-prices[i])
            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1]-prices[i])
            dp[i][1][2] = float("-inf")  # 不可能事件
        # 注意最大利润可能为负
        return max(0, dp[-1][0][1], dp[-1][0][2])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LeetCode188.买卖股票的最佳时机IV — 这个包含了III（⭐️⭐️难 高频）

最多总共完成k次交易 同时最多只能完成一次交易

LeetCode188.买卖股票的最佳时机IV

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        # 最多总共完成k次交易 同时最多只能完成一次交易
        if len(prices) < 2: return 0
        # dp[i][j][k]表示第i天 持股状态为j 交易次数为k的情况下所获的最大利润
        # i=0~(len(price)-1)  j: 0不持股 1持股   k: 0~k
        dp = [[[0 for _ in range(k+1)]for _ in range(2)]for _ in range(len(prices))]
        dp[0][0][0] = 0
        dp[0][1][0] = -prices[0]
        # 只有一支股票  不可能交易1次、2次.....
        for i in range(1, k+1):
            dp[0][0][i] = dp[0][1][i] =float('-inf')
        for i in range(1, len(prices)):
            for j in range(0, k+1):
                if j == 0:
                    dp[i][0][0] = 0
                    dp[i][1][0] = max(dp[i-1][0][0] - prices[i], dp[i-1][1][0])
                else:
                    dp[i][0][j] = max(dp[i-1][0][j], dp[i-1][1][j-1]+prices[i])
                    dp[i][1][j] = max(dp[i-1][0][j]-prices[i], dp[i-1][1][j])
        res = 0
        for i in range(k+1):
            res = max(res, dp[-1][0][i])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

8.5、子序列、子数组、回文问题系列

8.5.1、子序列问题

子序列可能是连续的也可能是不连续的。

LeetCode674.最长连续递增子序列（⭐️⭐️高频）

LeetCode674.最长连续递增子序列

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) < 2: return len(nums)
        # dp[i]表示以nums[i]原素结尾的最长连续递增子序列的长度
        dp = [1 for _ in range(len(nums))]
        max_len = 1
        # s_end = 1  # 进一步可以通过s_end标记最长子序列的尾部找到最长连续递增子序列
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                # 如果前一个元素小于当前元素 以当前元素结尾的最长子序列长度=以前一个元素结尾的最长子序列长度+1
                # 如果前一个元素大于等于当前元素 则以当前元素结尾的最长子序列长度=1
                dp[i] = dp[i-1] + 1
            if dp[i] > res:
                max_len = dp[i]
                # s_end = i 
        # nums[s_end-max_len+1:s_end+1]  # 找到这个最长连续递增子序列
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode300.最长递增子序列（⭐️⭐️高频 Hot100）

LeetCode300.最长递增子序列

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) < 2: return len(nums)
        # dp[i]表示以nums[i]结尾的最长递增子串的长度
        dp = [1 for _ in range(len(nums))]
        max_len = 1
        for i in range(1, len(nums)):
            # 对每个元素都要从前面的元素开始找 找比当前元素小的元素 得到可能的最长子序列长度=dp[j]+1
            # 不确定最长的子序列是哪个  所以要一个个比较
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j]+1)
            if max_len < dp[i]: max_len = dp[i]
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode1143.最长公共子序列（⭐️⭐️高频）

做这道题可以和718题一起做，类似的。

LeetCode1143.最长公共子序列

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2: return 0
        # dp[i][j]表示text1[:i]和text2[:j]的最长公共子序列的长度
        dp = [[0 for _ in range(len(text2)+1)]for _ in range(len(text1)+1)]
        max_len = 0
        for i in range(1, len(text1)+1):
            for j in range(1, len(text2)+1):
                if text1[i-1] == text2[j-1]:
                    # 如果当前两个子序列最尾的字符相等
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    # 如果当前两个子序列最尾的字符不相等  并不意味着这两个子序列就没有公共子序列了  
                    # 因为text[:i-1]和text2[:j]是可能有公共子序列的
                    # text[:i]和text2[:j-1]也是可能有公共子序列的
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                if max_len < dp[i][j]: max_len = dp[i][j]
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

8.5.2、子数组问题

子数组一定是连续的。

LeetCode53.最大子数组和（⭐️⭐️高频 Hot100 腾讯）

LeetCode53.最大子数组和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 子数组一定是连续的
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0]
        dp = [nums[i] for i in range(len(nums))]
        max_sum = dp[0]
        # dp[i]表示以nums[i]结尾的连续子数组的最大和
        for i in range(1, len(nums)):
            # 1、当前元素当作最大连续子数组
            # 2、前面最大连续子数组+当前元素当作最大连续子数组
            dp[i] = max(nums[i], dp[i-1]+nums[i])
            if max_sum < dp[i]: max_sum = dp[i]
        return max_sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode152.乘积最大子数组（⭐️⭐️高频 Hot100）

LeetCode152.乘积最大子数组

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # 这道题和最大子数组和差不多，但是需要考虑一个特殊情况：
        # 当i-1的乘积是个负数，第i个元素也是一个负数的时候 此时乘积可能最大
        # 所以需要定义两个dp数组，一个记录子数组最大乘积、一个记录子数组最小乘积
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0]
        # 注意这里不能用普通赋值 数组也最好别用普通赋值
        # dp_max[i]表示以nums[i]元素结尾的子数组的最大乘积
        dp_max = [nums[i] for i in range(len(nums))]
        # dp_max[i]表示以nums[i]元素结尾的子数组的最小乘积
        dp_min = [nums[i] for i in range(len(nums))]
        max_mul = nums[0]
        for i in range(1, len(nums)):
            dp_max[i] = max(nums[i], dp_max[i-1]*nums[i], dp_min[i-1]*nums[i]) 
            dp_min[i] = min(nums[i], dp_max[i-1]*nums[i], dp_min[i-1]*nums[i])
            max_mul = max(max_mul, dp_max[i], dp_min[i])
        return max_mul
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode718.最长公共子数组（⭐️⭐️高频）

LeetCode718.最长重复子数组

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        if not nums1 or not nums2: return 0
        # dp[i][j]代表nums1[:i]和nums2[:j]的最长公共子数组的长度
        dp = [[0 for _ in range(len(nums2)+1)]for _ in range(len(nums1)+1)]
        max_len = 0
        for i in range(1, len(nums1)+1):
            for j in range(1, len(nums2)+1):
                if nums1[i-1] == nums2[j-1]:
                    # 如果当前两个子数组最尾的字符相等 + 1
                    dp[i][j] = dp[i-1][j-1] + 1
                if max_len < dp[i][j]: max_len = dp[i][j]
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13

8.5.3、回文问题

LeetCode647. 回文子串（⭐️Hot100）

LeetCode647. 回文子串

class Solution:
    def countSubstrings(self, s: str) -> int:
        if len(s) == 0: return 0
        if len(s) == 1: return 1
        # dp[i][j]表示s[i:j+1]是否是回文子串
        dp = [[False for _ in range(len(s))]for _ in range(len(s))]
        res = 0
        # 初始化dp 
        for i in range(len(s)):  
            dp[i][i] = True
            res += 1
        for i in range(len(s)-2, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    if j - i < 2: dp[i][j] = True
                    else: dp[i][j] = dp[i+1][j-1]
                if dp[i][j] == True: res += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode5.最长回文子串/子数组（⭐️⭐️⭐️经典 难 高频 Hot100 腾讯）

LeetCode5.最长回文子串

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2: return s
        # dp[i][j]表示s[i:j+1]是否是回文子串
        dp = [[False for _ in range(len(s))]for _ in range(len(s))]
        max_len = 1
        s_start, s_end = 0, 0
        for i in range(len(s)):
            dp[i][i] = True
        for i in range(len(s)-2, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    if j - i < 2: dp[i][j] = True
                    else: dp[i][j] = dp[i+1][j-1]
                if dp[i][j] == True and (j-i+1) > max_len:
                    max_len = j - i + 1
                    s_start = i
                    s_end = j
        # 进阶：找到所有最长回文子串
        # res = []
        # if max_len == 1:
        #     for i in s: res.append(i)
        # else:
        #     for i in range(len(s)):
        #         for j in range(i+1, len(s)):
        #             if dp[i][j] == True and (j-i+1) == max_len:
        #                 res.append(s[i:j+1])
        return s[s_start:s_end+1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

LeetCode516.最长回文子序列（⭐️⭐️经典 高频）

LeetCode516.最长回文子序列

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        if len(s) < 2: return len(s)
        # dp[i][j]表示s[i:j+1]内最长回文子序列的长度
        dp = [[0 for _ in range(len(s))]for _ in range(len(s))]
        max_len = 1
        for i in range(len(s)):
            dp[i][i] = 1
        for i in range(len(s)-2, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
                if max_len < dp[i][j]: max_len = dp[i][j]
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8.6、字符串问题系列

1. 在字符串的前面加上空字符之后，会让初始化操作变得简单了很多， 类似于哨兵的那种原理。
2. 如果涉及到两个字符串的动规问题，一般都是二维dp

LeetCode583: 两个字符串的删除操作（⭐️⭐️高频）

LeetCode583: 两个字符串的删除操作

class Solution:
    def minEditCost(self , str1: str, str2: str, ic: int, dc: int, rc: int) -> int:
        if len(str1) == 0: return len(str2) * ic
        if len(str2) == 0: return len(str1) * dc
        # dp[i][j]表示str1[1:i]到str2[1:j]最小代价
        # +1是因为str1和str2都可能会为空
        dp = [[0 for _ in range(len(str2)+1)]for _ in range(len(str1)+1)]
        for i in range(len(str1)):
            dp[i][0] = i * dc
        for j in range(len(str2)):
            dp[0][j] = j * ic
        for i in range(1, len(str1)+1):
            for j in range(1, len(str2)+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j]+dc, dp[i][j-1]+ic, dp[i-1][j-1]+rc)
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode72. 编辑距离（⭐️⭐️难 Hot100）

LeetCode72. 编辑距离

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if len(word1) == 0: return len(word2)
        if len(word2) == 0: return len(word1)
        # dp[i][j]表示word1[1:i+1]到word2[1:j+1]最少的步数
        # +1是因为str1和str2都可能会为空
        dp = [[0 for _ in range(len(word2)+1)]for _ in range(len(word1)+1)]
        for i in range(1, len(word1)+1):
            dp[i][0] = i
        for j in range(1, len(word2)+1):
            dp[0][j] = j
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                # dp[i][j]可以由三个方向来：dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]
                # 比如     abc
                #         acd  
                # 此时i->c  j->d
                # 知道ab->acd操作步数为dp[i-1][j]  =>  abc->acd操作数为dp[i-1][j]+1删除c即可 
                # 知道abc->ac操作步数为dp[i][j-1]  =>  abc->acd操作数为dp[i][j-1]+1插入d即可
                # 知道ab->ac操作步数为dp[i-1][j-1] =>  abc->acd操作数为dp[i-1][j-1]+1将c替换为d即可
                else:          #  删除            插入          替换
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

牛客Top200高频：最小编辑代码（⭐️⭐️高频）

牛客Top200高频：最小编辑代码

class Solution:
    def minEditCost(self , str1: str, str2: str, ic: int, dc: int, rc: int) -> int:
        if len(str1) == 0: return len(str2) * ic
        if len(str2) == 0: return len(str1) * dc
        # dp[i][j]表示str1[1:i]到str2[1:j]最小代价
        # +1是因为str1和str2都可能会为空
        dp = [[0 for _ in range(len(str2)+1)]for _ in range(len(str1)+1)]
        for i in range(len(str1)):
            dp[i][0] = i * dc
        for j in range(len(str2)):
            dp[0][j] = j * ic
        for i in range(1, len(str1)+1):
            for j in range(1, len(str2)+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j]+dc, dp[i][j-1]+ic, dp[i-1][j-1]+rc)
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Leetcode32. 最长有效括号（⭐️⭐️⭐️超难 高频 Hot100）

Leetcode32. 最长有效括号

视频讲解

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if len(s) == 0: return 0
        # dp[i]表示s[:i+1]的最长有效括号长度(格式正确且连续)
        dp = [0 for _ in range(len(s))]
        max_len = 0
        for i in range(1, len(s)):
            if s[i] == '(': dp[i] = 0
            else:
                if s[i-1] == '(': dp[i] = dp[i-2] + 2
                #      0 1 2 3 4 5
                # s = '( ( ) ( ) )'
                #      0 0 2 0 4 i
                # i=')'且i-1=')' 那么看 i-dp[i-1]-1 就是 5-4-1=0(>=0)的位置是'('则
                # dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]=4+2+0=6
                # 注意这里需要保证(i-dp[i-1]-1)>=0因为如果小于0就会跑到最后的元素了
                # (i-dp[i-1]-2)不需要保证，因为默认是为0的，for从前往后遍历 如果(i-dp[i-1]-2)<0 那么dp[(i-dp[i-1]-2)]刚好等于0 对结果不影响
                elif s[i-dp[i-1]-1] == '(' and (i-dp[i-1]-1) >= 0:
                    dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
            if dp[i] > max_len: max_len = dp[i]
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Leetcode10. 正则表达式匹配（超难 Hot100 写不出…）

太难了，顶不住顶不住

Leetcode10. 正则表达式匹配

视频讲解

1

8.7、背包问题系列

0-1背包笔记

b站视频讲解：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题

0-1背包问题：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weights[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

二维dp：

1. 确定dp数组及其含义
   dp[i][j]表示从下标为 0~i 的物品里任意取， 放进容量为 j 的背包， 价值总和的最大值

2. 状态转移方程/递推公式
   dp[i][j]一般可以由两个方向得到：
   A、dp[i-1][j]：表示第 i 个物体我不考虑放不放，那么背包容量为 j ，取前i个物体的最大价值就等于背包容量为 j ，取前 i-1 个物体的最大价值；
   B、dp[i-1][j-weight[i]：表示第i个物体我要考虑放不放的情况下，那么只需要计算在背包容量为 j-weight[i] 的情况下，从前 i-1 个物体中取的最大价值；
   所以dp[i][j] = max(dp[i-1][j]，value[i] + dp[i-1][j-weight[i]])

3. 确定dp初始化方式（由递推公式决定）：
   背包容量为0的话，什么物体都放不下，最大价值永远都是0，即dp[0~][0] = 0；
   只放物品0的话，背包容量大于等于物品0的重量时等于物品0的value，小于物品0的重量时等于0；

   dp = [[0 for _ in range(bagWegiht+1)] for _ in range(len(weight))]   # [物品个数行, 背包重量列]
   for j in (bagWeight, weight[0]-1, -1):  # 得放的下0物品
       dp[0][j] = dp[0][j-wieght[0]] + value[0]
       # dp[0][j] = value[0]   可以这样写吗
   1
   2
   3
   4

4. 确定遍历顺序(顺序可颠倒)

   for i in range(1, len(weight)):     # 遍历物品
   	for j in range(1, bagWegiht+1):   # 遍历背包容量
   1
   2

二维模板：

class Solution:
    def test(self, weights, bagWeight, values) -> bool:
        # dp[i][j]表示从下标为 0~i 的物品里任意取，放进容量为 j 的背包，价值总和的最大值
        # [物品个数行, 背包重量列]
        dp = [[0 for _ in range(bagWegiht+1)] for _ in range(len(weights))]   
        for j in (bagWeight, weights[0]-1, -1):  # 得放的下0物品
            # dp[0][j] = dp[0][j-wieghts[0]] + values[0]
            dp[0][j] = values[0]   
        for i in range(1, len(weights)):     # 遍历物品
                for j in range(1, bagWegiht+1):   # 遍历背包容量
                    # 如果当前包的容量放不下当前物品i, 那么就不放，dp[i][j]继续保持前面的累积最大价值
                    if j < weights[i]: dp[i][j] = dp[i-1][j]
                    else:
                        # 动态转移方程
                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]]+values[i])
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

一维模板（必须完全会写）：

class Solution:
    def test(self, weights, bagWeight, values) -> bool:
        # dp[i][j]表示从下标为 0~i 的物品里任意取，放进容量为 j 的背包，价值总和的最大值
        # [物品个数行, 背包重量列]
        dp = [0 for _ in range(bagWegiht+1)]  
        # dp[0] = 0
        for i in range(len(weights)):     # 遍历物品
            for j in range(bagWegiht, weights[i]-1, -1):   # 遍历背包容量
                 # 小于的时候dp[i][j]=dp[i-1][j] => dp[j]=dp[j] 所以无需判断
                 # 如果当前包的容量放不下当前物品i, 那么就不放，dp[i][j]继续保持前面的累积最大价值
                 if j >= weights[i]:
                     # 动态转移方程
                     dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3种题型：

1. 传统背包问题：dp[i][j]表示在背包容量为j的情况下，从前i个物体中任意选取若干个物体，能够达到的最大重量?最多能装多少？ 公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

2. 转型问题1（LeetCode416: 分割等和子集）：dp[i][j]表示在背包容量为j的情况下，从前i个物体中任意选取若干个物体，能否找到重量为j的组合？能否装满背包？
   公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
   转型问题1是可以等价用传统背包问题等价的，只要在遍历每个物体结束的时候，比较下当前最大重量是否等于target即可：

   dp = [0 for _ in range(bagweight+1)]
   for i in range(len(weights)):     # 遍历物品
       for j in range(bagwegiht, weights[i]-1, -1):   # 遍历背包容量
           if j >= weights[i]:
              dp[i][j] = max(dp[j], dp[j-nums[i]]+nums[i])
           if dp[i][bagweight] == bagweight: return True
   return False
   1
   2
   3
   4
   5
   6
   7

3. 转型问题2（LeetCode494: 目标和）：dp[i][j]表示在背包容量为j的情况下，从前i个物体中任意选取若干个物体，找到重量为j的组合数目？装满背包有几种方法？
   公式：dp[j] += dp[j - nums[i]] 且 dp[0]=1 装满容量为0的背包，有一种方法， 就是啥也不装

完全背包笔记

完全背包问题：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。和0-1背包不同的是，这里的每个物品有无限件。

模板：

def test_complete_pack1(nums):
    bagweight = ?  # 这里具体问题具体分析  
    # dp[j]表示背包容量为j，背包最大能装多少的重量
    dp = [0 for _ in range(bagweight + 1)]
    for i in range(len(nums)):
        for j in range(nums[i], bagweight + 1):
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
    return dp[-1]
1
2
3
4
5
6
7
8

8.7.1、0-1背包

LeetCode416: 分割等和子集（⭐️⭐️⭐️难 高频 Hot100）

LeetCode416: 分割等和子集

把题目转变为：能否找到一个subset，它的和是nums总和的一半。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 1、二维数组
        if len(nums) < 2: return False  # 小于2没法拆
        if sum(nums) % 2 == 1: return False  # 奇数没法拆
        bagWeight = sum(nums) // 2
        if max(nums) > bagWeight: return False  # 最大数大于一半 不可能有
        # dp[i][j]表示下标0~i的元素任意取，限定背包容量为target的情况下 最终最大价值是多少
        # 这里容量=价值=元素本身大小  所有dp又可表示为
        # dp[i][j]表示从下标0~i的元素任意取，限定最大和为target的情况下 最终相加和的最大值 
        dp = [[0 for _ in range(bagWeight+1)]for _ in range(len(nums))]
        for j in range(bagWeight, nums[0]-1, -1):
            dp[0][j] = nums[0]
        for i in range(1, len(nums)):
            for j in range(1, bagWeight+1):
                if j < nums[i]: dp[i][j] = dp[i-1][j]  # 容量小于nums[i]
                else:
                    # 1、不放i 背包容量为j 最大和为dp[i-1][j]
                    # 2、放i 背包容量为j-nums[i] 最大值为dp[i-1][j-nums[i]]+nums[i]
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
            # 如果背包容量为bagWeight（目标和），前i个元素任取的情况下最大和恰好等于背包元素
            # 又因为dp[i][bagWeight] <= bagWeight 所以如果有等于的话 那么就满足条件
            if dp[i][bagWeight] == bagWeight: return True
        return False
        
        # 2、一维数组
        if sum(nums) < 2: return False
        if sum(nums) % 2 == 1: return False
        bagweight = sum(nums) // 2
        if max(nums) > bagweight: return False
        dp = [0 for _ in range(bagweight + 1)]
        for i in range(len(nums)):
            for j in range(bagweight, nums[i]-1, -1):
                if j >= nums[i]:
                    dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
                if dp[bagweight] == bagweight: return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

LeetCode494: 目标和（⭐️⭐️⭐️难 高频 Hot100）

LeetCode494: 目标和

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 设数组中添加'-'元素的总和为neg  则添加'+'的总和为sum_nums-neg
        # (sum_nums-neg) - neg = target => bagweight = neg = (sum_nums-target)//2
        # 所以问题转换为：求出和为bagweight的个数
        sum_nums = sum(nums)
        if (sum_nums - target) % 2 == 1: return 0
        if target > sum_nums: return 0
        bagweight = (sum_nums - target) // 2
        dp = [0 for _ in range(bagweight + 1)]
        dp[0] = 1
        for i in range(len(nums)):
            for j in range(bagweight, nums[i]-1, -1):
                if j >= nums[i]:
                    dp[j] += dp[j-nums[i]]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8.7.2、完全背包（套模板）

LeetCode518.零钱兑换II（⭐️⭐️高频）

LeetCode518.零钱兑换II

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        if amount == 0 or len(coins) == 0: return 1
        dp = [0 for _ in range(amount+1)]
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(coins[i], amount+1):
                if j >= coins[i]:
                    dp[j] += dp[j - coins[i]]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10

LeetCode322.零钱兑换（⭐️⭐️高频 Hot100）

LeetCode322.零钱兑换

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0: return 0
        if len(coins) == 0: return -1
        # dp[i]表示抽成总金额为i的最少金币数
        dp = [float('inf') for _ in range(amount + 1)]
        dp[0] = 0
        for i in range(len(coins)):
            for j in range(coins[i], amount+1):
                dp[j] = min(dp[j], dp[j-coins[i]]+1)
        return dp[-1] if dp[-1] != float('inf') else -1
1
2
3
4
5
6
7
8
9
10
11

LeetCode279.完全平方数（⭐️⭐️Hot100）

LeetCode279.完全平方数

class Solution:
    def numSquares(self, n: int) -> int:
        # 完全背包问题：每个平方数可以使用多次  这里求的是最少值
        # 定义物品：完全平方数  1~sqrt(n)
        nums = [i*i for i in range(1, floor(sqrt(n))+1)]
        # dp[i]表示若干个平方数相加和为j的最少数量
        dp = [float('inf') for _ in range(n+1)]
        dp[0] = 0
        for i in range(len(nums)):
            for j in range(nums[i], n+1):
                dp[j] = min(dp[j], dp[j-nums[i]]+1)
        return dp[-1] if dp[-1] != float('inf') else 0
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode139.单词拆分（⭐️⭐️思路新 Hot100）

LeetCode139.单词拆分

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if len(s) == 0 or len(wordDict) == 0: return False
        # dp[j]表示从i位置到j位置的子串能否被切割成字典中的单词
        dp = [False for _ in range(len(s)+1)]
        dp[0] = True
        for i in range(len(s)):
            for j in range(i+1, len(s)+1):
                if dp[i]==True and s[i:j] in wordDict:
                    dp[j] = True
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11

8.7.3、总结（⭐️⭐️⭐️⭐️⭐️重点知识）

常见的题型：

1. 如果是装满背包有多少种方法
   A、初始化：全局初始化为0， dp[0]=1， 啥也不能装也算一种方法
   B、动态转移方程：dp[j] += dp[j-nums[i]]
2. 当前容量下能否装满
   A、初始化：全局初始化为0， dp[0] = 0， 0容量的背包不能装物品
   B、动态转移方程：dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]
3. 当前容量下装满所用物品的最小个数
   A、初始化：全局初始化为float(“intf”), dp[0]=0， 0容量没法装
   B、动态转移方程：dp[j] = min(dp[j], dp[j-nums[i]]+1
4. 遍历顺序
   A、0-1背包问题： 正向遍历物品， 逆向遍历背包容量， 且必须先遍历物品，后遍历背包容量

    for i in range(len(weights)):     # 遍历物品
        for j in range(bagWegiht, weights[i]-1, -1):   # 遍历背包容量
   1
   2

   B、完全背包问题：正向遍历物品，正向遍历背包容量

   for i in range(len(nums)):
       for j in range(nums[i], bagweight + 1):
   1
   2

九、贪心

9.1、常规问题

9.2、峰值问题（重要）

找极值点这里有个比较好的技巧就是从现在看过去， 当前这个 i 位置，其实是判断的i − 1 这个点是不是一个极值点，这一点要注意。

LeetCode162.寻找峰值/极大值（高频）

LeetCode162.寻找峰值

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # 方法1、直接返回最大值 O(n) 找到1个极值
        # 方法2、贪心 O(n)  找到所有极值
        if len(nums) < 2: return 0
        pre, cur = 0, 0
        res = []
        # nums 看成 [-无穷大] + nums + [无穷大]
        for i in range(1, len(nums)):
            cur = nums[i] - nums[i-1]
            # 极大值
            if cur < 0 and pre >= 0:
                res.append(i-1)
                pre = cur
            # # 极小值
            # if cur > 0 and pre < 0:
            #     res.append(i-1)
            #     pre = cur
            
            # # 极值
            # if (cur < 0 and pre >= 0) or (cur > 0 and pre < 0):
            #     res.append(i-1)
            #     pre = cur
        if cur > 0: res.append(len(nums)-1)
        return res[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

LeetCode376.摆动序列

LeetCode376.摆动序列

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) < 2: return len(nums)
        # [1,1] res=1  [1,2] res=2
        pre, cur = 0, 0
        res = 1  # 第1个是
        arr = []
        for i in range(1, len(nums)):
            cur = nums[i] - nums[i-1]
            # 等于的话也成立 因为可能相邻重复 223的情况  arr=[23] res = 2
            if (cur>0 and pre<=0) or (cur<0 and pre>=0):  # 判断i-1位置是不是极值点
                res += 1
                arr.append(nums[i-1])
                pre = cur
        arr.append(nums[-1])
        print(arr)  
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

9.2、区间类问题（最远覆盖范围）

LeetCode55.跳跃游戏

LeetCode55.跳跃游戏

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1: return True
        max_idx = 0  # 当走到idx=i这个位置时 （0~i-1）位置元素最远能跳到的位置
        for i in range(len(nums)):
            # 走到idx=i位置了 但是max_idx<i 说明 （0~i-1）位置元素都不能到达idx=i位置
            # 也就无法往下走了
            # 注意这里是先if判断 再调整max 
            # 因为就是要在刚进入idx=i的适合 马上就判断（0~i-1）的位置能不能走到idx=i的位置   
            if max_idx < i: return False
            max_idx = max(max_idx, i + nums[i])  # 更新（0~i）位置元素最远能跳到的位置
        return True

1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode45.跳跃游戏II（难 经典）

LeetCode45.跳跃游戏II

class Solution:
    def jump(self, nums: List[int]) -> int:
        # 肯定能走到最后位置 求最少步数
        if len(nums) == 1: return 0

        res = 0  # 记录最小步数
        cur_max_cover = 0  # 当前覆盖的最远距离下标
        next_max_cover = 0 # 下一步覆盖最远距离下表

        for i in range(len(nums)):
            # 走进了一个新的idx
            # 更新下一步覆盖最远距离下标
            next_max_cover = max(next_max_cover, i+nums[i])  
            # 如果当前的最远覆盖距离下表刚好等于i，说明不走不行了 
            if cur_max_cover == i:
                # 如果当前最远覆盖距离到了最后 break 不用走了
                if cur_max_cover == (len(nums)-1): break
                # 否则 继续往下走 更新当前最远覆盖距离
                res += 1
                cur_max_cover = next_max_cover
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

LeetCode56.合并区间（HOT100）

LeetCode56.合并区间

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) <= 0: return intervals
        res = []
        intervals.sort(key=lambda x:x[0])  # 按照起始点大小排序
        intervals.append([float('inf'), 0])  # 最后append一个区间  
        
        for i in range(1, len(intervals)):
            if intervals[i][0] <= intervals[i-1][1]:
                # 当前区间和前面区间重合了 合并当前区间和前面一个区间->当前区间
                intervals[i][0] = min(intervals[i-1][0], intervals[i][0])
                intervals[i][1] = max(intervals[i-1][1], intervals[i][1])
            else:
                # 没有重叠 就把前一个区间append  因为当前区间还需要和后面区间对比
                # 最后一个区间和【float('inf'), 0】对比float('inf)可到小于前一个区间的右部分
                # 所以最后一个区间也必会append进来
                res.append(intervals[i-1])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

十、其他题

10.1、常规题

LeetCode14.最长公共前缀（高频 腾讯）

LeetCode14.最长公共前缀

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1: return strs[0]
        for i in range(len(strs[0])):
            for j in range(1, len(strs)):
                # 超过长度（第一个字符串可能比后面的长） 或 不等（不是公共字符）
                if i == len(strs[j]) or strs[j][i] != strs[0][i]: return strs[0][:i]
        return strs[0]
1
2
3
4
5
6
7
8

LeetCode9. 回文数（腾讯）

LeetCode9. 回文数

class Solution:
    def isPalindrome(self, x: int) -> bool:
        x = str(x)
        return x[:] == x[::-1]
1
2
3
4

LeetCode344. 反转字符串（腾讯）

LeetCode344. 反转字符串

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        for i in range(len(s) // 2):
            s[i], s[len(s)-i-1] = s[len(s)-i-1], s[i]
        return s
1
2
3
4
5
6
7
8

10.2、位运算

笔记

异或（^）运算：

1. a^a=0
2. a^0=a
3. a ^ b ^ c = a ^ c ^ b

与（&）运算：

1. 1&1=1；1&0=0；0&0=0
   a & 1 = 1：可以用这个性质判断a的最后一位是不是1

二进制/比特位中计算1个数的方法：
6. 判断一个数a的比特位最后一位是不是1，用 a&1就能判断出，再将a>>1向右移动一位就再重复使用 a&1就能判断一个数的比特位上有几个1；

LeetCode136. 只出现一次的数字（异或 HOT100）

LeetCode136. 只出现一次的数字

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res ^= num
        return res
1
2
3
4
5
6

LeetCode461. 汉明距离（异或 HOT100）

LeetCode461. 汉明距离

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # 0^0=0  1^1=0  0^1=1
        # 统计s中1的个数
        s = x ^ y
        res = 0
        # 用&统计1的个数
        while s:
            # 判断s的最后一位是不是1
            res += (s & 1)
            s >>= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode338. 比特位计数（HOT100）

LeetCode338. 比特位计数

class Solution:
    def countBits(self, n: int) -> List[int]:
        def count_one(x):
            count = 0
            while x:
                if x & 1: count += 1
                x >>= 1
            return count
        res = []
        for i in range(n+1):
            res.append(count_one(i))
        return res
1
2
3
4
5
6
7
8
9
10
11
12

10.3、前缀树

视频讲解：什么是前缀树？

LeetCode208. 实现 Trie (前缀树)（HOT100）

LeetCode208. 实现 Trie (前缀树)

class Trie:
    def __init__(self):
        self.children = [None for _ in range(26)]
        self.isEnd = False
       
    def insert(self, word: str) -> None:
        cur_node = self
        for c in word:
            c = ord(c) - ord('a')
            if not cur_node.children[c]:  # 当前char在不在
                cur_node.children[c] = Trie()
            cur_node = cur_node.children[c]  # 往下查 下一个char
        # 如果没有就往下补 补到最后一个节点
        # 如果有就一直往下查 查到最后一个节点  isEnd = True
        cur_node.isEnd = True
    
    def _searchPrefix(self, word):
        # 查看前缀树中有没有以prefix为前缀的单词
        cur_node = self
        for c in word:
            c = ord(c) - ord('a')
            if not cur_node.children[c]: return None   
            cur_node = cur_node.children[c]  
        return cur_node

    def search(self, word: str) -> bool:
        # 查看前缀树中有没有单词word
        node = self._searchPrefix(word)
        # 前缀树中有以prefix为前缀的单词+这个单词的末尾str.isEnd=True => 前缀树中有单词word
        return node is not None and node.isEnd

    def startsWith(self, prefix: str) -> bool:
        # 查看前缀树中有没有以prefix为前缀的单词
        node = self._searchPrefix(prefix)
        return True if node is not None else False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

10.4、前缀和

LeetCode560. 和为 K 的子数组（HOT100）

这道题一拿到就想用滑动窗口 但是发现数组中的值可能为负数 那么滑动窗口的while循环就不成立了

LeetCode560. 和为 K 的子数组

视频讲解

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        res = 0
        mapp = {0:1} # k: 前缀和  v: 前缀和为k出现的次数
        pre = 0  # 记录当前前缀和
        for i in range(len(nums)):
            pre += nums[i]
            if pre - k in mapp: res += mapp[pre-k]

            if pre not in mapp: mapp[pre] = 1
            else: mapp[pre] += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12

Reference

CSDN大佬翻滚的小@强博客: LeetCode算法题高频整理(精华篇) 非常牛的人工智能大佬.

b站大佬 哈哈哈123yl: 各专题讲解视频 python语言 主要讲思路.

b站大佬 郭郭wg: 各专题讲解视频 特别是树章节讲的很好.