LeetCode 热题 HOT 100 经典算法题 Python 解法汇总

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

# 前序
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(root):
            if root is None:
                return []
            else:
                return solve(root.left) + [root.val] + solve(root.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
        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 = deque()
        queue.append(root)
        while queue:
            n = len(queue)
            cur_level = []
            for _ in range(n):  # 当前层的 node 数
                node = queue.popleft()  # 丢掉最前面的一项（当前层）
                cur_level.append(node.val)  # 当前层的 node 值都放进一个 sublist
                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 递归

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 (前缀树)【中等】

• 思路：前缀树模板

class Trie:
    def __init__(self):
        self.children = [None]*26  # 指向子节点的指针数组：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)  # 注意需要 isEnd=True，说明字符串被完整搜索到了
    
    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:  # 如果有一棵树是 None，则都必须是 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:  # 如果有一棵树是 None，则都必须是 None
                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()
        queue.append(root)
        ans = []
        while queue:
            n = len(queue)  # 当前层的 node 数
            ans.append(queue[-1].val)  # 将当前层最右侧的 node 存进答案
            for _ in range(n):
                node = queue.popleft()  # 取出当前层的每个 node
                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:  # 注意是在为下一层存，所以 layer_idx=0 时应该从右往左存，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:
        if not root:
            return 0
        def dfs(node):
            if not node:
                return 0
            left = max(dfs(node.left), 0)  # 左树最大路径，要>0 才可取
            right = max(dfs(node.right), 0)  # 右树最大路径，要>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. 将有序数组转换为二叉搜索树【简单】

• 思路：递归

# self.right = right
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 需要非空，并且和最近的元素成对。注意最终 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
        else:
            # 预定义匹配对
            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)
            # 最终 stack 必须被消耗为空才行
            if not stack:
                return True
            else:
                return False

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

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

class Solution:
    def minDistance(self, word1:str, word2:str)->int:
        m, n = len(word1),len(word2)
        dp =[[0]*(n +1)for _ inrange(m +1)]  # (m+1)x(n+1)：dp[i][j]表示 word1 前 i 个字符=>word2 前 j 个字符的操作数（多加 1 行 1 列目的：word1/word2 长度为 0 的边界情况）
        for i inrange(m +1):  # word2 长度为 0，从 word1=>到长度为 i 的 word2 需要删除 i 步
            dp[i][0]= i
        for i inrange(n +1):  # word1 长度为 0，从 word1=>长度为 i 的 word2 需要插入 i 步
            dp[0][i]= i
        for i inrange(1, m +1):
            for j inrange(1, n +1):
                if word1[i -1]== word2[j -1]:  # 如果某 2 个字符相同，则这一步不需要操作
                    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  # 增、删、改三种情况取最小
                    """ dp[i][j - 1] + 1: 增
                        dp[i - 1][j] + 1: 删
                        dp[i - 1][j - 1] + 1: 改 """
        return dp[m][n]  # 从 word1 的前 m 个字符=>word2 的前 n 个字符的最小操作数

168. Excel 表列名称【简单】

• 思路：26 个一组逐步计算

class Solution:
    def convertToTitle(self, columnNumber:int)->str:
        ans = []
        while columnNumber >0:
            columnNumber -=1  # A 是从 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
        while num1 or num2:
            x =int(num1[-1])if num1 else0  # 取最后一位
            y =int(num2[-1])if num2 else0  # 取最后一位
            sum_val = x + y + carry
            value =sum_val%10
            ans =str(value)+ ans
            carry =sum_val//10  # 0 or 1
            num1 = num1[:-1]  # 丢掉最后一位
            num2 = num2[:-1]  # 丢掉最后一位
        if carry:
            ans =str(carry)+ ans
        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)  # 因为元素范围是 1～n，所以只在下标 1～n 的位置记录
        for x in nums:
            flag[x]=1
        for i inrange(1, n +1):  # 只在下标 1～n 的位置记录
            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 =0
        right =len(nums)-1
        while left <= right:
            mid =(left + right)//2
            if nums[mid]== target:
                return mid
            elif nums[mid]> target:
                right = mid -1
            elif nums[mid]< target:
                left = mid +1
        return-1

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

暴力写法，复杂度 O(n^2) 会 timeout：

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

其实只需要在一次遍历过程中记录最低点和当前最大收益：

class Solution:
    def maxProfit(self, prices: List[int])->int:
        min_price =1e4
        max_profit =0
        n =len(prices)
        for i inrange(n):
            min_price =min(min_price, prices[i])  # 动态更新当前最低点
            max_profit =max(max_profit, prices[i]- min_price)  # 记录当前最大收益
        return max_profit

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

• 思路：贪心，累加所有上涨趋势

class Solution:
    def maxProfit(self, prices: List[int])->int:
        n =len(prices)
        ans =0  # 如果仅一条数据（如 [1]），则当天买入卖出，结果是 0
        for i inrange(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]*2for _ inrange(n)]  # 2D 数组：dp[a][b]表示第 a 天的是否持有股票（0=否，1=是）
        dp[0][0], dp[0][1]=0,-prices[0]  # 第 0 天：不持有股票利润 0，持有股票利润-prices[0]
        for i inrange(1, n):
            dp[i][0]=max(dp[i-1][0], dp[i-1][1]+ prices[i])  # 第 i 天不持有股票，如 1）第 i-1 天也不持有，不操作；2）第 i-1 天持有，现卖出
            dp[i][1]=max(dp[i-1][1], dp[i-1][0]- prices[i])  # 第 i 天持有股票，如 1）第 i-1 天也持有，不操作；2）第 i-1 天不持有，现买入
        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.keys():
                count_dict[num]+=1
            else:
                count_dict.update({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) 的，会 timeout：

class Solution:
    def dailyTemperatures(self, temperatures: List[int])-> List[int]:
        n =len(temperatures)
        ans =[0]* n
        for i inrange(n):
            for j inrange(i+1, n):
                if temperatures[j]> temperatures[i]:
                    ans[i]= j - i
                    break
        return ans

从右往左构造单调栈：

class Solution:
    def dailyTemperatures(self, temperatures: List[int])-> List[int]:
        n =len(temperatures)
        ans =[0]* n
        stack =[]  # 用栈存 index
        for i inrange(n-1,-1,-1):
            while stack and temperatures[i]>= temperatures[stack[-1]]:  # 单调栈
                stack.pop()
            if stack:  # 右边存在更大的数（如不存在，则就是 0）
                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 =[]  # 用栈存 index
        for i inrange(n):
            while stack and temperatures[i]> temperatures[stack[-1]]:
                j = stack.pop()
                ans[j]= i - j
            stack.append(i)
        return ans

1. 两数之和【简单】

• 思路：用 hash 存储

最暴力的做法就是双重循环：

class Solution:
    def twoSum(self, nums: List[int], target:int)-> List[int]:
        n =len(nums)
        for i inrange(n):
            for j inrange(i+1, n):
                if nums[i]+ nums[j]== target:
                    return[i, j]

这个问题的本质：给一个 x，判断 targe-x 是否存在于这个数组中？构建一个 hash 表，核心是判断 diff in hash_table：

class Solution:
    def twoSum(self, nums: List[int], target:int)-> List[int]:
        n =len(nums)
        hash_table ={}
        for i inrange(n):
            diff = target - nums[i]  # 先判断再 update 哈希表，避免重复使用当前元素
            if diff in hash_table:
                return[i, hash_table[diff]]
            else:
                hash_table.update({nums[i]: i})

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

• 思路：和第 1 题没本质区别，可以延用 hash 检索，注意 index 从 1 开始，并且输出的 index 要升序

class Solution:
    def twoSum(self, numbers: List[int], target:int)-> List[int]:
        n =len(numbers)
        hash_table ={}
        for i inrange(n):
            diff = target - numbers[i]  # 先判断再 update 哈希表，避免重复使用当前元素
            if diff in hash_table:
                return[i +1, hash_table[diff]+1]if i +1< hash_table[diff]+1else[hash_table[diff]+1, i +1]  # index 从 1 开始，并且注意输出 index 升序
            else:
                hash_table[numbers[i]]= i

但这样做没有利用到数组单增的特点，可以采用类似二分查找的思路，用（相向）双指针解决

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 应该向右走
                left +=1
            elif s > target:  # 如果求和偏大，说明 right 应该向左走
                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 inrange(n-2):
            a = nums[i]
            if i >=1and a == nums[i-1]:  # 如果当前遍历的值和上一步相同，就跳过（避免重复），注意第 2 个元素开始才有前置元素
                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 指针向右（避开重复）、right 指针向左（避开重复）
                    left +=1
                    while left < right and nums[left]== nums[left -1]:
                        left +=1
                    right -=1
                    while left < right and nums[right]== nums[right +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 个高频元素【中等】

• 思路：

下面是最暴力的做法，用到了排序，复杂度 O(nlogn)：

class Solution:
    def topKFrequent(self, nums: List[int], k:int)-> List[int]:
        n =len(nums)
        ans =[]
        hash_table ={}
        for i inrange(n):
            if nums[i]notin hash_table:
                hash_table[nums[i]]=1
            else:
                hash_table[nums[i]]+=1
        # 降序排列：[(k1, v1), (k2, v2), ...]
        rank_value =sorted(hash_table.items(), key=lambda x:x[1], reverse=True)
        i =0
        for key, value in rank_value:
            i +=1
            ans.append(key)
            if i == k:
                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 inrange(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_right =max(height[left], max_left),max(height[right], max_right)  # 动态更新两边的最高点
            # 较低的那边去接雨水（说明有容纳雨水的可能性）
            if max_left <= max_right:
                ans += max_left - height[left]  # 统计低洼的情况
                left +=1
            if max_left > max_right:
                ans += max_right - height[right]  # 统计低洼的情况
                right -=1
        return ans

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

• 思路：相向双指针，比第 42 题接雨水还是要简单不少

class Solution:
    def maxArea(self, height: List[int])->int:
        n =len(height)
        if n ==2:
            returnmin(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
            elif height[left]> height[right]:
                right -=1
        return ans

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

• 思路：二分法搜索边界

class Solution:
    def countTarget(self, scores: List[int], target:int)->int:
        n =len(scores)
        def helper(target):
            left, right =0, n -1
            while left <= right:
                mid =(left + right)//2
                if scores[mid]< target:
                    left = mid +1
                elif scores[mid]>= target:
                    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(target):
            left, right =0, n -1
            while left <= right:
                mid =(left + right)//2
                if nums[mid]< target:
                    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 notin hash_table:
                hash_table[a]=1
            else:
                hash_table[a]+=1
            # 得先统计上当前的元素
            if hash_table[a]> thre:
                return a

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 =[],[],[]  # 将大于、小于、等于 pivot 的元素划分到三个列表中
            for x in nums:
                if x > pivot:
                    big.append(x)
                elif x < pivot:
                    small.append(x)
                else:
                    equal.append(x)
            iflen(big)>= k:  # 第 k 大的元素在 big 中，递归划分 big
                return quick_select(big, k)
            iflen(big)+len(equal)< k:  # 第 k 大的元素在 small 中，递归划分 small
                return quick_select(small, k -len(big)-len(equal))
            return pivot  # 第 k 大的元素在 equal 中，返回 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 inenumerate(nums):  # x: nums[right]
            s += x  # 加一个右边的端点进来
            while s >= target:
                ans =min(ans, right - left +1)
                s -= nums[left]
                left +=1
        return ans if ans <= n else0

优化一下 while 循环的代码，下面的代码更直观：

class Solution:
    def minSubArrayLen(self, target:int, nums: List[int])->int:
        n =len(nums)
        ans = n +1
        s =0  # 初始化滑窗中的和
        left =0  # 初始化滑窗的左端点
        # 枚举滑窗右端点
        for right, x inenumerate(nums):  # x: nums[right]
            s += x  # 加一个右边的端点进来
            while s - nums[left]>= target:  # 如果减去左端点还>=targe，可以安全丢掉
                s -= nums[left]
                left +=1
            if s >= target:
                ans =min(ans, right - left +1)
        return ans if ans <= n else0

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

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

class Solution:
    def minWindow(self, s:str, t:str)->str:
        from collections import Counter
        cnt_win = Counter()  # s 的滑窗字符计数器
        cnt_t = Counter(t)  # t 的字符计数器
        ans_left, ans_right =-float('inf'), float('inf')
        left =0
        for right, x inenumerate(s):  # 枚举右端点
            cnt_win[x]+=1
            while cnt_win >= cnt_t:  # s 滑窗能覆盖 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 >=0else""

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

• 思路：滑动窗口

class Solution:
    def lengthOfLongestSubstring(self, s:str)->int:
        n =len(s)
        ans =0
        visited =set()  # 用 set 检测重复元素
        left =0
        for right, x inenumerate(s):  # x: s[right]
            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] """
        # 冒泡排序 O(n^2)
        n =len(nums)
        for i inrange(1, n):  # n-1 趟：每趟可以将一个大数放到最后
            for j inrange(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 quicksort(arr, low, high):
            if low < high:
                pivot_idx = partition(arr, low, high)
                quicksort(arr, low, pivot_idx -1)
                quicksort(arr, pivot_idx +1, high)
            return arr
        
        def partition(arr, low, high):
            r = random.randint(low, high)
            arr[r], arr[high]= arr[high], arr[r]
            pivot = arr[high]
            slow = fast = low
            while fast <= high:
                if arr[fast]< pivot:
                    arr[fast], arr[slow]= arr[slow], arr[fast]
                    slow +=1
                fast +=1
            arr[high], arr[slow]= arr[slow], arr[high]
            return slow
        
        n =len(nums)
        nums = quicksort(nums,0, n -1)
        return nums

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 inrange(len(nums)):
            if nums[right]!=0:
                nums[right], nums[left]= nums[left], nums[right]
                left +=1
        return nums

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

class Solution(object):
    def moveZeroes(self, nums):
        """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """
        right =len(nums)-1
        left =0
        while left < right:
            if nums[left]==0:
                nums[right], nums[left]= nums[left], nums[right]
                right -=1
                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 inrange(len(nums)):
            if nums[i]!=0:
                nums[idx_non_zero]= nums[i]
                idx_non_zero +=1
        for i inrange(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 交换到前面了，下次应该直接在该位置 i 和 p0 交换）

class Solution:
    def sortColors(self, nums: List[int])->None:
        """ Do not return anything, modify nums in-place instead. """
        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 =[]
        # 身高 h 降序，相同 h 中 k 升序：先处理高个子，相同身高里先处理前面人少的
        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
            elif nums[left]**2> nums[right]**2:
                ans.append(nums[left]**2)
                left +=1
        return ans[::-1]

31. 下一个排列【中等】

• 思路：先从右往左找到第一个较小元素，然后和右侧比其大一点的元素交换，再把右侧元素翻转为升序

class Solution:
    def nextPermutation(self, nums: List[int])->None:
        """ Do not return anything, modify nums in-place instead. """
        n =len(nums)
        # 从右往左找到第一个小于右侧邻居的元素 nums[i]，nums[i]右侧一定是递减
        # 为什么 nums[i]右侧一定是递减？反证法：如果不是，说明 nums[i]不应该是第一个被找到的
        i = n -2
        while i >=0and nums[i]>= nums[i +1]:
            i -=1
        # 如果找到了 nums[i]，继续找 nums[i]右边大于它且最小的元素 nums[j]
        if i >=0:
            j = n -1
            while nums[j]<= nums[i]:
                j -=1
            nums[i], nums[j]= nums[j], nums[i]  # 交换两个元素
        # 将右侧的元素翻转：从递减到递增，保证右侧字典序最小
        # 如果找不到（即 i=-1），说明当前是最大排列，直接翻转即可得到最小排列
        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]  # 返回 d 中 key=sorted_s 的 value，如果 value 为空，返回 []
            # 字典存储：key=排序后的字符串，value=原始的字符串
            # 将具有相同排序后的字符串放在同一个 value 列表中
        return d.values()

78. 子集【中等】

思路：维护一个 ans 列表，遍历 nums 中所有元素，每个元素都将和 ans 列表中每一项进行组合，然后放进 ans 列表中（难点在于区分 python 中 list 的加法和 append，很容易在[][]嵌套结构上出错。加法是把两个列表中的元素合并起来，append 是往列表中添加一整个元素）

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[:])  # 注意！这里需要用 list(nums)活着 nums[:]，相当于对 nums 进行了一次浅拷贝
                return
            for i inrange(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[:])  # 注意！这里需要用 list(nums)活着 nums[:]，相当于对 nums 进行了一次浅拷贝
                return
            dic =set()  # 用集合去重
            for i inrange(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 才能支持交换操作，并且可以直接 list(set(x))实现去重

class Solution:
    def goodsOrder(self, goods:str)-> List[str]:
        n =len(goods)
        lst =list(goods)  # 必须把字符串转 list，才支持在回溯时交换元素
        ans =[]
        # 回溯法
        def dfs(start):
            if start == n:
                ans.append(''.join(lst))
                return
            for i inrange(start, n):
                lst[i], lst[start]= lst[start], lst[i]
                dfs(start +1)
                lst[i], lst[start]= lst[start], lst[i]
        dfs(0)
        returnlist(set(ans))  # list 中元素是字符串时，可以直接转 set 然后再转 list 去重

链表

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 拿到
            curr.next= prev  # curr 的后面接 prev，即链表方向反转
            # prev 和 curr 一起往后走
            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
        # 用 p0 节点定位 left 位置左边的节点
        # 需要加入哨兵节点，为什么？因为当 left=1 时，left 位置左边不存在节点，哨兵节点用于处理特殊情况
        dummy = ListNode(next=head)
        p0 = dummy
        for _ inrange(left -1):
            p0 = p0.next  # 此时，p0 走到了 left 位置的左边
        cur, prev = p0.next,None
        for _ inrange(right - left +1):  # 反转中间的元素
            next_node = cur.next
            cur.next= prev
            prev = cur
            cur =next_node
        # 处理最后两个指向
        p0.next.next= cur  # 把图中的 1 指向 5
        p0.next= prev  # 把图中的 1 指向 4
        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
        ans =(l == l[::-1])
        return ans

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()  # 用 hash 避免 timeout，因为 hash 的搜素是 O(1)，而 list 是 O(n)
        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. 环形链表【简单】

• 思路：用 hash 存储遍历到的节点，如果遍历到重复节点，说明是环形

class Solution:
    def hasCycle(self, head: Optional[ListNode])->bool:
        if not head:
            return False
        link_set =set()  # 用 hash 而不是 list 的原因：hash 的搜索更快
        cur = head
        while cur:
            if cur in link_set:  # 如果是环形，则会返回 True 跳出循环
                return True
            link_set.add(cur)
            cur = cur.next  # 如果不是环形，则一定会执行到 cur=None 跳出循环
        return False

如果只用 O(1) 空间解决这个问题，需要快慢指针（追及问题）

class Solution:
    def hasCycle(self, head: Optional[ListNode])->bool:
        if not head:
            return False
        # 核心：设置快慢指针，慢指针每次走 1 步，快指针走 2 步
        # 如果不存在环，则快指针会走到尽头，返回 False
        # 如果存在环，则快指针迟早会在环中追上慢指针，返回 True
        slow, fast = head, head.next
        while fast and fast.next:
            if fast == slow:
                return True
            slow = slow.next
            fast = fast.next.next
        return False

142. 环形链表 II【中等】

• 思路：和上一题并无区别，改成返回节点

class Solution:
    def detectCycle(self, head: Optional[ListNode])-> Optional[ListNode]:
        if not head:
            return None
        link_set =set()  # 用 hash 而不是 list 的原因：hash 的搜索更快
        cur = head
        while cur:
            if cur in link_set:  # 如果是环形，则会返回 cur 跳出循环
                return cur
            link_set.add(cur)
            cur = cur.next  # 如果不是环形，则一定会执行到 cur=None 跳出循环
        return None

如果想用 O(1) 空间解决，同样需要快慢指针，但是还需要多一个步骤定位环的入口

class Solution:
    def detectCycle(self, head: Optional[ListNode])-> Optional[ListNode]:
        if not head:
            return None
        # 设置快慢指针，定位相遇时 slow 指针在环中的位置
        fast, slow = head, head
        flag =False  # flag 标记是否有环
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                flag =True
                break
        # 如果不存在环，则返回 None
        if not flag:
            return None
        # 如果存在环，则进一步计算环的入口
        # 再加入一个指针从头开始走，速度为 1，和环中的 slow 指针相遇时，即环的入口
        tmp = head
        while tmp != slow:
            slow = slow.next
            tmp = tmp.next
        return slow

148. 排序链表【中等】

最暴力的做法，转列表排序后放回链表：

class Solution:
    def sortList(self, head: Optional[ListNode])-> Optional[ListNode]:
        cur = head  # 链表转列表
        head_list =[]
        while cur:
            head_list.append(cur.val)
            cur = cur.next
        head_list.sort()  # 列表升序排列
        # 列表转链表
        cur = head
        i =0
        while cur:
            cur.val = head_list[i]
            i +=1
            cur = cur.next
        return head

归并排序

class Solution:
    def sortList(self, head: Optional[ListNode])-> Optional[ListNode]:
        if not head or not head.next:
            return head
        # 步骤 1. 递归每次分割成 2 组
        slow, fast = head, head.next
        while fast and fast.next:  # 定位中点的位置
            slow = slow.next  # slow 走一步
            fast = fast.next.next  # fast 走两步
        mid = slow.next
        slow.next=None
        left = self.sortList(head)  # 递归
        right = self.sortList(mid)  # 递归
        # 步骤 2. 迭代两两合并在一起（有序）
        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
        else:
            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)  # 在头节点前面加一个 dummy 节点（更方便支持删除头节点的边界情况）
        right = dummy
        for _ inrange(n):  # 右指针先往右走 n 步
            right = right.next
        left = dummy  # 左指针初始和右指针保持 n 的距离
        while right.next:  # 右指针走到末尾前，左右指针同时向右走
            left = left.next
            right = right.next
        left.next= left.next.next  # 右指针走到末尾了，左指针刚到'待删除节点'的前面，开始跳过
        return dummy.next  # dummy 是头节点之前的虚拟节点，所以要返回真正的头节点 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:  # 发现相同值的节点了！要通过循环从 cur.next 开始跳过
                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 else0  # 长度不够就补 0
            y = l2.val if l2 else0  # 长度不够就补 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()  # 答案链表，初始化一个 dummy 节点，答案节点都存储在后面
        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  # 跳过初始化的第一个 dummy 节点

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. 汉明距离【简单】

比特位的模板解法：

class Solution:
    def hammingDistance(self, x:int, y:int)->int:
        bit_num =32
        dist =0  # 初始化答案
        for i inrange(bit_num):
            one_bit_x =1if x &(1<< i)else0  # x 的每一位是否为 1
            one_bit_y =1if y &(1<< i)else0  # y 的每一位是否为 1
            if one_bit_x != one_bit_y:
                dist +=1
        return dist

思路：直接异或再计数，注意 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')  # 统计 1 的数目
        return dist

338. 比特位计数【简单】

比特位的模板解法：

class Solution:
    def countBits(self, n:int)-> List[int]:
        bit_num =32
        ans =[]
        for i inrange(n +1):  # n 个 sample
            one_bit =[]
            for b inrange(bit_num):
                if(1<< b)& i:
                    one_bit.append(1)
            ans.append(sum(one_bit))
        return ans

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

class Solution(object):
    def countBits(self, n):
        """ :type n: int :rtype: List[int] """
        ans =[]
        for i inrange(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 =[]  # 记录每一位是否为 1（是=1，否=0）
        for i inrange(bit_num):  # if n & (2 ** i):
            if n &(1<< i):  # 从低往高判断每一位是否为 1（比如 5&010=101&010=000，则说明第 2 位不是 1）
                one_bit.append(1)
        ans =sum(one_bit)
        return ans

231. 2 的幂【简单】

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

class Solution:
    def isPowerOfTwo(self, n:int)->bool:
        if n <=0:  # 2 的幂次一定是正数！
            return False
        num_bits =32
        bits =[]
        for i inrange(num_bits):
            cur_bit =1if(2** i)& n else0
            bits.append(cur_bit)
        # 2 的幂次转二进制一定有且只有一个 1
        returnTrueif bits.count(1)==1elseFalse

数组计算

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

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

class Solution:
    def productExceptSelf(self, nums: List[int])-> List[int]:
        n =len(nums)
        ans =[0]* n
        # 计算前缀元素乘积
        front_mul =[1]+[0]*(n -1)  # [1, 0, 0, ...]
        for i inrange(1, n):
            front_mul[i]= front_mul[i -1]* nums[i -1]
        # 计算后缀元素乘积
        behind_mul =[0]*(n -1)+[1]  # [0, ..., 0, 1]
        for i inrange(n-2,-1,-1):
            behind_mul[i]= behind_mul[i +1]* nums[i +1]
        # 把前缀乘积和后缀成绩再乘起来得到答案
        for i inrange(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 inrange(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 inrange(n):
            dp[i]=max(nums[i], dp[i -1]+ nums[i])
        returnmax(dp)

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

• 思路：DP

class Solution:
    def lengthOfLIS(self, nums: List[int])->int:
        n =len(nums)
        if n ==1:
            return1
        dp =[1]* n
        for i inrange(n):
            for j inrange(i):
                if nums[i]> nums[j]:
                    dp[i]=max(dp[i], dp[j]+1)
        returnmax(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 -1in hash_set:  # 说明 num 不是连续序列的开头
                continue  # 跳过，因为希望从连续序列的开头开始计数
            elif num -1notin hash_set:  # 说明 num 是连续序列的开头，可以计数了
                length_from_here =1  # 从本次起点出发，能达到的最大长度
                cur_num = num
                while cur_num +1in hash_set:
                    cur_num +=1
                    length_from_here +=1
                ans =max(ans, length_from_here)  # 更新最大答案长度
        return ans

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

下面是最简单，但是会 timeout 的写法：

class Solution:
    def findAnagrams(self, s:str, p:str)-> List[int]:
        window_size =len(p)
        n =len(s)
        ans =[]
        p_cnt =[0]*26
        for c in p:
            p_cnt[ord(c)-ord('a')]+=1
        for i inrange(n):
            window_s = s[i:i+window_size]  # "cba"
            iflen(window_s)!= window_size:
                continue
            # if sorted(window_s) == sorted(p): # O(nlogn)会 timeout
            # ans.append(i)
            window_cnt =[0]*26
            for c in window_s:
                window_cnt[ord(c)-ord('a')]+=1
            # print(p_cnt, window_cnt)
            if p_cnt == window_cnt:
                ans.append(i)
        return ans

下面是完美的做法，每次滑窗实际上只需要更新左右两端两个元素的统计情况：

class Solution:
    def findAnagrams(self, s:str, p:str)-> List[int]:
        window_size =len(p)
        n =len(s)
        ans =[]
        window_cnt =[0]*26  # 维持一个随着窗口更新的字符统计分布（每次只改变 2 个）
        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
        # print(p_cnt, window_cnt)
        if p_cnt == window_cnt:
            ans.append(0)
        for i inrange(1, n - window_size +1):
            left_del_char, right_new_char = s[i -1], s[i + window_size -1]  # 记录要删除的左字符、要添加的右字符
            # print(left_del_char, right_new_char)
            window_cnt[ord(left_del_char)-ord('a')]-=1
            window_cnt[ord(right_new_char)-ord('a')]+=1
            # print(p_cnt, window_cnt)
            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  # 从右往左遍历 num 的每一位
        carry =0
        ans =[]
        while i >=0or k !=0:  # num 和 k 长度可能不一致，只要还有没遍历完的，就要继续算
            x = num[i]if i >=0else0  # 不够长就补 0
            y = k %10if k !=0else0  # 不够长就补 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  # rowIndex 是从 0 开始的，注意行数要 +1
        T =[[1]*(i+1)for i inrange(row_num)]  # rowIndex * 1,2,3,...
        for i inrange(row_num):
            for j inrange(1, i):  # 不算每行的首尾，默认是 1
                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:
            returnmax(nums[0], nums[1])  # 两间房，只能偷一家最有钱的
        dp =[0]* n  # dp[i]表示前 i 间房最高金额
        dp[0]= nums[0]
        dp[1]=max(nums[0], nums[1])
        for i inrange(2, n):  # 当前 dp[i]的可能性：
            # 1）前一间偷过了 dp[i-1]，这间不能偷；2）前一间没偷，这间还可以偷 nums[i]
            dp[i]=max(dp[i -1], dp[i -2]+ nums[i])
        return dp[-1]

213. 打家劫舍 II【中等】

• 思路：DP，和第 198 题没有本质区别，不过首尾两间不能同时偷，所以需要分情况讨论首尾偷哪个

class Solution:
    def rob(self, nums: List[int])->int:
        # 核心：第 0 天和第 n-1 天不能同时偷
        n =len(nums)
        if n ==1:
            return nums[0]
        if n ==2:
            returnmax(nums[0], nums[1])
        dp =[0]* n
        # 情况 1：如果第 0 天可以偷，第 n-1 天不能偷
        dp[0]= nums[0]
        dp[1]=max(nums[0], nums[1])
        for i inrange(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 inrange(3, n):
            dp[i]=max(dp[i -1], dp[i -2]+ nums[i])
        ans2 = dp[-1]
        returnmax(ans1, ans2)

337. 打家劫舍 III【中等】

• 思路：树形 DP

class Solution:
    def rob(self, root: Optional[TreeNode])->int:
        def dfs(node):
            # 返回两个值：偷这个节点的最大收益、不偷这个节点的最大收益
            if not node:
                return0,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
        returnmax(dfs(root))

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

• 思路：滑窗 + 单调队列

class Solution:
    def maxSlidingWindow(self, nums: List[int], k:int)-> List[int]:
        n =len(nums)
        ans =[]
        q = deque()  # 双端队列
        for i, x inenumerate(nums):  # 入队
            while q and x >= nums[q[-1]]:
                q.pop()
            q.append(i)  # 记录 index，方便后面判断距离进行出队
            # 出队
            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:
        # 假设：nums 中元素和是 s
        # 正数之和（+）=p，负数之和（-）=s-p
        # p-(s-p)=target => p=(target+s)/2
        # 转化成了一个'0-1 背包问题'：从 nums 中选若干个数，使和为 (target+sum(nums))/2
        n =len(nums)
        target +=sum(nums)
        if target <0or target %2!=0:  # 必须正数且偶数
            return0
        target //=2
        @lru_cache(None)  # 用@cache 实现'记忆化'搜索，缓存中间结果，避免重复计算（用空间换时间）
        def dfs(i, target):
            # dfs(i, target)表示 nums 前 i 个数中，选中数之和为 target 的方案数
            if i <0:  # 没有数可选
                return1if target ==0else0  # target==0 表示刚好 1 种方案，返回 1，否则返回 0
            if nums[i]> target:  # 如果这个数比 target 大，则不选
                return dfs(i-1, target)
            return dfs(i-1, target)+ dfs(i-1, target-nums[i])  # 选或不选当前数的情况相加
        return dfs(n-1, target)

322. 零钱兑换【中等】

• 思路：完全背包

class Solution:
    def coinChange(self, coins: List[int], amount:int)->int:
        n =len(coins)
        @lru_cache(None)
        def dfs(i, t):  # 表示 coins 中前 i 个硬币能凑出 t 的最小硬币数
            if i <0:  # 没有硬币了
                return0if t ==0else inf  # 如果要凑的金额是 0，则需要 0 个硬币，否则 inf（凑不出）
            if coins[i]> t:  # 当前硬币超过要凑的数，不选
                return dfs(i-1, t)
            returnmin(dfs(i-1, t), dfs(i, t-coins[i])+1)  # 关键问题：为什么是 dfs(i, t-coins[i])而不是 dfs(i-1, t-coins[i])？
            # 因为'每种硬币可以使用无限次'，所以选了一枚 coins[i]后，仍可以继续选当前种类的硬币，所以保持 i 不变
        ans = dfs(n-1, amount)
        return ans if ans < inf else-1

数据结构设计

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

最简单的写法，纯用 list 实现，list 支持 O(1) 的 getRandom，但是 insert 和 remove 都需要判断元素存在性，所以复杂度是 O(n) 的：

class RandomizedSet:
    def __init__(self):
        self.nums =[]
    
    def insert(self, val:int)->bool:
        if val notin self.nums:
            self.nums.append(val)
            returnTrue
        returnFalse
    
    def remove(self, val:int)->bool:
        if val in self.nums:
            idx = self.nums.index(val)
            del self.nums[idx]
            returnTrue
        returnFalse
    
    def getRandom(self)->int:
        if not self.nums:
            return[]
        return choice(self.nums)

把上面的 list 改成 set 也可以，set 支持 O(1) 的 insert 和 remove，不过注意 set 无法通过下标取元素（即没有 choice），所以无法实现 getRandom。必须要先 choice(list(self.nums))，不过注意这个转换是 O(n) 的。 如果要实现 O(1) 复杂度，可以用一个 hash table 记录 index 和值的关系：

class RandomizedSet:
    def __init__(self):
        self.nums =[]
        self.hash={}  # {val: index}
    
    def insert(self, val:int)->bool:
        if val notin self.hash:
            self.nums.append(val)
            self.hash[val]=len(self.nums)-1  # {val: index}
            returnTrue
        returnFalse
    
    def remove(self, val:int)->bool:
        if val in self.hash:
            index = self.hash[val]  # 接下来是重点：如何 O(1)丢弃index位置的元素？只能用pop()操作
            self.nums[index]= self.nums[-1]  # 把末尾的元素值备份到要丢的位置上
            self.hash[self.nums[-1]]= index  # 记录末尾元素的 hash：index 改成要丢的那个位置（补位）
            del self.hash[val]  # 丢弃 hash 中 val 及对应的 index
            self.nums.pop()  # 丢弃末尾元素
            returnTrue
        returnFalse
    
    def getRandom(self)->int:
        if not self.nums:
            return[]
        return choice(self.nums)

146. LRU 缓存【中等】

• 思路：字典 + 双向链表

用 Python 库实现：

class LRUCache:
    def __init__(self, capacity:int):
        self.capacity = capacity
        self.cache = OrderedDict()  # dict + 双向链表
    
    def get(self, key:int)->int:
        if key notin self.cache:  # 找不到这个 key
            return-1
        self.cache.move_to_end(key, last=False)  # 找到这个 key，移动到链表表头
        return self.cache[key]
    
    def put(self, key:int, value:int)->None:
        self.cache[key]= value  # 加入这个 key-value 对
        self.cache.move_to_end(key, last=False)  # 移动到链表表头
        iflen(self.cache)> self.capacity:  # 超过容量了，剔除最后一个
            self.cache.popitem()

手写字典 + 双向链表【TODO】：

class Node:
    # 提高访问属性的速度，并节省内存
    __slots__ ='prev','next','key','value'
    
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value

class LRUCache:
    def __init__(self, capacity:int):
        self.capacity = capacity
        self.dummy = Node()  # 哨兵节点
        self.dummy.prev = self.dummy
        self.dummy.next= self.dummy
        self.key_to_node ={}  # 获取 key 对应的节点，同时把该节点移到链表头部
    
    def get_node(self, key:int)-> Optional[Node]:
        if key notin self.key_to_node:  # 没有这本书
            returnNone
        node = self.key_to_node[key]  # 有这本书
        self.remove(node)  # 把这本书抽出来
        self.push_front(node)  # 放到最上面
        return node
    
    def get(self, key:int)->int:
        node = self.get_node(key)  # get_node 会把对应节点移到链表头部
        return node.value if node else-1
    
    def put(self, key:int, value:int)->None:
        node = self.get_node(key)  # get_node 会把对应节点移到链表头部
        if node:  # 有这本书
            node.value = value  # 更新 value
            return
        self.key_to_node[key]= node = Node(key, value)  # 新书
        self.push_front(node)  # 放到最上面
        iflen(self.key_to_node)> self.capacity:  # 书太多了
            back_node = self.dummy.prev
            del self.key_to_node[back_node.key]
            self.remove(back_node)  # 去掉最后一本书
    
    # 删除一个节点（抽出一本书）
    def remove(self, x: Node)->None:
        x.prev.next= x.next
        x.next.prev = x.prev
    
    # 在链表头添加一个节点（把一本书放到最上面）
    def push_front(self, x: Node)->None:
        x.prev = self.dummy
        x.next= self.dummy.next
        x.prev.next= x
        x.next.prev = x

矩阵

200. 岛屿数量【中等】

• 思路：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 <0or r > row_num -1or c <0or c > col_num -1:
                return  # 指 dfs 退一层
            if grid[r][c]!="1":  # 如果当前访问的位置不是 1，则退出递归（0 说明不满足；2 说明访问过了，不能走重复路）
                return  # 指 dfs 退一层
            grid[r][c]="2"  # 定义 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 inrange(row_num):
            for c inrange(col_num):
                if grid[r][c]=='1':  # 遍历到了岛屿
                    dfs(grid, r, c)  # 递归：深度优先搜索
                    ans +=1  # 答案 +1
        return ans

221. 最大正方形【中等】

• 思路：DP

class Solution:
    def maximalSquare(self, matrix: List[List[str]])->int:
        rows, cols =len(matrix),len(matrix[0])
        if rows ==0or cols ==0:  # 如果正方形不存在，返回 0
            return0
        dp =[[0]* cols for _ inrange(rows)]  # dp[i][j]表示以 (i, j) 为右下角的正方形的边长
        max_side =0
        for i inrange(rows):
            for j inrange(cols):
                if matrix[i][j]=='1':  # 只有当遍历到'1'这个位置，才能去探索
                    if i ==0and j ==0:  # 右下角在边界上，边长只能是 1
                        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:
        """ Do not return anything, modify matrix in-place instead. """
        rows =len(matrix)
        cols =len(matrix[0])
        row_flag, col_flag =[0]* rows,[0]* cols  # 设置行列 flag：初始化 0，matrix 某行某列出现 0 时则改成 1
        for r inrange(rows):
            for c inrange(cols):
                if matrix[r][c]==0:  # 如果 matrix 某个元素是 0，则把行列 flag 改成 1
                    row_flag[r]=1
                    col_flag[c]=1
        for r inrange(rows):
            for c inrange(cols):
                if row_flag[r]or col_flag[c]:  # 如果行或列 flag 是 1，就需要把 matrix 的整行整列改成 0
                    matrix[r][c]=0

48. 旋转图像【中等】

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

class Solution:
    def rotate(self, matrix: List[List[int]])->None:
        """ Do not return anything, modify matrix in-place instead. """
        # 顺时针旋转 90 度 = 水平翻转 + 主对角线翻转
        n =len(matrix)
        # 水平翻转
        for i inrange(n //2):
            for j inrange(n):
                matrix[i][j], matrix[n - i -1][j]= matrix[n - i -1][j], matrix[i][j]
        # 主对角线翻转
        for i inrange(n):
            for j inrange(i):
                matrix[i][j], matrix[j][i]= matrix[j][i], matrix[i][j]

也可以用辅助矩阵实现变换

class Solution:
    def rotate(self, matrix: List[List[int]])->None:
        """ Do not return anything, modify matrix in-place instead. """
        # 顺时针旋转 90 度：原来的 i 行 j 列 => 旋转后的倒数 i 列 j 行
        n =len(matrix)
        matrix_rot =[[0]* n for _ inrange(n)]
        for i inrange(n):
            for j inrange(n):
                matrix_rot[j][n - i -1]= matrix[i][j]
        matrix[:]= matrix_rot

在此基础上，可以进一步避免辅助矩阵【TODO】

class Solution:
    def rotate(self, matrix: List[List[int]])->None:
        n =len(matrix)
        for i inrange(n //2):
            for j inrange((n +1)//2):
                matrix[i][j], matrix[n - j -1][i], matrix[n - i -1][n - j -1], matrix[j][n - i -1] \
                = matrix[n - j -1][i], matrix[n - i -1][n - j -1], matrix[j][n - i -1], 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 _ inrange(cols)]  # cols * rows
        for i inrange(rows):
            for j inrange(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

• 思路：牛顿迭代 公式：$x_{n+1}=x_n - \frac{f(x_n)}{f'(x_n)}$ 对于 $x^2=C$，有 $f(x)=x^2-C$，则 $f'(x)=2x$，所以 $x_{n+1}=x_n-\frac{x_n^2-C}{2x_n}=\frac{1}{2}(x_n+\frac{C}{x_n})$

class Solution:
    def mySqrt(self, x:int)->int:
        if x ==0:
            return0
        x0 = x
        whileTrue:
            x1 =0.5*(x0 + x / x0)
            ifabs(x0 - x1)<1e-6:
                break
            x0 = x1
        returnint(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)$，这两种情况概率一致，因此把 $P(0,1)$ 看作生成 0，$P(1,0)$ 看作生成 1 即可。伪代码如下：

import random
defrandom_coin(p):  # 生成概率为 p 的 0/1
    return1if random.random()< p else0

def Rand1(self):  # 周期性地产生 2 个数，直到生成 01 或者 10 才满足
    i1 = random_coin()  # 生成 0/1
    i2 = random_coin()  # 生成 0/1
    if i1 ==0and i2 ==1:
        return0
    elif i1 ==1and i2 ==0:
        return1
    else:
        return Rand1()  # 重新生成

接下来考虑如何等概率生成 1～N 的数。对于这个范围，需要 $k = log_2n+1$ 位，所以调用 $k$ 次 Rand1() 函数即可。伪代码如下：

defRandN(self, n:int):  # 以 1/n 的概率返回 1~n 之间的数
    # int(res, 2)指二进制转十进制
    k = math.log2(n)+1
    res =''
    for _ inrange(k):
        res +=str(Rand1())
    ifint(res,2)> n:
        return RandN(n)  # 重新生成
    else:
        returnint(res,2)

343. 整数拆分【中等】

• 思路：DP

class Solution:
    def integerBreak(self, n:int)->int:
        if n ==1:
            return1
        dp =[0]*(n +1)  # dp[i]表示整数 i 时的乘积最大值
        dp[1]=1
        for i inrange(2, n +1):
            for j inrange(0, i):  # 对于整数 i，可以拆分成 j 和 i-j
                dp[i]=max(dp[i], j *(i - j), j * dp[i - j])  # j*(i-j)表示两段都不能拆，j*dp[i-j]表示有一段还能拆（和 dp[j]*(i-j)是对称的）
        return dp[n]

263. 丑数【简单】

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

class Solution:
    def isUgly(self, n:int)->bool:
        if n <=0:
            returnFalse
        while n %2==0:
            n //=2
        while n %3==0:
            n //=3
        while n %5==0:
            n //=5
        returnTrueif n ==1elseFalse

264. 丑数 II【中等】

• 思路：三指针分别定为三个因子的增长，每次取最小值，并更新该指针

class Solution:
    def nthUglyNumber(self, n:int)->int:
        a =[0]*(n +1)  # 下标从 1 开始更方便
        a[1]=1
        p2, p3, p5 =1,1,1  # 三指针
        for i inrange(2, n +1):
            num2, num3, num5 = a[p2]*2, a[p3]*3, a[p5]*5
            a[i]=min(num2, num3, num5)
            print(a[i], num2, num3, num5)
            if a[i]== num2:
                p2 +=1
            if a[i]== num3:
                p3 +=1
            if a[i]== num5:
                p5 +=1
        # 不能用 elif 的原因：6=3*2 同时 6=2*3，所以 p2、p3 都要加 1 才行
        return a[n]

258. 各位相加【简单】

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

class Solution:
    def addDigits(self, num:int)->int:
        if num ==0:
            return0
        while num >=10:  # 只要不是个位数，就要继续
            sum_val =0
            while num >0:
                sum_val += num %10
                num //=10
            num =sum_val
        return num

进阶：用 O(1) 复杂度完成，需要考虑数的性质。最终结果一定是 num 不断减 9 得到的个位数，称为'数根'，所以结果其实就是模 9 的余数，但需要考虑 0 和 9 的倍数特殊情况

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

也可以统一写法如下：

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

202. 快乐数【简单】

• 思路：哈希判断重复元素

class Solution:
    def isHappy(self, n:int)->bool:
        if n ==1:
            returnTrue
        def compute_next(n):
            sum_val =0
            while n >0:
                sum_val +=(n %10)**2
                n //=10
            return sum_val
        # 核心思想：如果结果回不到 1，则一定会出现重复的数（当然也可以用快慢指针做，参考 141.环形链表）
        hash_table =set()
        while n !=1:
            if n in hash_table:
                break
            hash_table.add(n)
            n = compute_next(n)
        if n ==1:
            returnTrue
        returnFalse

如果空间复杂度 O(1)，则用快慢指针判断重复元素，参考 141. 环形链表。

class Solution:
    def isHappy(self, n:int)->bool:
        if n ==1:
            returnTrue
        def compute_next(n):
            sum_val =0
            while n >0:
                sum_val +=(n %10)**2
                n //=10
            return sum_val
        # 核心思想：快慢指针判断环，参考 141.环形链表
        slow, fast = n, compute_next(n)
        whileTrue:
            if slow == fast:  # 快慢指针相遇，说明出现重复数，一定到不了 1
                returnFalse
            if fast ==1:  # 如果能到 1，则一定是 fast 指针先到
                returnTrue
            slow = compute_next(slow)  # slow 指针走一步
            fast = compute_next(compute_next(fast))  # fast 指针走两步

图

207. 课程表【中等】

• 思路：用 DFS 判断图是否存在环

class Solution:
    def canFinish(self, numCourses:int, prerequisites: List[List[int]])->bool:
        # 思路：判断节点构成的图是否存在环，存在说明无法存在冲突，则无法完成课程
        # 构图：存储节点与其后继节点
        graph =[[]for _ inrange(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)
        states =[0]* numCourses  # 定义节点状态
        """ 0：节点 x 未被访问
            1：节点 x 正在访问中，dfs(x)尚未结束
            2：节点 x 已经完全访问完，说明从 x 出发无法找到环 """
        # DFS：返回 True 表示找到了环
        def dfs(x):
            states[x]=1
            for node in graph[x]:
                if states[node]==1or(states[node]==0and dfs(node)==True):
                    returnTrue
            states[x]=2
            returnFalse
        for i, s inenumerate(states):
            if s ==0and dfs(i)==True:  # 存在环
                returnFalse
        returnTrue

64. 最小路径和【中等】

• 思路：DP

class Solution:
    def minPathSum(self, grid: List[List[int]])->int:
        rows, cols =len(grid),len(grid[0])
        dp =[[0]* cols for _ inrange(rows)]  # dp[i][j]表示在第 i 行 j 列的最小路径和
        dp[0][0]= grid[0][0]  # 处理第 1 列
        for i inrange(1, rows):
            dp[i][0]= dp[i -1][0]+ grid[i][0]
        # 处理第 1 行
        for j inrange(1, cols):
            dp[0][j]= dp[0][j -1]+ grid[0][j]
        # 处理中间元素
        for i inrange(1, rows):
            for j inrange(1, cols):  # 当前状态由左边状态/上边状态的最小值决定
                dp[i][j]=min(dp[i][j -1], dp[i -1][j])+ grid[i][j]
        return dp[rows -1][cols -1]