LeetCode Hot 100 经典题型 Python 实战解析

98. 验证二叉搜索树【中等】

思路： 二叉搜索树的中序遍历结果应当是严格递增的序列。

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        def solve(node):
            if node is None:
                return []
            return solve(node.left) + [node.val] + solve(node.right)
        
        tree_values = solve(root)
        for i in range(len(tree_values) - 1):
            if tree_values[i] >= tree_values[i + 1]:
                return False
        return True

543. 二叉树的直径【简单】

思路： DFS 递归。直径定义为任意两节点间最长路径的边数。全局变量记录最大节点数，最后减 1 得到边数。

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        self.ans = 1  # 最大节点数
        
        def solve(node):
            if node is None:
                return 0
            left_depth = solve(node.left)
            right_depth = solve(node.right)
            total_length = left_depth + right_depth
            self.ans = max(self.ans, total_length + 1)
            return max(left_depth, right_depth) + 1
        
        solve(root)
        return self.ans - 1

617. 合并二叉树【简单】

思路： DFS 递归，对应节点值相加，若某侧为空则返回另一侧。

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        
        merge_tree = TreeNode(val=root1.val + root2.val)
        merge_tree.left = self.mergeTrees(root1.left, root2.left)
        merge_tree.right = self.mergeTrees(root1.right, root2.right)
        return merge_tree

102. 二叉树的层序遍历【中等】

思路： BFS 广度优先搜索，利用队列存储每一层的节点。注意处理每层节点数量以分层输出。

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ans = []
        queue = deque([root])
        while queue:
            n = len(queue)
            cur_level = []
            for _ in range(n):
                node = queue.popleft()
                cur_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(cur_level)
        return ans

226. 翻转二叉树【简单】

思路： 递归交换每个节点的左右子树。

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left = right
        root.right = left
        return root

236. 二叉树的最近公共祖先【中等】

思路： DFS 递归。若当前节点为 p 或 q，直接返回；否则在左右子树查找，若两侧均找到则当前节点即为 LCA。

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

112. 路径总和【简单】

思路： 递归。叶子节点时判断剩余目标值是否等于当前节点值。

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return targetSum == root.val
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

208. 实现 Trie (前缀树)【中等】

思路： 标准前缀树模板，使用数组存储子节点指针。

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

    def searchPrefix(self, prefix: str):
        node = self
        for c in prefix:
            idx = ord(c) - ord('a')
            if not node.children[idx]:
                return None
            node = node.children[idx]
        return node

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if not node.children[idx]:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self.searchPrefix(word)
        return node is not None and node.isEnd

    def startsWith(self, prefix: str) -> bool:
        return self.searchPrefix(prefix) is not None

100. 相同的树【简单】

思路： 递归比较两棵树结构及节点值。

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is None and q is None
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

101. 对称二叉树【简单】

思路： 递归比较左右子树是否镜像对称。

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def helper(p, q):
            if not p or not q:
                return not p and not q
            return p.val == q.val and helper(p.left, q.right) and helper(p.right, q.left)
        return helper(root.left, root.right)

199. 二叉树的右视图【中等】

思路： BFS 层序遍历，每层只保留最后一个节点的值。

from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        queue = deque([root])
        ans = []
        while queue:
            n = len(queue)
            ans.append(queue[-1].val)
            for _ in range(n):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return ans

103. 二叉树的锯齿形层序遍历【中等】

思路： 层序遍历基础上，根据层索引奇偶性决定子节点入队顺序。

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = [root]
        ans = []
        layer_idx = 0
        while queue:
            n = len(queue)
            cur_level = []
            for _ in range(n):
                node = queue.pop(0)
                cur_level.append(node.val)
                if layer_idx % 2 == 1:
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                else:
                    if node.right:
                        queue.append(node.right)
                    if node.left:
                        queue.append(node.left)
            ans.append(cur_level)
            layer_idx += 1
        return ans

124. 二叉树中的最大路径和【困难】

思路： 递归。每个节点作为路径最高点时，路径和为 node.val + max(left, 0) + max(right, 0)。

class Solution:
    def __init__(self):
        self.ans = float('-inf')

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0
            left = max(dfs(node.left), 0)
            right = max(dfs(node.right), 0)
            cur_sum = node.val + left + right
            self.ans = max(self.ans, cur_sum)
            return node.val + max(left, right)
        
        dfs(root)
        return self.ans

108. 将有序数组转换为二叉搜索树【简单】

思路： 递归选取中间元素作为根节点，左右部分分别构建左右子树。

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        n = len(nums) // 2
        left = self.sortedArrayToBST(nums[:n])
        right = self.sortedArrayToBST(nums[n+1:])
        return TreeNode(nums[n], left, right)

字符串

20. 有效的括号【简单】

思路： 栈匹配。遇到左符号入栈，右符号需匹配栈顶。最终栈必须为空。

class Solution(object):
    def isValid(self, s):
        if len(s) % 2 == 1:
            return False
        pairs_dict = {')': '(', '}': '{', ']': '['}
        stack = []
        for c in s:
            if c in pairs_dict:
                if not stack or stack[-1] != pairs_dict[c]:
                    return False
                stack.pop()
            else:
                stack.append(c)
        return not stack

32. 最长有效括号【困难】

思路： 栈存下标。初始化 -1 方便计算长度差。

class Solution(object):
    def longestValidParentheses(self, s):
        stack = [-1]
        ans = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if stack:
                    ans = max(ans, i - stack[-1])
                else:
                    stack.append(i)
        return ans

647. 回文子串【中等】

思路： 中心扩展法，分奇数和偶数长度情况。

class Solution(object):
    def countSubstrings(self, s):
        n = len(s)
        def solve(left, right):
            cnt = 0
            while 0 <= left < n and 0 <= right < n and s[left] == s[right]:
                cnt += 1
                left -= 1
                right += 1
            return cnt
        ans = 0
        for i in range(n):
            ans += solve(i, i)
            ans += solve(i, i + 1)
        return ans

139. 单词拆分【中等】

思路： DP。dp[i] 表示前 i 个字符能否被拆分。

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

394. 字符串解码【中等】

思路： 栈处理嵌套结构，提取数字和字母进行重复拼接。

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        for c in s:
            if c != ']':
                stack.append(c)
            else:
                chars = ''
                while stack and stack[-1] != '[':
                    chars = stack[-1] + chars
                    stack.pop()
                stack.pop()  # pop '['
                num = ''
                while stack and stack[-1].isdigit():
                    num = stack[-1] + num
                    stack.pop()
                stack.append(int(num) * chars)
        return ''.join(stack)

72. 编辑距离【中等】

思路： DP。dp[i][j] 表示 word1 前 i 个字符变为 word2 前 j 个字符的最小操作数。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1): dp[i][0] = i
        for j in range(n + 1): dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
        return dp[m][n]

168. Excel 表列名称【简单】

思路： 类似进制转换，注意 A 从 1 开始编码。

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        ans = []
        while columnNumber > 0:
            columnNumber -= 1
            ch = chr(columnNumber % 26 + ord('A'))
            ans.append(ch)
            columnNumber //= 26
        return ''.join(ans[::-1])

415. 字符串相加【简单】

思路： 模拟竖式加法，从低位往高位进位。

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        ans = ""
        carry = 0
        i, j = len(num1) - 1, len(num2) - 1
        while i >= 0 or j >= 0 or carry:
            x = int(num1[i]) if i >= 0 else 0
            y = int(num2[j]) if j >= 0 else 0
            value = (x + y + carry) % 10
            carry = (x + y + carry) // 10
            ans = str(value) + ans
            i -= 1
            j -= 1
        return ans

搜索查找

448. 找到所有数组中消失的数字【简单】

思路： 标记法。用辅助数组记录出现过的数字。

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        flag = [0] * (n + 1)
        for x in nums:
            flag[x] = 1
        return [i for i in range(1, n + 1) if flag[i] == 0]

136. 只出现一次的数字【简单】

思路： 集合去重计算差值。

class Solution(object):
    def singleNumber(self, nums):
        nums_set = set(nums)
        return sum(nums_set) * 2 - sum(nums)

704. 二分查找【简单】

思路： 标准二分查找模板。

class Solution(object):
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1

121. 买卖股票的最佳时机【简单】

思路： 一次遍历记录最低点和最大收益。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
        return max_profit

122. 买卖股票的最佳时机 II【中等】

思路： 贪心累加所有上涨趋势，或 DP。

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

169. 多数元素【简单】

思路： 哈希统计频率。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count_dict = {}
        threshold = len(nums) // 2
        for num in nums:
            count_dict[num] = count_dict.get(num, 0) + 1
        for k, v in count_dict.items():
            if v > threshold:
                return k

739. 每日温度【中等】

思路： 单调栈。从右向左或从左向右均可，维护递减栈。

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        stack = []
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                j = stack.pop()
                ans[j] = i - j
            stack.append(i)
        return ans

1. 两数之和【简单】

思路： Hash 表存储已遍历元素的索引，O(1) 查找补数。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff in hash_table:
                return [hash_table[diff], i]
            hash_table[num] = i

167. 两数之和 II - 输入有序数组【中等】

思路： 双指针相向移动。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            s = numbers[left] + numbers[right]
            if s < target:
                left += 1
            elif s > target:
                right -= 1
            else:
                return [left + 1, right + 1]

15. 三数之和【中等】

思路： 排序 + 双指针。固定一个数，寻找另外两个数使和为 0。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        n = len(nums)
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, n - 1
            while left < right:
                s = nums[i] + nums[left] + nums[right]
                if s < 0:
                    left += 1
                elif s > 0:
                    right -= 1
                else:
                    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

155. 最小栈【中等】

思路： 辅助栈同步记录最小值。

import math

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        self.min_stack.append(min(self.min_stack[-1], val))

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

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

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

347. 前 K 个高频元素【中等】

思路： 哈希统计 + 排序（或堆）。

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        hash_table = {}
        for num in nums:
            hash_table[num] = hash_table.get(num, 0) + 1
        rank_value = sorted(hash_table.items(), key=lambda x: x[1], reverse=True)
        return [key for key, _ in rank_value[:k]]

287. 寻找重复数【中等】

思路： 哈希集检测重复。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        hash_table = set()
        for num in nums:
            if num in hash_table:
                return num
            hash_table.add(num)

42. 接雨水【困难】

思路： 双指针维护左右最高水位。

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        max_left, max_right = 0, 0
        left, right = 0, n - 1
        ans = 0
        while left < right:
            max_left = max(max_left, height[left])
            max_right = max(max_right, height[right])
            if max_left <= max_right:
                ans += max_left - height[left]
                left += 1
            else:
                ans += max_right - height[right]
                right -= 1
        return ans

11. 盛最多水的容器【中等】

思路： 双指针，矮边向内移动。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        ans = 0
        while left < right:
            width = right - left
            cur_s = width * min(height[left], height[right])
            ans = max(ans, cur_s)
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
        return ans

LCR 172. 统计目标成绩的出现次数【简单】

思路： 二分法找边界。

class Solution:
    def countTarget(self, scores: List[int], target: int) -> int:
        def helper(t):
            left, right = 0, len(scores) - 1
            while left <= right:
                mid = (left + right) // 2
                if scores[mid] < t:
                    left = mid + 1
                else:
                    right = mid - 1
            return left
        l = helper(target)
        r = helper(target + 1)
        return r - l

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

思路： 同上一题，二分查找左右边界。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]
        def helper(t):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < t:
                    left = mid + 1
                else:
                    right = mid - 1
            return left
        l = helper(target)
        r = helper(target + 1)
        if r > l:
            return [l, r - 1]
        return [-1, -1]

1287. 有序数组中出现次数超过 25% 的元素【简单】

思路： 哈希计数。

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        thre = int(n * 0.25)
        hash_table = {}
        for a in arr:
            hash_table[a] = hash_table.get(a, 0) + 1
            if hash_table[a] > thre:
                return a

215. 数组中的第 K 个最大元素【中等】

思路： 快速选择算法（Quick Select）。

import random

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_select(arr, k):
            pivot = random.choice(arr)
            big, equal, small = [], [], []
            for x in arr:
                if x > pivot: big.append(x)
                elif x < pivot: small.append(x)
                else: equal.append(x)
            if len(big) >= k:
                return quick_select(big, k)
            if len(big) + len(equal) < k:
                return quick_select(small, k - len(big) - len(equal))
            return pivot
        return quick_select(nums, k)

209. 长度最小的子数组【中等】

思路： 滑动窗口，枚举右端点收缩左端点。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1
        s = 0
        left = 0
        for right, x in enumerate(nums):
            s += x
            while s >= target:
                ans = min(ans, right - left + 1)
                s -= nums[left]
                left += 1
        return ans if ans <= n else 0

76. 最小覆盖子串【困难】

思路： 滑动窗口 + 字符计数器。

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cnt_win = Counter()
        cnt_t = Counter(t)
        ans_left, ans_right = -float('inf'), float('inf')
        left = 0
        for right, x in enumerate(s):
            cnt_win[x] += 1
            while cnt_win >= cnt_t:
                if right - left < ans_right - ans_left:
                    ans_left, ans_right = left, right
                cnt_win[s[left]] -= 1
                left += 1
        return s[ans_left:ans_right + 1] if ans_left >= 0 else ""

3. 无重复字符的最长子串【中等】

思路： 滑动窗口 + Set 去重。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        visited = set()
        left = 0
        for right, x in enumerate(s):
            while x in visited:
                visited.remove(s[left])
                left += 1
            visited.add(x)
            ans = max(ans, right - left + 1)
        return ans

排列

冒泡排序【排序模板】

class Solution(object):
    def sortArray(self, nums):
        n = len(nums)
        for i in range(1, n):
            for j in range(0, n - i):
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
        return nums

快速排序【排序模板】

import random

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quicksort(arr, low, high):
            if low < high:
                pivot_idx = partition(arr, low, high)
                quicksort(arr, low, pivot_idx - 1)
                quicksort(arr, pivot_idx + 1, high)
            return arr

        def partition(arr, low, high):
            r = random.randint(low, high)
            arr[r], arr[high] = arr[high], arr[r]
            pivot = arr[high]
            slow = fast = low
            while fast <= high:
                if arr[fast] < pivot:
                    arr[fast], arr[slow] = arr[slow], arr[fast]
                    slow += 1
                fast += 1
            arr[high], arr[slow] = arr[slow], arr[high]
            return slow

        n = len(nums)
        return quicksort(nums, 0, n - 1)

283. 移动零【简单】

思路： 双指针保持非零元素相对顺序。

class Solution(object):
    def moveZeroes(self, nums):
        left = 0
        for right in range(len(nums)):
            if nums[right] != 0:
                nums[right], nums[left] = nums[left], nums[right]
                left += 1
        return nums

75. 颜色分类【中等】

思路： 三指针（荷兰国旗问题）。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        n = len(nums)
        p0, p2 = 0, n - 1
        i = 0
        while i <= p2:
            if nums[i] == 2:
                nums[i], nums[p2] = nums[p2], nums[i]
                p2 -= 1
            elif nums[i] == 0:
                nums[i], nums[p0] = nums[p0], nums[i]
                p0 += 1
                i += 1
            else:
                i += 1

406. 根据身高重建队列【中等】

思路： 先按身高降序，再按 k 升序插入。

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people_sort = sorted(people, key=lambda x: (-x[0], x[1]))
        ans = []
        for person in people_sort:
            ans.insert(person[1], person)
        return ans

977. 有序数组的平方【简单】

思路： 双指针从两端向中间比较平方值。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left, right = 0, n - 1
        ans = []
        while left <= right:
            if nums[left]**2 <= nums[right]**2:
                ans.append(nums[right]**2)
                right -= 1
            else:
                ans.append(nums[left]**2)
                left += 1
        return ans[::-1]

31. 下一个排列【中等】

思路： 找右侧递减区间的转折点，交换并反转后缀。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

组合

49. 字母异位词分组【中等】

思路： 排序字符串作为 Key。

class Solution(object):
    def groupAnagrams(self, strs):
        d = {}
        for s in strs:
            sorted_s = ''.join(sorted(s))
            d[sorted_s] = d.get(sorted_s, []) + [s]
        return list(d.values())

78. 子集【中等】

思路： 迭代生成，每次加入新元素到现有子集中。

class Solution(object):
    def subsets(self, nums):
        ans = [[]]
        for num in nums:
            tmp = []
            for i in ans:
                tmp.append([num] + i)
            ans += tmp
        return ans

46. 全排列【中等】

思路： 回溯法，交换元素并恢复现场。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        def dfs(start):
            if start == n:
                ans.append(nums[:])
                return
            for i in range(start, n):
                nums[i], nums[start] = nums[start], nums[i]
                dfs(start + 1)
                nums[i], nums[start] = nums[start], nums[i]
        dfs(0)
        return ans

47. 全排列 II【中等】

思路： 回溯 + 剪枝去重。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        def dfs(start):
            if start == n:
                ans.append(nums[:])
                return
            dic = set()
            for i in range(start, n):
                if nums[i] in dic:
                    continue
                dic.add(nums[i])
                nums[i], nums[start] = nums[start], nums[i]
                dfs(start + 1)
                nums[i], nums[start] = nums[start], nums[i]
        dfs(0)
        return ans

LCR 157. 套餐内商品的排列顺序【中等】

思路： 字符串转列表回溯，最后去重。

class Solution:
    def goodsOrder(self, goods: str) -> List[str]:
        n = len(goods)
        lst = list(goods)
        ans = []
        def dfs(start):
            if start == n:
                ans.append(''.join(lst))
                return
            for i in range(start, n):
                lst[i], lst[start] = lst[start], lst[i]
                dfs(start + 1)
                lst[i], lst[start] = lst[start], lst[i]
        dfs(0)
        return list(set(ans))

链表

206. 反转链表【简单】

思路： 双指针原地反转箭头方向。

class Solution(object):
    def reverseList(self, head):
        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

92. 反转链表 II【中等】

思路： 哨兵节点定位区间，局部反转。

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head:
            return None
        dummy = ListNode(next=head)
        p0 = dummy
        for _ in range(left - 1):
            p0 = p0.next
        cur, prev = p0.next, None
        for _ in range(right - left + 1):
            next_node = cur.next
            cur.next = prev
            prev = cur
            cur = next_node
        p0.next.next = cur
        p0.next = prev
        return dummy.next

234. 回文链表【简单】

思路： 转列表判断回文。

class Solution(object):
    def isPalindrome(self, head):
        l = []
        while head:
            l.append(head.val)
            head = head.next
        return l == l[::-1]

160. 相交链表【简单】

思路： Hash 集存储一条链表的节点。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if not headA or not headB:
            return None
        link_set = set()
        cur = headA
        while cur:
            link_set.add(cur)
            cur = cur.next
        cur = headB
        while cur:
            if cur in link_set:
                return cur
            cur = cur.next
        return None

141. 环形链表【简单】

思路： 快慢指针追及问题。

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            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

142. 环形链表 II【中等】

思路： 快慢指针相遇后，从头和相遇点同时出发再次相遇即为入口。

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        else:
            return None
        tmp = head
        while tmp != slow:
            slow = slow.next
            tmp = tmp.next
        return slow

148. 排序链表【中等】

思路： 归并排序，分割 + 合并。

class Solution:
    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
        mid = slow.next
        slow.next = None
        left = self.sortList(head)
        right = self.sortList(mid)
        ans = ListNode()
        cur = ans
        while left and right:
            if left.val < right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        cur.next = left if left else right
        return ans.next

237. 删除链表中的节点【中等】

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

19. 删除链表的倒数第 N 个节点【中等】

思路： 双指针保持距离 N。

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        right = dummy
        for _ in range(n):
            right = right.next
        left = dummy
        while right.next:
            left = left.next
            right = right.next
        left.next = left.next.next
        return dummy.next

83. 删除排序链表中的重复元素【简单】

思路： 单指针跳过相同值。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        cur = head
        while cur.next:
            if cur.next.val == cur.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

82. 删除排序链表中的重复元素 II【中等】

思路： 哨兵节点，循环跳过所有重复值。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        cur = dummy
        while cur.next and cur.next.next:
            if cur.next.next.val == cur.next.val:
                val = cur.next.val
                while cur.next and cur.next.val == val:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

203. 移除链表元素【简单】

思路： 哨兵节点处理头节点删除。

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if not head:
            return None
        dummy = ListNode(next=head)
        cur = dummy
        while cur and cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

2. 两数相加【中等】

思路： 逐位相加处理进位。

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        ans = ListNode(0)
        cur = ans
        carry = 0
        while l1 or l2 or carry:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            s = x + y + carry
            cur.next = ListNode(s % 10)
            cur = cur.next
            carry = s // 10
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        return ans.next

21. 合并两个有序链表【简单】

思路： 双指针合并。

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        ans = ListNode()
        cur = ans
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return ans.next

23. 合并 K 个升序链表【困难】

思路： 分治法，两两合并。

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def mergeTwoLists(l1, l2):
            dummy = ListNode()
            cur = dummy
            while l1 and l2:
                if l1.val < l2.val:
                    cur.next = l1
                    l1 = l1.next
                else:
                    cur.next = l2
                    l2 = l2.next
                cur = cur.next
            cur.next = l1 if l1 else l2
            return dummy.next

        n = len(lists)
        if n == 0:
            return None
        if n == 1:
            return lists[0]
        left = self.mergeKLists(lists[:n // 2])
        right = self.mergeKLists(lists[n // 2:])
        return mergeTwoLists(left, right)

位运算

461. 汉明距离【简单】

思路： 异或后统计 1 的个数。

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        xor = x ^ y
        dist = 0
        while xor:
            dist += xor & 1
            xor >>= 1
        return dist

338. 比特位计数【简单】

思路： 内置函数或动态规划。

class Solution:
    def countBits(self, n: int) -> List[int]:
        return [bin(i).count('1') for i in range(n + 1)]

191. 位 1 的个数【简单】

思路： 逐位判断。

class Solution:
    def hammingWeight(self, n: int) -> int:
        bit_num = 32
        one_bit = 0
        for i in range(bit_num):
            if n & (1 << i):
                one_bit += 1
        return one_bit

231. 2 的幂【简单】

思路： 二进制只有一个 1。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        return (n & (n - 1)) == 0

数组计算

238. 除自身以外数组的乘积【中等】

思路： 前缀积 + 后缀积。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        front_mul = [1] * n
        behind_mul = [1] * n
        for i in range(1, n):
            front_mul[i] = front_mul[i - 1] * nums[i - 1]
        for i in range(n - 2, -1, -1):
            behind_mul[i] = behind_mul[i + 1] * nums[i + 1]
        return [front_mul[i] * behind_mul[i] for i in range(n)]

152. 乘积最大子数组【中等】

思路： 同时维护最大和最小乘积（负负得正）。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        cur_max = cur_min = ans = nums[0]
        for i in range(1, n):
            temp_max = max(nums[i] * cur_min, nums[i] * cur_max, nums[i])
            cur_min = min(nums[i] * cur_min, nums[i] * cur_max, nums[i])
            cur_max = temp_max
            ans = max(ans, cur_max)
        return ans

53. 最大子数组和【中等】

思路： 经典 DP 模板。

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

300. 最长递增子序列【中等】

思路： DP 状态转移。

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

128. 最长连续序列【中等】

思路： Hash 集 + 起点计数。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hash_set = set(nums)
        ans = 0
        for num in hash_set:
            if num - 1 not in hash_set:
                length_from_here = 1
                cur_num = num
                while cur_num + 1 in hash_set:
                    cur_num += 1
                    length_from_here += 1
                ans = max(ans, length_from_here)
        return ans

438. 找到字符串中所有字母异位词【中等】

思路： 滑动窗口更新字符计数。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        window_size = len(p)
        n = len(s)
        ans = []
        window_cnt = [0] * 26
        p_cnt = [0] * 26
        for c in p:
            p_cnt[ord(c) - ord('a')] += 1
        for c in s[:window_size]:
            window_cnt[ord(c) - ord('a')] += 1
        if p_cnt == window_cnt:
            ans.append(0)
        for i in range(1, n - window_size + 1):
            left_del_char = s[i - 1]
            right_new_char = s[i + window_size - 1]
            window_cnt[ord(left_del_char) - ord('a')] -= 1
            window_cnt[ord(right_new_char) - ord('a')] += 1
            if p_cnt == window_cnt:
                ans.append(i)
        return ans

989. 数组形式的整数加法【简单】

思路： 逐位模拟加法。

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        n = len(num)
        i = n - 1
        carry = 0
        ans = []
        while i >= 0 or k != 0:
            x = num[i] if i >= 0 else 0
            y = k % 10 if k != 0 else 0
            s = x + y + carry
            ans.append(s % 10)
            carry = s // 10
            i -= 1
            k //= 10
        if carry:
            ans.append(carry)
        return ans[::-1]

119. 杨辉三角 II【简单】

思路： 递推每行值。

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row_num = rowIndex + 1
        T = [[1] * (i + 1) for i in range(row_num)]
        for i in range(row_num):
            for j in range(1, i):
                T[i][j] = T[i - 1][j - 1] + T[i - 1][j]
        return T[rowIndex]

198. 打家劫舍【中等】

思路： DP，状态转移方程 dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

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

213. 打家劫舍 II【中等】

思路： 分两种情况讨论首尾不能同时偷。

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])
        def rob_range(start, end):
            dp = [0] * (end - start + 1)
            dp[0] = nums[start]
            dp[1] = max(nums[start], nums[start + 1])
            for i in range(2, end - start + 1):
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i])
            return dp[-1]
        return max(rob_range(0, n - 2), rob_range(1, n - 1))

337. 打家劫舍 III【中等】

思路： 树形 DP，返回偷/不偷两种状态。

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0, 0
            left_rob, left_not_rob = dfs(node.left)
            right_rob, right_not_rob = dfs(node.right)
            cur_rob = node.val + left_not_rob + right_not_rob
            cur_not_rob = max(left_rob, left_not_rob) + max(right_rob, right_not_rob)
            return cur_rob, cur_not_rob
        return max(dfs(root))

239. 滑动窗口最大值【困难】

思路： 单调队列。

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        ans = []
        q = deque()
        for i, x in enumerate(nums):
            while q and x >= nums[q[-1]]:
                q.pop()
            q.append(i)
            if i - q[0] >= k:
                q.popleft()
            if i >= k - 1:
                ans.append(nums[q[0]])
        return ans

56. 合并区间【中等】

思路： 排序后线性扫描合并。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda p: p[0])
        ans = []
        for p in intervals:
            if ans and p[0] <= ans[-1][1]:
                ans[-1][1] = max(p[1], ans[-1][1])
            else:
                ans.append(p)
        return ans

494. 目标和【中等】

思路： 转化为 0-1 背包问题，记忆化搜索。

from functools import cache

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if (target + total) < 0 or (target + total) % 2 != 0:
            return 0
        target = (target + total) // 2

        @cache
        def dfs(i, t):
            if i < 0:
                return 1 if t == 0 else 0
            if nums[i] > t:
                return dfs(i - 1, t)
            return dfs(i - 1, t) + dfs(i - 1, t - nums[i])
        return dfs(len(nums) - 1, target)

322. 零钱兑换【中等】

思路： 完全背包 DP。

from functools import cache

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @cache
        def dfs(i, t):
            if t == 0:
                return 0
            if i < 0:
                return float('inf')
            if coins[i] > t:
                return dfs(i - 1, t)
            return min(dfs(i - 1, t), dfs(i, t - coins[i]) + 1)
        res = dfs(len(coins) - 1, amount)
        return res if res < float('inf') else -1

数据结构设计

380. O(1) 时间插入、删除和获取随机元素【中等】

思路： Hash 表记录索引 + 数组支持 O(1) 访问。

from random import choice

class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.hash = {}

    def insert(self, val: int) -> bool:
        if val not in self.hash:
            self.nums.append(val)
            self.hash[val] = len(self.nums) - 1
            return True
        return False

    def remove(self, val: int) -> bool:
        if val in self.hash:
            index = self.hash[val]
            last_val = self.nums[-1]
            self.nums[index] = last_val
            self.hash[last_val] = index
            del self.hash[val]
            self.nums.pop()
            return True
        return False

    def getRandom(self) -> int:
        return choice(self.nums)

146. LRU 缓存【中等】

思路： 字典 + 双向链表（或使用 OrderedDict）。

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

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

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

矩阵

200. 岛屿数量【中等】

思路： DFS 遍历连通区域。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid, r, c):
            rows, cols = len(grid), len(grid[0])
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
                return
            grid[r][c] = '2'
            dfs(grid, r + 1, c)
            dfs(grid, r - 1, c)
            dfs(grid, r, c + 1)
            dfs(grid, r, c - 1)

        rows, cols = len(grid), len(grid[0])
        ans = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    dfs(grid, r, c)
                    ans += 1
        return ans

221. 最大正方形【中等】

思路： DP，状态取决于左、上、左上三个方向的最小值。

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        if rows == 0 or cols == 0:
            return 0
        dp = [[0] * cols for _ in range(rows)]
        max_side = 0
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                    max_side = max(max_side, dp[i][j])
        return max_side ** 2

73. 矩阵置零【中等】

思路： 两次遍历，标记行列。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0])
        row_flag, col_flag = [0] * rows, [0] * cols
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 0:
                    row_flag[r] = 1
                    col_flag[c] = 1
        for r in range(rows):
            for c in range(cols):
                if row_flag[r] or col_flag[c]:
                    matrix[r][c] = 0

48. 旋转图像【中等】

思路： 水平翻转 + 主对角线翻转。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

867. 转置矩阵【简单】

思路： 行列交换。

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        rows, cols = len(matrix), len(matrix[0])
        ans = [[0] * rows for _ in range(cols)]
        for i in range(rows):
            for j in range(cols):
                ans[j][i] = matrix[i][j]
        return ans

数学计算

69. x 的平方根【简单】

思路： 二分法或牛顿迭代。

import math

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        left, right = 1, x
        ans = 1
        while left <= right:
            mid = (left + right) // 2
            if mid * mid <= x:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        return ans

构造随机变量，等概率生成 1～n 的数

思路： 利用不等概率硬币构造等概率事件，再生成二进制位。

import math

def Rand1(p=0.5):
    return 1 if __import__('random').random() < p else 0

def RandN(n: int):
    k = int(math.log2(n)) + 1
    while True:
        res = 0
        for _ in range(k):
            res = (res << 1) | Rand1()
        if res <= n:
            return res

343. 整数拆分【中等】

思路： DP，拆分为两段或不拆。

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(1, i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[n]

263. 丑数【简单】

思路： 循环除 2、3、5。

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        for p in [2, 3, 5]:
            while n % p == 0:
                n //= p
        return n == 1

264. 丑数 II【中等】

思路： 三指针法。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        a = [0] * (n + 1)
        a[1] = 1
        p2, p3, p5 = 1, 1, 1
        for i in range(2, n + 1):
            num2, num3, num5 = a[p2] * 2, a[p3] * 3, a[p5] * 5
            a[i] = min(num2, num3, num5)
            if a[i] == num2: p2 += 1
            if a[i] == num3: p3 += 1
            if a[i] == num5: p5 += 1
        return a[n]

258. 各位相加【简单】

思路： 数根性质，模 9 余数。

class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0
        return (num - 1) % 9 + 1

202. 快乐数【简单】

思路： 哈希判环或快慢指针。

class Solution:
    def isHappy(self, n: int) -> bool:
        def compute_next(n):
            total = 0
            while n > 0:
                digit = n % 10
                total += digit ** 2
                n //= 10
            return total
        slow, fast = n, compute_next(n)
        while True:
            if slow == fast:
                return False
            if fast == 1:
                return True
            slow = compute_next(slow)
            fast = compute_next(compute_next(fast))

图

207. 课程表【中等】

思路： DFS 判断是否有环。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)
        states = [0] * numCourses
        def dfs(x):
            states[x] = 1
            for node in graph[x]:
                if states[node] == 1 or (states[node] == 0 and dfs(node)):
                    return True
            states[x] = 2
            return False
        for i in range(numCourses):
            if states[i] == 0 and dfs(i):
                return False
        return True

64. 最小路径和【中等】

思路： DP，从左上到右下。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = [[0] * cols for _ in range(rows)]
        dp[0][0] = grid[0][0]
        for i in range(1, rows):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for j in range(1, cols):
            dp[0][j] = dp[0][j - 1] + grid[0][j]
        for i in range(1, rows):
            for j in range(1, cols):
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
        return dp[rows - 1][cols - 1]