Python 刷题清单
哈希表
双指针
| def lengthOfLongestSubstring(s: str) -> int:
# 哈希表记录出现的元素及索引
# 哈希表出现的元素，left 移动到哈希表中索引 +1 位置，否则右指针右移扩大窗口
seen = {}
left = right = max_win = 0
while right < len(s):
if s[right] in seen:
left = seen[s[right]] + 1
seen[s[right]] = right
right += 1
max_win = max(max_win, right - left)
return max_win
|
| def threeSum(nums: list[int]) -> list[list[int]]:
if len(nums) < 3:
return []
nums.sort()
ans = []
# 先固定第一个数
for i in range(len(nums) - 2):
# 提前剪枝：如果第一个数已经大于0，后面都是正数，不可能和为0
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i-1]:
continue # 跳过重复的第一个数
# 用双指针让剩余两数之和与第一个数的和为0
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
# 注意此时已经排序
if s < 0: # 和太小，需要右移靠近较大数
left += 1
elif s > 0: # 和太大，需要左移靠近较小数
right -= 1
else: # 和为 0
ans.append([nums[i], nums[left], nums[right]])
# 跳过重复的第二个数
while left < right and nums[left] == nums[left+1]:
left += 1
# 跳过重复的第三个数
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
return ans
|
由于本题查找最长回文子串，我们并不清楚回文边界，因此 无法使用对撞指针，只能用回文中心对称的特点，从中心向两侧扩展求解。
| # Time: O(n²), Space: O(1)
def longestPalindrome(s: str) -> str:
start = max_len = 0
# 从中心向两侧扩展，返回回文长度
def expand(l: int, r: int) -> None:
nonlocal start, max_len
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
# 此时 [l+1, r-1] 是回文
if r - l - 1 > max_len:
start = l + 1
max_len = r - l - 1
for i in range(len(s)):
# 无法预知以某个位置为中心的最长回文是奇数还是偶数长度，因此需要同时遍历两种情况，取最长的那个
expand(i, i) # 奇数长度回文（如 "aba"）
expand(i, i + 1) # 偶数长度回文（如 "abba"）
return s[start:start + max_len]
|
题目解释：将数组视为一个数字，在所有排列中找到恰好比当前排列大的下一个排列；若已是最大排列，则回绕到最小排列。
nums = [1,2,3]：对应数字 123，所有排列按大小排序为 123 → 132 → 213 → …，下一个排列为 [1,3,2]nums = [3,2,1]：对应数字 321，已是最大排列，回绕到最小排列 [1,2,3]
解题思路：
- 从右往左，找到第一个满足
nums[k] < nums[k+1] 的位置 k（即第一个"下降点"）。若不存在，说明已是最大排列，直接翻转整个数组即可。（可以通过折线图可视化查找过程）
- 再从右往左，找到第一个满足
nums[l] > nums[k] 的位置 l。
- 交换
nums[k] 与 nums[l]。
- 翻转
nums[k+1:]，使其从降序变为升序，得到恰好大一点的排列。
以 nums = [1,2,7,4,3,1] 为例：
- 找下降点：从右往左扫描，
nums[1]=2 < nums[2]=7，故 k=1
- 找交换点：从右往左找第一个大于 2 的数，
nums[4]=3，故 l=4
- 交换：
nums = [1,3,7,4,2,1]
- 翻转
nums[2:]：nums = [1,3,1,2,4,7] ✅
| # Time: O(n), Space: O(1)
def nextPermutation(nums: list[int]) -> None:
# 从右往左找到第一个下降点 i
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
if i >= 0:
# 从右往左找到第一个大于 nums[i] 的数 j
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
# 交换 i 和 j
nums[i], nums[j] = nums[j], nums[i]
# 反转 i 之后的部分
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
|
双指针倒序填充
| # Time: O(m+n), Space: O(1)
def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
p1, p2, tail = m - 1, n - 1, m + n - 1
# 只需检查 p2 >= 0，因为 nums2 处理完后，nums1 剩余元素已在正确位置
while p2 >= 0:
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[tail] = nums1[p1]
p1 -= 1
else:
nums1[tail] = nums2[p2]
p2 -= 1
tail -= 1
|
| # Time: O(n+m), Space: O(1)
def compareVersion(version1: str, version2: str) -> int:
n, m = len(version1), len(version2)
i = j = 0
while i < n or j < m:
x = 0
while i < n and version1[i] != '.':
x = x * 10 + int(version1[i])
i += 1
i += 1 # 跳过点号
y = 0
while j < m and version2[j] != '.':
y = y * 10 + int(version2[j])
j += 1
j += 1 # 跳过点号
if x > y:
return 1
if x < y:
return -1
return 0
|
链表
| def reverseList(head: ListNode | None) -> ListNode | None:
prev = None
# 暂存、反转、移动
while head:
next_node = head.next
head.next = prev
prev = head
head = next_node
return prev
|
头插法，将每个要反转的节点连接到 prev 后
| def reverseBetween(head: ListNode | None, left: int, right: int) -> ListNode | None:
dummy = ListNode(next=head) # 可能从头结点开始反转
prev = dummy
for _ in range(left - 1):
prev = prev.next
curr = prev.next
for _ in range(right - left):
next_node = curr.next # 暂存操作节点的移动路径
curr.next = next_node.next # 摘下节点
next_node.next = prev.next # 插到区间头部
prev.next = next_node # 移动操作的节点
return dummy.next
|
分组+局部反转
| def reverseKGroup(head: ListNode | None, k: int) -> ListNode | None:
dummy = ListNode(next=head)
prev = dummy
while True:
tail = prev
for _ in range(k):
tail = tail.next
if not tail:
return dummy.next
next_group = tail.next
# 局部反转链表
cur = prev.next
for _ in range(k - 1):
next_node = cur.next
cur.next = next_node.next
next_node.next = prev.next
prev.next = next_node
cur.next = next_group
prev = cur
|
快慢指针解法：快指针走两步，慢指针走一步，相遇则有环
| def hasCycle(head: ListNode | None) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
|
| def detectCycle(head: ListNode | None) -> ListNode | None:
seen = set()
while head:
if head in seen:
return head
seen.add(head)
head = head.next
return None
|
| def mergeTwoLists(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
dummy = ListNode()
current = dummy
# 注意该遍历需同时操作3个链表
while l1 and l2: # 注意是 and
if l1.val < l2.val: # 将较小的值挂载在新链表上
current.next = l1
l1 = l1.next # 移动原链表
else:
current.next = l2
l2 = l2.next
current = current.next # 移动新链表
# 将链表剩余部分挂载，同时处理原链表为空
current.next = l1 if l1 else l2
# 注意返回的是 dummy.next
return dummy.next
|
双向链表 + 哈希表
| class Node:
def __init__(self, key: int = 0, value: int = 0):
self.key = key
self.value = value
self.prev: 'Node | None' = None
self.next: 'Node | None' = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache: dict[int, Node] = {} # 哈希表：key -> 链表节点
self.head = Node() # 虚拟头节点（最近使用）
self.tail = Node() # 虚拟尾节点（最久未使用）
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
# 将节点移到头部（标记为最近使用）
self._move_to_head(node)
return node.value
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
# 更新已存在的节点
node = self.cache[key]
node.value = value
self._move_to_head(node)
else:
# 创建新节点
new_node = Node(key, value)
self.cache[key] = new_node
self._add_to_head(new_node)
# 检查容量，必要时删除最久未使用的节点
if len(self.cache) > self.capacity:
removed = self._remove_tail()
del self.cache[removed.key]
# 辅助方法：将节点添加到头部
def _add_to_head(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
# 辅助方法：移除节点
def _remove_node(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
# 辅助方法：将节点移到头部
def _move_to_head(self, node: Node) -> None:
self._remove_node(node)
self._add_to_head(node)
# 辅助方法：移除尾部节点
def _remove_tail(self) -> Node:
node = self.tail.prev
self._remove_node(node)
return node
|
二叉树
遍历方式
后序遍历题目
当节点需要依赖左右子树的信息时，使用后序遍历
后序遍历的递归解法：先钻到最底下，在返回时再做处理
| def maxDepth(root: TreeNode | None) -> int:
if not root:
return 0
left = maxDepth(root.left)
right = maxDepth(root.right)
return max(left, right) + 1
|
平衡树就是左右子树高度差不超过 1，所以要基于后序遍历的树深度来求解
| def isBalanced(root: TreeNode | None) -> bool:
def check_height(node: TreeNode | None) -> int:
if not node:
return 0
# 后序遍历：先检查左子树
left_height = check_height(node.left)
if left_height == -1:
return -1 # 左子树不平衡，提前终止
# 后序遍历：再检查右子树
right_height = check_height(node.right)
if right_height == -1:
return -1 # 右子树不平衡，提前终止
# 返回时处理：检查当前节点是否平衡
if abs(left_height - right_height) > 1:
return -1 # 当前节点不平衡
# 返回当前节点的高度（自底向上汇总信息）
return max(left_height, right_height) + 1
return check_height(root) != -1
|
| def diameterOfBinaryTree(root: TreeNode | None) -> int:
max_diameter = 0
def depth(node: TreeNode | None) -> int:
nonlocal max_diameter
if not node:
return 0
# 后序遍历：先递归计算左右子树的深度
left_depth = depth(node.left)
right_depth = depth(node.right)
# 当前节点的直径 = 左子树深度 + 右子树深度
max_diameter = max(max_diameter, left_depth + right_depth)
# 计算当前节点的深度
return max(left_depth, right_depth) + 1
depth(root)
return max_diameter
|
与树的直径类似，对于每个节点，路径和 = 左子树贡献 + 右子树贡献 + 当前节点值
| import math
def maxPathSum(root: TreeNode | None) -> int:
max_sum = -math.inf # 初始化为最小值，因为节点值可能为负
def max_gain(node: TreeNode | None) -> int:
nonlocal max_sum
if not node:
return 0
# 后序遍历：先递归计算左右子树的最大贡献
# 如果子树贡献为负，则不选择该子树（取 0）
left_gain = max(max_gain(node.left), 0)
right_gain = max(max_gain(node.right), 0)
# 以当前节点为"拐点"的路径和
# 路径和 = 左子树贡献 + 右子树贡献 + 当前节点值
current_path_sum = left_gain + right_gain + node.val
max_sum = max(max_sum, current_path_sum)
# 返回给父节点的最大贡献：只能选择左或右其中一条路径
# 贡献 = 当前节点值 + max(左子树贡献, 右子树贡献)
return node.val + max(left_gain, right_gain)
max_gain(root)
return max_sum
|
-
最近公共祖先示例
-
LCA 判断逻辑
| def lowestCommonAncestor(root: TreeNode | None, p: TreeNode, q: TreeNode) -> TreeNode | None:
# 递归终止条件：
# 1. 搜到底了（None）
# 2. 找到目标节点（p 或 q）
if not root or root is p or root is q:
return root
# 后序遍历：先递归左右子树
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
# 根据左右子树的返回值判断 LCA 位置
# 情况1：p 和 q 分散在左右两侧 → 当前节点就是 LCA
if left and right:
return root
# 情况2：p 和 q 都在左子树 → 返回左子树的结果
if left:
return left
# 情况3：p 和 q 都在右子树（或右子树找到一个）→ 返回右子树的结果
return right
|
由于 BST 的有序性，其解法与普通的 LCA 相似：如果 \(p\) 和 \(q\) 都小于当前节点，则 LCA 在左子树；如果 \(p\) 和 \(q\) 都大于当前节点，则 LCA 在右子树；否则当前节点就是 LCA。
| # 迭代解法(推荐)
# Time: O(h), Space: O(1)
def lowestCommonAncestorIterative(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode | None:
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
return None
|
| # 递归解法
# Time: O(h), Space: O(h)
def lowestCommonAncestorRecursive(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if p.val < root.val and q.val < root.val:
return lowestCommonAncestorRecursive(root.left, p, q)
if p.val > root.val and q.val > root.val:
return lowestCommonAncestorRecursive(root.right, p, q)
return root
|
中序遍历题目
前序遍历题目
当节点需要依赖左右子树的信息时，使用前序遍历，这样不仅代码简单，而且高效
层序遍历题目
DFS
堆/优先队列
栈
队列
二分查找
动态规划
回溯
贪心
递归
编写递归步骤：
- 明确输入输出
- 明确递归终止条件（什么时候触底反弹？）
- 明确递归处理逻辑（每层要做什么事？）
- 明确递归过程（下楼做还是返回做？）
图论
