LeetCode 经典算法题 Python 实战解析：树、链表与 DP

同理，前序遍历和后序遍历如下：

# 前序
return [root.val] + self.inorderTraversal(root.left) + self.inorderTraversal(root.right)
# 后序
return self.inorderTraversal(root.left) + self.inorderTraversal(root.right) + [root.val]

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

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

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

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

思路是 DFS 递归。我们需要一个全局变量来记录经过当前节点的最大路径长度（左深度 + 右深度）。

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        self.ans = 1  # 最大 node 数（全局变量）
        
        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)  # 加上 root 的 node 数
            return max(left_depth, right_depth) + 1  # node 数
        
        solve(root)
        return self.ans - 1  # 得到的 node 数减 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，用队列存储每一层的节点。为了清晰展示过程，这里保留了部分打印语句，实际提交时请删除。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ans = []
        queue = [root]
        while queue:
            n = len(queue)
            cur_level = []
            for _ in range(n):
                node = queue.pop(0)  # 丢掉最前面的一项（当前层）
                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

也可以用 Python 库中的双向队列实现，效率更高：

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ans = []
        queue = deque()
        queue.append(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:
            return None
        if 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 (前缀树)【中等】

思路是前缀树模板。每个节点维护一个长度为 26 的子节点数组和一个结束标记。

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:
        node = self.searchPrefix(prefix)
        return node 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. 有效的括号【简单】

思路：遇到左符号直接入栈，右符号则开始匹配。注意最终 stack 必须被消耗为空才成功。列表非空的判断语法是 if not list，而不是 if list is None。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        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):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        ans = 0
        stack.append(-1)
        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):
        """
        :type s: str
        :rtype: int
        """
        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[j] 表示字符串前 j 个字符是否能被拆分。

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)
            if c == ']':
                chars = ''
                while stack and stack[-1] != '[':
                    chars = stack[-1] + chars
                    stack.pop()
                stack.pop()  # 弹出 '['
                
                num = ''
                while stack and stack[-1].isdigit():
                    num = stack[-1] + num
                    stack.pop()
                num = int(num)
                chars_repeat = num * chars
                stack.append(chars_repeat)
        
        ans = ''
        while stack:
            ans = stack[-1] + ans
            stack.pop()
        return ans

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 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 进制转换，注意 A 是从 1 开始编码的，所以每次先减 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
            sum_val = x + y + carry
            value = sum_val % 10
            carry = sum_val // 10
            ans = str(value) + ans
            i -= 1
            j -= 1
        return ans

搜索查找

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

思路：不能用 python 的 if i in list，因为底层也是循环，会超时。最简单的做法是用辅助的 flag 来记录哪些位置有元素。

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

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

思路：集合 set 去重，然后用两倍 sum 减原来 sum 得到那个单个数。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums_set = set(nums)
        nums_set_sum = sum(nums_set)
        gap = nums_set_sum * 2 - sum(nums)
        return gap

704. 二分查找【简单】

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

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        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. 买卖股票的最佳时机【简单】

暴力写法复杂度 O(n^2) 会超时。其实只需要在一次遍历过程中记录最低点和当前最大收益。

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:
        n = len(prices)
        ans = 0
        for i in range(1, n):
            ans += max(prices[i] - prices[i - 1], 0)
        return ans

思路二：DP。

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

169. 多数元素【简单】

思路：拿一个字典存储 number 以及对应的数量。

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

739. 每日温度【中等】

思路：单调栈。最暴力的写法是 O(n^2) 的，会超时。

从右往左构造单调栈：

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

还可以从左往右构造单调栈：

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 存储。构建一个 hash 表，核心是判断 diff in hash_table。

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

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

思路：利用数组单增的特点，采用相向双指针解决。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        left, right = 0, n - 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. 三数之和【中等】

思路：先排序，然后指定第一个元素，在剩下两个元素值上用相向双指针。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = []
        for i in range(n - 2):
            a = nums[i]
            if i >= 1 and a == nums[i - 1]:
                continue
            left, right = i + 1, n - 1
            while left < right:
                s = a + nums[left] + nums[right]
                if s < 0:
                    left += 1
                elif s > 0:
                    right -= 1
                elif s == 0:
                    ans.append([a, nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 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 个高频元素【中等】

思路：统计频率后排序。下面是最暴力的做法，复杂度 O(n log n)。

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        hash_table = {}
        for i in range(n):
            if nums[i] not in hash_table:
                hash_table[nums[i]] = 1
            else:
                hash_table[nums[i]] += 1
        
        rank_value = sorted(hash_table.items(), key=lambda x: x[1], reverse=True)
        ans = []
        for i, (key, value) in enumerate(rank_value):
            ans.append(key)
            if i == k - 1:
                break
        return ans

287. 寻找重复数【中等】

思路：用 hash 存储遍历的值，如果发现重复则返回结果。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        if not nums:
            return -1
        n = len(nums)
        hash_table = set()
        for i in range(n):
            if nums[i] in hash_table:
                return nums[i]
            hash_table.add(nums[i])

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:
        n = len(height)
        if n == 2:
            return min(height[0], height[1]) * 1
        ans = 0
        left, right = 0, n - 1
        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:
        n = len(scores)
        def helper(t):
            left, right = 0, n - 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. 在排序数组中查找元素的第一个和最后一个位置【中等】

思路：同第 172 题，二分法搜索边界。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]
        n = len(nums)
        def helper(t):
            left, right = 0, n - 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% 的元素【简单】

思路：用 hash/数组计数。

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

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

思路：基于快速排序思想（Quick Select）。

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. 最小覆盖子串【困难】

思路：滑动窗口，和第 209 题思路一致，这里用到字符计数器 Count()。

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):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        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

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

283. 移动零【简单】

思路：双指针（都从左侧开始），实现 inplace 排列。

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        left = 0
        for right in range(len(nums)):
            if nums[right] != 0:
                nums[right], nums[left] = nums[left], nums[right]
                left += 1
        return nums

如果用双指针（从两端开始），无法保证元素的相对顺序，不推荐。

当然也可以先把所有非零数放到左边，最后右边填补 0。

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        idx_non_zero = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[idx_non_zero] = nums[i]
                idx_non_zero += 1
        for i in range(idx_non_zero, len(nums)):
            nums[i] = 0
        return nums

75. 颜色分类【中等】

思路：三指针，p0 左侧保持全 0，p2 右侧保持全 2，i 从左往右遍历数组。

细节：如果 i 遇到 0，swap 后 i 继续走；如果 i 遇到 2，swap 后 i 先别动（因为可能把后面的 0 交换到前面了）。

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
            elif nums[i] == 1:
                i += 1

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

思路：对身高降序，k 升序，然后根据 k 进行插入。

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        n = len(people)
        ans = []
        people_sort = sorted(people, key=lambda x: (-x[0], x[1]))
        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 映射多个字母异位词（用 value 列表存）。

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

78. 子集【中等】

思路：维护一个 ans 列表，遍历 nums 中所有元素，每个元素都将和 ans 列表中每一项进行组合。

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        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【中等】

思路：仍然是第 46 题的回溯，但是需要用哈希去重。

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. 套餐内商品的排列顺序【中等】

思路：同样回溯，但是针对字符串，需要先转 list 才能支持交换操作。

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):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

92. 反转链表 II【中等】

思路：加入哨兵节点，定义 left 位置左边的节点、prev 节点和 cur 节点。

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):
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """
        l = []
        while head:
            l.append(head.val)
            head = head.next
        return l == l[::-1]

160. 相交链表【简单】

思路：用 hash 存储一条链表的节点，然后去搜索另一条链表中哪个节点存在于 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【中等】

思路：和上一题并无区别，改成返回节点。如果存在环，再加入一个指针从头开始走，速度为 1，和环中的 slow 指针相遇时，即环的入口。

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:
                tmp = head
                while tmp != slow:
                    slow = slow.next
                    tmp = tmp.next
                return slow
        return None

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):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

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

思路：安排哨兵 dummy 节点，双指针保持距离为 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【中等】

思路：判断 cur.next 和 cur.next.next 的值，然后用循环去跳过所有相同值的节点。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        cur = dummy
        while cur.next and cur.next.next:
            val = cur.next.val
            if cur.next.next.val == 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. 两数相加【中等】

思路：参照第 989 题的加法模板，该题从左往右即数字的低位开始。

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
            value = s % 10
            carry = s // 10
            cur.next = ListNode(value)
            cur = cur.next
            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(list1, list2):
            dummy = ListNode()
            cur = dummy
            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 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. 汉明距离【简单】

思路：直接异或再计数，注意 bin() 的输出是 string。

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        xor = bin(x ^ y)
        dist = list(xor[2:]).count('1')
        return dist

338. 比特位计数【简单】

思路：转二进制然后计数。

class Solution(object):
    def countBits(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        ans = []
        for i in range(n + 1):
            bin_num = list(bin(i))[2:]
            ans.append(bin_num.count('1'))
        return ans

191. 位 1 的个数【简单】

思路：通过'与'进行逐位判断。

class Solution:
    def hammingWeight(self, n: int) -> int:
        bit_num = 32
        one_bit = []
        for i in range(bit_num):
            if n & (1 << i):
                one_bit.append(1)
        return sum(one_bit)

231. 2 的幂【简单】

思路：转二进制后判断 1 的个数。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        bits = []
        for i in range(32):
            cur_bit = 1 if (2 ** i) & n else 0
            bits.append(cur_bit)
        return True if bits.count(1) == 1 else False

数组计算

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

思路：分别计算某个数左右的乘积，再汇总起来。

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

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(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. 最大子数组和【中等】

思路：这是 152 题的普通版，典型 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(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 存储方便查找元素，先找到序列的开头，然后不断 +1 去判断存在性。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        n = len(nums)
        hash_set = set(nums)
        ans = 0
        for num in hash_set:
            if num - 1 in hash_set:
                continue
            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
            value = s % 10
            carry = s // 10
            ans.append(value)
            i -= 1
            k //= 10
        if carry:
            ans.append(carry)
        return ans[::-1]

119. 杨辉三角 II【简单】

思路：递推每行的值，但是要注意每行首尾两个元素默认为 1。

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【中等】

思路：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])
        
        # 情况 1：如果第 0 天可以偷，第 n-1 天不能偷
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n - 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        ans1 = dp[-2]
        
        # 情况 2：第 n-1 天可以偷，第 0 天不能偷
        dp[1] = nums[1]
        dp[2] = max(nums[1], nums[2])
        for i in range(3, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        ans2 = dp[-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 = 0 + 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 背包。转化成了一个'选若干个数，使和为 (target+sum(nums))/2'的问题。

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

322. 零钱兑换【中等】

思路：完全背包。

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

数据结构设计

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

如果要实现 O(1) 复杂度，可以用一个 hash table 记录 index 和值的关系。

import random

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:
        if not self.nums:
            return []
        return random.choice(self.nums)

146. LRU 缓存【中等】

思路：字典 + 双向链表。用 Python 库实现。

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。遍历网格，遇到 '1' 就启动 DFS 将整个连通区域标记为已访问。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid, r, c):
            row_num = len(grid)
            col_num = len(grid[0])
            if r < 0 or r > row_num - 1 or c < 0 or c > col_num - 1:
                return
            if 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)

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

221. 最大正方形【中等】

思路：DP。dp[i][j] 表示以 (i, j) 为右下角的正方形的边长。

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 and 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. 矩阵置零【中等】

思路：两次遍历，第一次记录行列存在 0 的位置，第二次修改原矩阵。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows = len(matrix)
        cols = 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. 旋转图像【中等】

思路：顺时针旋转 90 度=水平翻转 + 主对角线翻转（转置）。

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 = len(matrix)
        cols = 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:
        left, right = 0, x
        ans = -1
        while left <= right:
            mid = (left + right) // 2
            if mid ** 2 <= x:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        return ans

思路：牛顿迭代。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        x0 = x
        while True:
            x1 = 0.5 * (x0 + x / x0)
            if abs(x0 - x1) < 1e-6:
                break
            x0 = x1
        return int(x0)

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

题目：一个随机变量 X，有 P 的概率生成 1，（1-P）的概率生成 0，请利用 X 构造一个随机变量，等概率生成 1～n 的数。 解答：由题目可得，P(1)=p, P(0)=1-p。首先考虑一个更简单的问题，能否等概率生成 0 和 1？可以，随机采样两次。P(0,1)=(1-p)p, P(1,0)=p(1-p)，这两种情况概率一致。

import random

def random_coin(p):
    return 1 if random.random() < p else 0

def Rand1(self):
    i1 = random_coin()
    i2 = random_coin()
    if i1 == 0 and i2 == 1:
        return 0
    elif i1 == 1 and i2 == 0:
        return 1
    else:
        return Rand1()

def RandN(self, n: int):
    import numpy as np
    k = int(np.log2(n) + 1)
    res = ''
    for _ in range(k):
        res += str(Rand1())
    if int(res, 2) > n:
        return RandN(n)
    else:
        return int(res, 2)

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(0, i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[n]

263. 丑数【简单】

思路：循环除 2、3、5，检查最后是否为 1。

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        while n % 2 == 0:
            n //= 2
        while n % 3 == 0:
            n //= 3
        while n % 5 == 0:
            n //= 5
        return True if n == 1 else False

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. 各位相加【简单】

思路：暴力做法直接循环进行模拟。

class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0
        while num >= 10:
            s = 0
            while num > 0:
                s += num % 10
                num //= 10
            num = s
        return num

进阶：用 O(1) 复杂度完成，结果为模 9 的余数，但需要考虑 0 和 9 的倍数特殊情况。

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

202. 快乐数【简单】

思路：哈希判断重复元素。如果空间复杂度 O(1)，则用快慢指针判断重复元素。

class Solution:
    def isHappy(self, n: int) -> bool:
        if n == 1:
            return True
        def compute_next(n):
            s = 0
            while n > 0:
                s += (n % 10) ** 2
                n //= 10
            return s
        
        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) == True):
                    return True
            states[x] = 2
            return False

        for i, s in enumerate(states):
            if s == 0 and dfs(i) == True:
                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]