LeetCode Hot 100 经典题型 Python 刷题记录

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

利用中序遍历特性，判断序列是否严格单调递增。

class Solution(object):
    def isValidBST(self, root):
        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 递归，计算经过当前节点的最长路径。

class Solution(object):
    def diameterOfBinaryTree(self, root):
        self.ans = 1
        def solve(node):
            if node is None:
                return 0
            left_depth = solve(node.left)
            right_depth = solve(node.right)
            self.ans = max(self.ans, left_depth + right_depth + 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 模板，用队列存储每一层的节点。注意调试用的 print 语句在实际提交时需删除。

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 的子树。

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. 二叉树的右视图【中等】

广度优先搜索，取每层最右侧节点。

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. 二叉树中的最大路径和【困难】

递归计算以当前节点为起点的最大路径，同时更新全局最大值。

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. 最长有效括号【困难】

栈存下标，计算长度差。

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. 单词拆分【中等】

动态规划，判断前缀是否可拆且后缀在字典中。

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，考虑增删改三种操作。

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 i in range(n + 1): dp[0][i] = i
        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 表列名称【简单】

26 进制转换，注意从 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
            s = x + y + carry
            ans = str(s % 10) + ans
            carry = s // 10
            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【中等】

贪心累加所有上涨趋势。

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 = {}
        for num in nums:
            count_dict[num] = count_dict.get(num, 0) + 1
        return max(count_dict, key=count_dict.get)

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. 两数之和【简单】

哈希表存储已遍历元素及其索引。

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
        return []

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]
        return []

15. 三数之和【中等】

排序后固定一个元素，双指针找另外两个。

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. 最小栈【中等】

辅助栈同步存储最小值。

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = [float('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
        return sorted(hash_table, key=lambda x: hash_table[x], reverse=True)[:k]

287. 寻找重复数【中等】

哈希集检测重复。

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

42. 接雨水【困难】

双指针维护左右最高点。

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_left, max_right = 0, 0
        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
            h = min(height[left], height[right])
            ans = max(ans, width * h)
            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(target_val):
            left, right = 0, len(scores) - 1
            while left <= right:
                mid = (left + right) // 2
                if scores[mid] < target_val:
                    left = mid + 1
                else:
                    right = mid - 1
            return left
        return helper(target + 1) - helper(target)

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

同上一题，二分查找边界。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def helper(target_val):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target_val:
                    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
        return arr[0]

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

快速选择算法思想。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        import random
        def quick_select(nums, k):
            pivot = random.choice(nums)
            big, equal, small = [], [], []
            for x in nums:
                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. 最小覆盖子串【困难】

滑动窗口配合字符计数器。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
        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. 无重复字符的最长子串【中等】

滑动窗口维护不重复集合。

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

排列

冒泡排序【排序模板】

O(n^2) 基础排序。

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

快速排序【排序模板】

分治策略，随机基准点。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        import random
        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
        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
        return quicksort(nums, 0, len(nums) - 1)

283. 移动零【简单】

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

class Solution(object):
    def moveZeroes(self, nums):
        left = 0
        for right in range(len(nums)):
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                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(key=lambda x: (-x[0], x[1]))
        ans = []
        for person in people:
            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. 相交链表【简单】

哈希存储一条链表的节点。

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:
            tmp = tmp.next
            slow = slow.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
        if left:
            cur.next = left
        elif right:
            cur.next = right
        return ans.next

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

直接复制后继节点值。

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

19. 删除链表的倒数第 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:
            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
        if carry:
            cur.next = ListNode(carry)
        return ans.next

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

双指针取小值。

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 and not list2:
            return None
        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
        if list1:
            cur.next = list1
        elif list2:
            cur.next = 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
            if l1: cur.next = l1
            elif l2: cur.next = l2
            return dummy.next
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        mid = len(lists) // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return mergeTwoLists(left, right)

位运算

461. 汉明距离【简单】

异或后统计 1 的个数。

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        xor = x ^ y
        dist = 0
        for i in range(32):
            if (xor >> i) & 1:
                dist += 1
        return dist

338. 比特位计数【简单】

转二进制计数。

class Solution(object):
    def countBits(self, n):
        ans = []
        for i in range(n + 1):
            ans.append(bin(i).count('1'))
        return ans

191. 位 1 的个数【简单】

逐位判断。

class Solution:
    def hammingWeight(self, n: int) -> int:
        one_bit = 0
        for i in range(32):
            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 bin(n).count('1') == 1

数组计算

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 = [0] * n
        cur_min = [0] * n
        ans = nums[0]
        cur_max[0], cur_min[0] = nums[0], nums[0]
        for i in range(1, n):
            cur_max[i] = max(nums[i] * cur_min[i - 1], nums[i] * cur_max[i - 1], nums[i])
            cur_min[i] = min(nums[i] * cur_min[i - 1], nums[i] * cur_max[i - 1], nums[i])
            ans = max(ans, cur_max[i])
        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. 最长连续序列【中等】

哈希集合查找连续序列。

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, right_new_char = s[i - 1], 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 状态转移。

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])
        dp1 = [0] * n
        dp1[0] = nums[0]
        dp1[1] = max(nums[0], nums[1])
        for i in range(2, n - 1):
            dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i])
        ans1 = dp1[-2]
        dp2 = [0] * n
        dp2[1] = nums[1]
        dp2[2] = max(nums[1], nums[2])
        for i in range(3, n):
            dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i])
        ans2 = dp2[-1]
        return max(ans1, ans2)

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. 滑动窗口最大值【困难】

单调队列。

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 背包问题转化。

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

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

数据结构设计

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

哈希表记录索引，列表支持随机访问。

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:
        import random
        return random.choice(self.nums)

146. LRU 缓存【中等】

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> value
        self.order = []  # 记录访问顺序

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.order.remove(key)
        self.order.append(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.order.remove(key)
        self.cache[key] = value
        self.order.append(key)
        if len(self.cache) > self.capacity:
            oldest = self.order.pop(0)
            del self.cache[oldest]

矩阵

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 - 1 or c < 0 or c > cols - 1 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 的平方根【简单】

二分法或牛顿迭代。

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

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. 丑数【简单】

循环除因子。

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]