【Leetcode 第二轮刷题日记】LeetcodeTOP100+高频题整理
目录
- 前言
- 一些笔记
- 一、链表篇（14）
- 二、树篇（26）
- 三、回溯、DFS、BFS篇（10）
- 四、数组和哈希表
- 五、二分查找（9）
- 六、栈和队列（9）
- 七、排序（5）
- 八、动态规划（33）
- 九、贪心
- 十、其他题
- Reference
前言
刷完第一轮已经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
# 然后对新链表进行操作
2、求链表的倒数节点，一般用快慢指针的思路；（ Leetcode 19）
3、下面两句是不一样的
while cur and cur.next:
while cur.next and cur:
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
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
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
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)
9、双向链表相关操作(面试高频题：Leetcode143 LRU缓存)
在p节点后面插入节点node：
node.next = p.next
p.next.pre = node
node.pre = p
p.next = node
删除node节点：
node.pre.next = node.next
node.next.pre = node.pre
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
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
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]
翻转二叉树（后序遍历）
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)
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]
5、在函数a的函数b中使用函数a的遍历，这个遍历最好用self. 让他变成全局变量
6、下面两种添加方式一样
res = [1,2]
res.append(3) -> res = [1,2,3]
res += [3] -> res = [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
8、idx = list.index(val) 返回list中值为val的index下标
一、链表篇（14）
1.1、删除链表元素
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
LeetCode19. 删除链表的倒数第 N 个结点（ ⭐️⭐️⭐️高频、剑指II、HOT100）
要点：首先，删除倒数第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
相同的类型还有找链表的中心节点，也是用快慢指针，慢指针每次走一步，快指针每次走两步，快指针走到末尾节点了，满指针也就走到了中间节点了。
LeetCode82. 删除排序链表中的重复元素 II（⭐️⭐️高频、剑指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、翻转/旋转链表
剑指 Offer II 024. 反转链表（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）
# 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
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
LeetCode61. 旋转链表（腾讯）
旋转数组：先整体逆序，再前k个逆序，最后k后面逆序
# 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.3、交换链表节点
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.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
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
这两道题也可以用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
LeetCode160.相交链表（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）
这道题非常的巧妙，题解：力扣官方题解.
# 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
同样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
LeetCode234.回文链表（⭐️⭐️⭐️高频、剑指II、HOT100）
第一种思路是用栈存储前面一半的节点（用快慢指针找中点），再每次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
第二种思路，边找中点边将前一半节点逆序，然后再将前一半节点和后一半节点比较：
# 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.5、链表合并
LeetCode2: 两数相加（⭐️腾讯 HOT100）
# 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
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)
LeetCode21: 合并两个有序链表（⭐️⭐️⭐️高频、剑指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 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
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
但是时间复杂度有点高，而且这道题是很多大厂都很喜欢考察的一道题，单单会这种简单方法应该是过不了关的，所以再学一种堆排序的思路：把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.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
但是想想还是优点讨巧，这和直接遍历，再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)
LeetCode143: 重排链表（⭐️⭐️高频、剑指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, 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.7、LRU缓存
LeetCode146. LRU 缓存（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）
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)
二、树篇（26）
本章题目总结：
-
层次遍历的题目比较简单，基本上弄得层次遍历的题目都是可以秒杀的
最后那道牛客的题有点东西：判断是否是完全二叉树的题，。 -
中序遍历：这部分的题目呢总是和二叉搜索树相关，一般用非递归容易写，特别是设计节点的一些操作，比如需要找到当前节点前一个节点的题，用非递归好写点。
最后两题有点意思：一个二叉搜索树转成双向链表；一个累加树（倒中序right->mid->left） -
二叉搜索树相关：二叉搜索树的题目一般会用到两个性质：1、中序遍历=升序；2、root.val>root.left.val and root.val < root.right.val（左子树都小于当前节点，右子树都大于当前节点）
上面的中序遍历是用到性质一，下面的两道题一般是用性质2：一道是求二叉搜索树的最近公共祖先，一道是判断某个数组是不是某个二叉搜索树的后续遍历结果
这部分这两道题都需要注意下。 -
前序遍历：这里的题目基本是都是用前序遍历的递归框架解决的：
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需要注意的是：这里需要返回什么？是否可以在preorderTraversal设置一个self.res全局变量，在dfs用self.res调用即可？这要看是否会在preorderTraversal调用自身，如果需要调用自身，那么你在preorderTraversal中每次都会重新定义这个全局变量，那么就不能在preorderTraversal中定义这个全局变量。如路径总和3，不过大部分情况下还是可以定义的。
这部分的题目需要格外注意的是：leetcode437路径总和3 -
后序遍历：这部分可以和后面的递归专题一起合起来看，联系很紧密
这部分的题目应该是树专题中比较难也是比较最要的部分，一道要全弄懂。
leetcode236可以说是树章节的王者，非常常考，也比较难，一定要掌握啊。另外leetcide124也稍微注意下。 -
树的递归：Leetcode572挺特别的一道题，和一般的递归想法不一样；
-
二叉树的修改构造：两道题都挺经典的，尤其是序列化与反序列化那道题，面试非常高频。必须掌握。
-
技巧性题：这道题是HOT100的题，很经典，一定要掌握：LeetCode114. 二叉树展开为链表
2.1、二叉树前序遍历
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
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
LeetCode617. 合并二叉树（⭐️Hot100）
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
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
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
LeetCode437.路径总和 III（⭐️难 Hot100）
视频讲解.
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
2.2、二叉树中序遍历
LeetCode98.验证二叉搜索树（⭐️⭐️高频、HOT100）
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
剑指 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
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
剑指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
Leetcode.538. 把二叉搜索树转换为累加树（⭐️Hot100）
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
2.3、二叉树后序遍历
Leetcode104. 二叉树的最大深度（⭐️HOT100 腾讯）
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
LeetCode226. 翻转二叉树（⭐️HOT100）
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)
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
LeetCode543.二叉树的直径 （⭐️⭐️高频、HOT100）
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 # 最大直径
LeetCode124.二叉树中的最大路径和（⭐️⭐️⭐️高频、剑指II、HOT100 腾讯）
和上面那题差不多。
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
Leetcode236. 二叉树的最近公共祖先（⭐️⭐️⭐️⭐️⭐️最经典 高频、HOT100 腾讯）
这道题应该是二叉树最重要的一道题，很多公式都会考察，题目难度也比较高，一定要理解透，争取拿到就能秒杀。
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
2.4、二叉树层次遍历
LeetCode199.二叉树的右视图（⭐️⭐️高频、剑指II）
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
剑指 Offer II 044. 二叉树每层的最大值（⭐️剑指II）
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
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
Leetcode101. 对称二叉树（⭐️⭐️高频、HOT100）
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
牛客.判断一棵树是否是完全二叉树（⭐️高频）
下面不设限制，不管左子树和右子树是否为空，都加入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
2.5、二叉搜索树
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
剑指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)
2.6、二叉树的修改构造
LeetCode105.从前序和中序遍历构造二叉树（⭐️⭐️⭐️高频、剑指II、HOT100）
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)
Leetcode 297.二叉树的序列化与反序列化（⭐️⭐️经典 高频、HOT100）
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))
2.7、二叉树的递归思维
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)
2.8、其他
LeetCode114. 二叉树展开为链表（技巧性题⭐️难 Hot100）
本来最简单的代码先前序遍历，将节点保存起来，再遍历创建链表，题目就很简单了，但是需要O(n)的空间复杂度。面试的时候肯定不能写成这样（实在写不出来也没办法，就写这个吧）。下面这种偏技巧性的思路，可以O(1)的空间复杂度，但是不容易想到。面试想到哪个用哪个吧。
这道题有点技巧性 视频讲解.
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
三、回溯、DFS、BFS篇（10）
3.1、回溯
3.1.1、组合问题
LeetCode39: 组合总和（⭐️⭐️经典 HOT100）
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
LeetCode40: 组合总和II（⭐️⭐️⭐️经典 高频、HOT100）
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
LeetCode17. 电话号码的字母组合(⭐️HOT100）
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
3.1.2、子集问题
LeetCode78：子集（⭐️⭐️⭐️经典 高频、Hot100 腾讯）
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
LeetCode90：子集II（⭐️⭐️⭐️经典 高频、Hot100）
和组合总和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
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
3.1.3、全排列问题
LeetCode46. 全排列（⭐️⭐️经典 HOT100 腾讯）
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
LeetCode47: 全排列II（⭐️⭐️⭐️经典 高频、HOT100）
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
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
3.2、DFS和BFS
3.2.1、网格类问题
LeetCode200: 岛屿数量（⭐️⭐️⭐️经典 高频、HOT100）
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
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
LeetCode79. 单词搜索（⭐️HOT100）
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
3.2.2、括号问题
LeetCode22. 括号生成（⭐️HOT100）
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
3.2.3、图问题
LeetCode207. 课程表（HOT100 难）
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
四、数组和哈希表
4.1、重建数组（高频）
适合用来删除数组中不符合要求的元素，如：删除0、输出有序数组中重复数字、删除指定数字target。
LeetCode283.移动零（HOT100）
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
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
4.2、双指针
剑指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
LeetCode11. 盛最多水的容器（HOT100 腾讯）
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
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
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
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
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]
LeetCode75. 颜色分类（难 很有特点的一道双指针题 HOT100）
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
LeetCode4.寻找两个正序数组的中位数（难 没解开 高频 HOT100 腾讯）
4.3、哈希表
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
LeetCode1.两数之和（高频 HOT100）
这道题第一想法是双指针，但是一看数组无序且这里不能排序，打扰了…
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
LeetCode128.最长连续序列（高频 HOT100）
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
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,这里具体情况具体分析
模板二：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) 具体情况具体分析
剑指offer03.数组中重复的数字（经典 高频）
长度为n的数组 存放0~n-1范围的数字，原地hash 让第i个位置存储i
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
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
4.5、滑动窗口
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
LeetCode3. 无重复字符的最长子串（HOT100）
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
LeetCode76. 最小覆盖子串（HOT100）
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
4.6、旋转模拟
这类题目实实在在的模拟旋转过程，不涉及高深的算法，但是很考察代码功底。
LeetCode48. 旋转图像（HOT100）
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]]
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
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
LeetCode498.对角线遍历（难 高频）
对角线遍历规律：
- 每一条对角线上横坐标和纵坐标的总和不变， 并且每一条对角线都是总和加1，也就是递增， 总和会从0开始增到m+n-2， m是矩阵的行数， n是矩阵的列数；
- 当遍历对角线的时候，如果是从下往上走， 那么横坐标递减到0，而纵坐标递增到最大， 如果是从上往下走，纵坐标递减到0，横坐标递增到最大
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
4.7、其他
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
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]))
Leetcode169. 多数元素（高频 HOT100 腾讯）
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
LeetCode31.下一个排列（高频 HOT100）
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
LeetCode8. 字符串转换整数（高频 腾讯）
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
五、二分查找（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
写法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
写法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
总结：
- 第一种适合找元素的左边界；第二种适合找右边界
5.1、正常二分
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
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
5.2、二维矩阵类
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
LeetCode240.搜索二维矩阵II（⭐️⭐️高频、HOT100）
这道题虽然不是用传统的二分模板来做的，但是里面的思想其实还是上面二分模板的思想，一次次的排除不可能的区域，最后剩下的要么是最终的答案要么没有答案。
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
# 这道题也可以左下角开始搜索
5.3、旋转数组类
LeetCode33.搜索旋转排序数组（⭐️⭐️⭐️经典 难 高频、HOT100 腾讯）
唯一一道用到模板3的题目
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
LeetCode153.搜索旋转数组的最小值（⭐️⭐️难 高频）
这道题技巧性优点重啊
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]
这道题还有道进阶题：数组元素重复。有重复元素，如果是连续的话，是没有关系的，这个模板还是可以找到最小元素，但是如果有重复元素，且分在mid左边两边，如：[1,0,1,1,1]
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]
5.4、找极大、极小值
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
5.5、其他
寻找两个正序数组的中位数（⭐️⭐️⭐️经典 难 HOT100）
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
LeetCode287. 寻找重复数（⭐️HOT100）
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
六、栈和队列（9）
6.1、普通栈
LeetCode20 有效的括号（⭐️⭐️⭐️基础题 经典 高频、HOT100 腾讯）
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
LeetCode155. 最小栈（⭐️⭐️基础题 高频、HOT100 腾讯）
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]
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
LeetCode394. 字符串解码（⭐️经典 Hot100）
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
6.2、单调栈（每一题都要掌握）
LeetCode739. 每日温度（⭐️Hot100）
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
下面的几道题差不多就是739的进阶版本了。
LeetCode84. 柱状图中最大的矩形（⭐️⭐️⭐️经典 难 高频、HOT100）
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
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
LeetCode42. 接雨水（⭐️⭐️⭐️经典 难 高频、HOT100）
视频讲解 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
6.3、单调队列
Leetcode239. 滑动窗口最大值（⭐️⭐️⭐️经典 难 高频 HOT100）
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
七、排序（5）
7.1、堆排序
笔记
适合解决前k个、第k个这种不需要整个数组排序，只用排一部分的题目。
堆排序特点：
- 完全二叉树+所有父节点val>子节点val
- 节点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]
调包实现：
heapq.heapify(nums) # 第一种掉包排序实现（建立最小堆）
hp = []
for num in nums: # 第二种掉包堆排序实现（建立最小堆）
heapq.heappush(hp, num) # push进一个元素 堆还是维护小顶堆
min_val = heapq.heappop() # 弹出堆顶元素（最小值） 堆还是维护小顶堆
LeetCode215.数组中的第K个最大元素（⭐️⭐️⭐️高频、HOT100 腾讯）
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]
面试题 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]
Leetcode347. 前 K 个高频元素（⭐️⭐️HOT100）
这道题掉包不是很好搞
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]
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]
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"
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"
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]
归并排序的典型应用就是链表排序。
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)
八、动态规划（33）
视频讲解：理解动态规划
8.1、普通动规系列
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]
LeetCode70. 爬楼梯（⭐️Hot100 腾讯）
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]
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]
8.2、路径规划系列
LeetCode62. 不同路径（⭐️Hot100 腾讯）
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]
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]
LeetCode64.最小路径和（⭐️⭐️⭐️高频 Hot100）
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]
LeetCode221. 最大正方形（Hot100）
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
8.3、打家劫舍系列
LeetCode198. 打家劫舍（⭐️⭐️Hot100）
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]
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)
LeetCode337. 打家劫舍 III（⭐️树形dp Hot100）
# 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))
8.4、股票问题系列
121、122、714、309是同一类问题；123、188是同一类问题。
LeetCode.121 买卖股票的最佳时机（⭐️⭐️Hot100 腾讯）
只能完成一次交易，且同一天只能进行买入或者卖出
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]
LeetCode.122. 买卖股票的最佳时机 II（⭐️⭐️ 腾讯 HOT100）
可以完成多次交易，但是同一时刻只能持有一只股
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]
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]
LeetCode309.最佳买卖股票时机含冷冻期（⭐️⭐️⭐️高频 Hot100）
交易无数次但是同时只能持有一只股票且当天卖出股票后第二天无法买入股票（冷冻期）
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]
LeetCode.123. 买卖股票的最佳时机 III（⭐️难）
最多总共完成2次交易 同时最多只能完成一次交易
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])
LeetCode188.买卖股票的最佳时机IV — 这个包含了III（⭐️⭐️难 高频）
最多总共完成k次交易 同时最多只能完成一次交易
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
8.5、子序列、子数组、回文问题系列
8.5.1、子序列问题
子序列可能是连续的也可能是不连续的。
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
LeetCode300.最长递增子序列（⭐️⭐️高频 Hot100）
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
LeetCode1143.最长公共子序列（⭐️⭐️高频）
做这道题可以和718题一起做，类似的。
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
8.5.2、子数组问题
子数组一定是连续的。
LeetCode53.最大子数组和（⭐️⭐️高频 Hot100 腾讯）
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
LeetCode152.乘积最大子数组（⭐️⭐️高频 Hot100）
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
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
8.5.3、回文问题
LeetCode647. 回文子串（⭐️Hot100）
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
LeetCode5.最长回文子串/子数组（⭐️⭐️⭐️经典 难 高频 Hot100 腾讯）
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]
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
8.6、字符串问题系列
- 在字符串的前面加上空字符之后，会让初始化操作变得简单了很多， 类似于哨兵的那种原理。
- 如果涉及到两个字符串的动规问题，一般都是二维dp
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]
LeetCode72. 编辑距离（⭐️⭐️难 Hot100）
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]
牛客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]
Leetcode32. 最长有效括号（⭐️⭐️⭐️超难 高频 Hot100）
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
Leetcode10. 正则表达式匹配（超难 Hot100 写不出…）
太难了，顶不住顶不住
8.7、背包问题系列
0-1背包笔记
b站视频讲解：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题
0-1背包问题：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weights[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
二维dp：
-
确定dp数组及其含义
dp[i][j]表示从下标为 0~i 的物品里任意取， 放进容量为 j 的背包， 价值总和的最大值 -
状态转移方程/递推公式
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]]) -
确定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] 可以这样写吗 -
确定遍历顺序(顺序可颠倒)
for i in range(1, len(weight)): # 遍历物品 for j in range(1, bagWegiht+1): # 遍历背包容量
二维模板：
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]
一维模板（必须完全会写）：
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]
3种题型：
-
传统背包问题：dp[i][j]表示在背包容量为j的情况下，从前i个物体中任意选取若干个物体，能够达到的最大重量?最多能装多少？ 公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
-
转型问题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 -
转型问题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]
8.7.1、0-1背包
LeetCode416: 分割等和子集（⭐️⭐️⭐️难 高频 Hot100）
把题目转变为：能否找到一个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
LeetCode494: 目标和（⭐️⭐️⭐️难 高频 Hot100）
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]
8.7.2、完全背包（套模板）
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]
LeetCode322.零钱兑换（⭐️⭐️高频 Hot100）
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
LeetCode279.完全平方数（⭐️⭐️Hot100）
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
LeetCode139.单词拆分（⭐️⭐️思路新 Hot100）
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]
8.7.3、总结（⭐️⭐️⭐️⭐️⭐️重点知识）
常见的题型：
- 如果是装满背包有多少种方法
A、初始化：全局初始化为0， dp[0]=1， 啥也不能装也算一种方法
B、动态转移方程：dp[j] += dp[j-nums[i]] - 当前容量下能否装满
A、初始化：全局初始化为0， dp[0] = 0， 0容量的背包不能装物品
B、动态转移方程：dp[j] = max(dp[j], dp[j-nums[i]]+nums[i] - 当前容量下装满所用物品的最小个数
A、初始化：全局初始化为float(“intf”), dp[0]=0， 0容量没法装
B、动态转移方程：dp[j] = min(dp[j], dp[j-nums[i]]+1 - 遍历顺序
A、0-1背包问题： 正向遍历物品， 逆向遍历背包容量， 且必须先遍历物品，后遍历背包容量
B、完全背包问题：正向遍历物品，正向遍历背包容量for i in range(len(weights)): # 遍历物品 for j in range(bagWegiht, weights[i]-1, -1): # 遍历背包容量for i in range(len(nums)): for j in range(nums[i], bagweight + 1):
九、贪心
9.1、常规问题
9.2、峰值问题（重要）
找极值点这里有个比较好的技巧就是从现在看过去， 当前这个 i 位置，其实是判断的i − 1 这个点是不是一个极值点，这一点要注意。
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]
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
9.2、区间类问题（最远覆盖范围）
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
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
LeetCode56.合并区间（HOT100）
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
十、其他题
10.1、常规题
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]
LeetCode9. 回文数（腾讯）
class Solution:
def isPalindrome(self, x: int) -> bool:
x = str(x)
return x[:] == x[::-1]
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
10.2、位运算
笔记
异或（^）运算：
- a^a=0
- a^0=a
- a ^ b ^ c = a ^ c ^ b
与（&）运算：
- 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）
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for num in nums:
res ^= num
return res
LeetCode461. 汉明距离（异或 HOT100）
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
LeetCode338. 比特位计数（HOT100）
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
10.3、前缀树
LeetCode208. 实现 Trie (前缀树)（HOT100）
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
10.4、前缀和
LeetCode560. 和为 K 的子数组（HOT100）
这道题一拿到就想用滑动窗口 但是发现数组中的值可能为负数 那么滑动窗口的while循环就不成立了
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
Reference
CSDN大佬翻滚的小@强博客: LeetCode算法题高频整理(精华篇) 非常牛的人工智能大佬.
b站大佬 哈哈哈123yl: 各专题讲解视频 python语言 主要讲思路.
b站大佬 郭郭wg: 各专题讲解视频 特别是树章节讲的很好.