【力扣Hot 100+经典题型】刷题记录（Python版）

Ne0inhk

16 Mar 2026 — 68 min read

文章目录

树
字符串
搜索查找
排列
组合
链表
位运算
数组计算
数据结构设计
- 380. O(1) 时间插入、删除和获取随机元素【中等】
- 146. LRU 缓存【中等】
矩阵
数学计算
图
- 207. 课程表【中等】
- 64. 最小路径和【中等】

Hot 100题单：🔥 LeetCode 热题 HOT 100
参考博客：LeetCode热题100Python解【题型分类】

树

104. 二叉树的最大深度【简单】

思路：递归、最终深度需要+1

classSolution(object):defmaxDepth(self, root):""" :type root: Optional[TreeNode] :rtype: int """if root isNone:return0else: left_height = self.maxDepth(root.left) right_height = self.maxDepth(root.right)returnmax(left_height, right_height)+1

94. 二叉树的中序遍历【简单】

思路：递归、列表可以用加法去append

classSolution(object):definorderTraversal(self, root):""" :type root: Optional[TreeNode] :rtype: List[int] """if root isNone:return[]else:# 中序return self.inorderTraversal(root.left)+[root.val]+ self.inorderTraversal(root.right)

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

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

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

思路：中序遍历、判断序列单增

classSolution(object):defisValidBST(self, root):""" :type root: Optional[TreeNode] :rtype: bool """defsolve(root):if root isNone:return[]else:return helper(root.left)+[root.val]+ helper(root.right) tree_values = solve(root) ans =Truefor i inrange(len(tree_values)-1):if tree_values[i]>= tree_values[i +1]: ans =Falsereturn ans

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

思路：DFS、递归

classSolution(object):defdiameterOfBinaryTree(self, root):""" :type root: Optional[TreeNode] :rtype: int """ self.ans =1# 最大node数（全局变量）defsolve(node):if node isNone:return0 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数returnmax(left_depth, right_depth)+1# node数 solve(root)return self.ans -1# 得到的node数减1得到路径长

617. 合并二叉树【简单】

思路：DFS、递归

classSolution:defmergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode])-> Optional[TreeNode]:# 特殊情况ifnot root1:return root2 ifnot 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、用队列存储每一层的节点

classSolution:deflevelOrder(self, root: Optional[TreeNode])-> List[List[int]]:ifnot root:return[] ans =[] queue =[root]print(f'inital queue: {queue}')while queue:print(f'current queue: {queue}') n =len(queue)print(f'n: {n}') cur_level =[]for _ inrange(n):# 当前层的node数 node = queue.pop(0)# 丢掉最前面的一项（当前层）print(f'node: {node}') cur_level.append(node.val)# 当前层的node值都放进一个sublistif node.left: queue.append(node.left)# 把下一层存进来if node.right: queue.append(node.right)# 把下一层存进来 ans.append(cur_level)print(f'ans: {ans}')return ans

也可以用Python库中的双向队列实现：

from collections import deque classSolution:deflevelOrder(self, root: Optional[TreeNode])-> List[List[int]]:ifnot root:return[] ans =[] queue = deque() queue.append(root)print(f'inital queue: {queue}')while queue:print(f'current queue: {queue}') n =len(queue)print(f'n: {n}') cur_level =[]for _ inrange(n):# 当前层的node数 node = queue.popleft()# 丢掉最前面的一项（当前层）print(f'node: {node}') cur_level.append(node.val)# 当前层的node值都放进一个sublistif node.left: queue.append(node.left)# 把下一层存进来if node.right: queue.append(node.right)# 把下一层存进来 ans.append(cur_level)print(f'ans: {ans}')return ans

但是直接跑上面代码会超时的，因为有很多print帮助理解，删掉print即可。

226. 翻转二叉树【简单】

思路：递归

classSolution:definvertTree(self, root: Optional[TreeNode])-> Optional[TreeNode]:ifnot root:returnNone left = self.invertTree(root.left) right = self.invertTree(root.right) root.left = right root.right = left return root

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

思路：DFS递归

classSolution:deflowestCommonAncestor(self, root:'TreeNode', p:'TreeNode', q:'TreeNode')->'TreeNode':ifnot root:returnNoneif root == p or root == q:return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q)ifnot left:return right ifnot right:return left return root

112. 路径总和【简单】

思路：递归

classSolution:defhasPathSum(self, root: Optional[TreeNode], targetSum:int)->bool:ifnot root:returnFalseifnot root.left andnot root.right:# 叶子结点return targetSum == root.val # 当叶子结点的值等于当前“还需要凑多少”时，说明存在这个路径# 挺抽象的递归代码：要么左分支、要么右分支，每次把targetSum更新成“还需要凑多少？”这个值return self.hasPathSum(root.left, targetSum - root.val)or self.hasPathSum(root.right, targetSum - root.val)

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

思路：前缀树模板

classTrie:def__init__(self): self.children =[None]*26# 指向子节点的指针数组：26个字母 self.isEnd =False# 该节点是否是字符串的结尾字母defsearchPrefix(self, prefix:str): node = self for c in prefix: idx =ord(c)-ord('a')ifnot node.children[idx]:# 如果该字符不在指针数组中，搜索不到returnNone node = node.children[idx]# 能搜索到该字符，移动指针到子节点return node definsert(self, word:str)->None: node = self for c in word: idx =ord(c)-ord('a')ifnot node.children[idx]:# 如果该字符不在指针数组中，创建新的子节点 node.children[idx]= Trie() node = node.children[idx]# 创建子节点之后，移动指针到子节点 node.isEnd =True# 移动到字符串末尾，给节点打一个标记defsearch(self, word:str)->bool: node = self.searchPrefix(word)return(node isnotNone)and(node.isEnd)# 注意需要isEnd=True，说明字符串被完整搜索到了defstartsWith(self, prefix:str)->bool: node = self.searchPrefix(prefix)return node isnotNone

100. 相同的树【简单】

思路：递归左右树相同

classSolution:defisSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode])->bool:if p isNoneor q isNone:# 如果有一棵树是None，则都必须是Nonereturn p isNoneand q isNone# 当前节点相同，并且递归左右树分别相同return p.val == q.val and self.isSameTree(p.left, q.left)and self.isSameTree(p.right, q.right)

101. 对称二叉树【简单】

思路：递归左右树相反

classSolution:defisSymmetric(self, root: Optional[TreeNode])->bool:defhelper(p, q):ifnot p ornot q:# 如果有一棵树是None，则都必须是Nonereturnnot p andnot 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. 二叉树的右视图【中等】

思路：广度优先搜索，取每层最右侧的节点

classSolution:defrightSideView(self, root: Optional[TreeNode])-> List[int]:ifnot root:return[]# 广度优先搜索模板 queue = deque() queue.append(root) ans =[]while queue: n =len(queue)# 当前层的node数 ans.append(queue[-1].val)# 将当前层最右侧的node存进答案for _ inrange(n): node = queue.popleft()# 取出当前层的每个nodeif node.left: queue.append(node.left)if node.right: queue.append(node.right)return ans

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

思路：层序遍历+层索引记录

classSolution:defzigzagLevelOrder(self, root: Optional[TreeNode])-> List[List[int]]:ifnot root:return[] queue =[root] ans =[] layer_idx =0while queue: n =len(queue) cur_level =[]for _ inrange(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 +=1return ans

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

思路：递归

classSolution:def__init__(self): self.ans =-inf # 定义全局最大路径答案defmaxPathSum(self, root: Optional[TreeNode])->int:ifnot root:return0defdfs(node):ifnot node:return0 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 = rightclassSolution:defsortedArrayToBST(self, nums: List[int])-> Optional[TreeNode]:ifnot nums:returnNone# 从中间位置将元素分成两拨，左右分别递归构造搜索数 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

classSolution(object):defisValid(self, s):""" :type s: str :rtype: bool """iflen(s)%2==1:returnFalseelse:# 预定义匹配对 pairs_dict ={")":"(","}":"{","]":"[",} stack =[]# 空栈for c in s:if c in pairs_dict:# 是右符号 待匹配ifnot stack or stack[-1]!= pairs_dict[c]:returnFalse stack.pop()else:# 是左符号 入栈 stack.append(c)# 最终stack必须被消耗为空才行ifnot stack:returnTrueelse:returnFalse

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

思路：栈存储下标而非元素值，这样就可以在后面用下标减法来计算长度。注意需要在开头插入-1，方便后面栈空的时候有东西可以减。

classSolution(object):deflongestValidParentheses(self, s):""" :type s: str :rtype: int """ stack =[] ans =0# 存储最大长度的答案 stack.append(-1)# 为了后面计算下标差值时，有足够的元素减for i inrange(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. 回文子串【中等】

思路：中心扩展（分奇数和偶数长度的回文）

classSolution(object):defcountSubstrings(self, s):""" :type s: str :rtype: int """ n =len(s)defsolve(left, right): cnt =0# 中心扩展法while0<= left < n and0<= right < n and s[left]== s[right]: cnt +=1 left -=1 right +=1return cnt ans =0for i inrange(n): ans += solve(i, i)# 奇数长度回文 ans += solve(i, i+1)# 偶数长度回文return ans

139. 单词拆分【中等】

思路：DP

classSolution:defwordBreak(self, s:str, wordDict: List[str])->bool: n =len(s) dp =[True]+[False]* n for i inrange(n):for j inrange(i+1, n+1):if dp[i]and s[i:j]in wordDict:# 前面的字符串满足，且后面的字符串满足 dp[j]=Truereturn dp[-1]

394. 字符串解码【中等】

思路：用栈去逐步提取字母和数字

classSolution:defdecodeString(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

classSolution:defminDistance(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个一组逐步计算

classSolution:defconvertToTitle(self, columnNumber:int)->str: ans =[]while columnNumber >0: columnNumber -=1# A是从1开始编码的 ch =chr(columnNumber %26+ord('A')) ans.append(ch) columnNumber //=26return"".join(ans[::-1])

415. 字符串相加【简单】

思路：从低位往高位相加进位

classSolution:defaddStrings(self, num1:str, num2:str)->str: ans ="" carry =0while num1 or num2: x =int(num1[-1])if num1 else0# 取最后一位 y =int(num2[-1])if num2 else0# 取最后一位sum= x + y + carry value =sum%10 ans =str(value)+ ans carry =sum//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来记录哪些位置有元素

classSolution:deffindDisappearedNumbers(self, nums: List[int])-> List[int]: n =len(nums) ans =[] flag =[0]*(n +1)# 因为元素范围是1～n，所以只在下标1～n的位置记录for x in nums: flag[x]=1for i inrange(1, n +1):# 只在下标1～n的位置记录if flag[i]==0: ans.append(i)return ans

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

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

classSolution(object):defsingleNumber(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. 二分查找【简单】

思路：二分查找

classSolution(object):defsearch(self, nums, target):""" :type nums: List[int] :type target: int :rtype: int """ left =0 right =len(nums)-1while left <= right: mid =(left + right)//2if nums[mid]== target:return mid elif nums[mid]> target: right = mid -1elif nums[mid]< target: left = mid +1return-1

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

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

classSolution:defmaxProfit(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

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

classSolution:defmaxProfit(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【中等】

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

classSolution:defmaxProfit(self, prices: List[int])->int: n =len(prices) ans =0# 如果仅一条数据（如[1]），则当天买入卖出，结果是0for i inrange(1, n): ans +=max(prices[i]- prices[i -1],0)return ans

思路：DP

classSolution:defmaxProfit(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以及对应的数量

classSolution:defmajorityElement(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]+=1else: count_dict.update({num:1}) ans =0 max_cnt =0for k, v in count_dict.items():if v >= threshold and v > max_cnt:# 不仅要数量达到阈值，还需要取数量最大的那个 max_cnt = v ans = k return ans

739. 每日温度【中等】

思路：单调栈

最暴力的写法是 O ( n 2 ) O(n^2) O(n2)的，会timeout：

classSolution:defdailyTemperatures(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 breakreturn ans

从右往左构造单调栈：

classSolution:defdailyTemperatures(self, temperatures: List[int])-> List[int]: n =len(temperatures) ans =[0]* n stack =[]# 用栈存indexfor 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

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

classSolution:defdailyTemperatures(self, temperatures: List[int])-> List[int]: n =len(temperatures) ans =[0]* n stack =[]# 用栈存indexfor 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存储

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

classSolution:deftwoSum(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：

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

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

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

classSolution:deftwoSum(self, numbers: List[int], target:int)-> List[int]: n =len(numbers) hash_table ={}for i inrange(n): diff = target - numbers[i]# 先判断再update hash表，避免重复使用当前元素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

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

classSolution:deftwoSum(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 +=1elif s > target:# 如果求和偏大，说明right应该向左走 right -=1else:return[left +1, right +1]

15. 三数之和【中等】

思路：先变成递增数组，然后指定第一个元素，在剩下两个元素值上用相向双指针

classSolution:defthreeSum(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 +=1elif s >0: right -=1elif s ==0: ans.append([a, nums[left], nums[right]])# 结果# 继续找结果：left指针向右（避开重复）、right指针向左（避开重复） left +=1while left < right and nums[left]== nums[left -1]: left +=1 right -=1while left < right and nums[right]== nums[right +1]: right -=1return ans

155. 最小栈【中等】

思路：用辅助栈的栈顶来同步存储当前数据栈的最小值

classMinStack:def__init__(self): self.stack =[] self.min_stack =[math.inf]defpush(self, val:int)->None: self.stack.append(val) self.min_stack.append(min(self.min_stack[-1], val))defpop(self)->None: self.stack.pop() self.min_stack.pop()deftop(self)->int:return self.stack[-1]defgetMin(self)->int:return self.min_stack[-1]

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

思路：

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

classSolution:deftopKFrequent(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]]=1else: hash_table[nums[i]]+=1# 降序排列: [(k1, v1), (k2, v2), ...] rank_value =sorted(hash_table.items(), key=lambda x:x[1], reverse=True) i =0for key, value in rank_value: i +=1 ans.append(key)if i == k:breakreturn ans

【TODO】

287. 寻找重复数【中等】

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

classSolution:deffindDuplicate(self, nums: List[int])->int:ifnot 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. 接雨水【困难】

思路：相向双指针

classSolution:deftrap(self, height: List[int])->int: n =len(height) max_left, max_right =0,0# 记录从左往右最高点、左右往左最高点 left, right =0, n -1# 相向双指针 ans =0while 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 +=1if max_left > max_right: ans += max_right - height[right]# 统计低洼的情况 right -=1return ans

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

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

classSolution:defmaxArea(self, height: List[int])->int: n =len(height)if n ==2:returnmin(height[0], height[1])*1 ans =0 left, right =0, n -1while left < right: width = right - left cur_s = width *min(height[left], height[right]) ans =max(ans, cur_s)# 面积取决于最矮的那边，所以哪边矮哪边就往前走一步，保留高的那边if height[left]<= height[right]: left +=1elif height[left]> height[right]: right -=1return ans

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

思路：二分法搜索边界

classSolution:defcountTarget(self, scores: List[int], target:int)->int: n =len(scores)defhelper(target): left, right =0, n -1while left <= right: mid =(left + right)//2if scores[mid]< target: left = mid +1elif scores[mid]>= target: right = mid -1return left l = helper(target) r = helper(target +1)return r - l

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

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

classSolution:defsearchRange(self, nums: List[int], target:int)-> List[int]:ifnot nums:return[-1,-1] n =len(nums)defhelper(target): left, right =0, n -1while left <= right: mid =(left + right)//2if nums[mid]< target: left = mid +1else: right = mid -1return left l = helper(target) r = helper(target +1)if r > l:return[l, r -1]return[-1,-1]

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

思路：用hash/数组计数

classSolution:deffindSpecialInteger(self, arr: List[int])->int: n =len(arr)if n ==1:return arr[0] thre =int(n *0.25)print(thre) hash_table ={}for a in arr:if a notin hash_table: hash_table[a]=1else: hash_table[a]+=1# 得先统计上当前的元素if hash_table[a]> thre:return a

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

思路：基于快速排序思想

classSolution:deffindKthLargest(self, nums: List[int], k:int)->int:defquick_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中，递归划分bigreturn quick_select(big, k)iflen(big)+len(equal)< k:# 第k大的元素在small中，递归划分smallreturn quick_select(small, k -len(big)-len(equal))return pivot # 第k大的元素在equal中，返回pivotreturn quick_select(nums, k)

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

思路：滑动窗口，枚举右端点，收缩左端点，记录全局左端点和滑窗元素和

classSolution:defminSubArrayLen(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 +=1if s >= target: ans =min(ans, right - left +1)return ans if ans <= n else0

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

classSolution:defminSubArrayLen(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 +=1return ans if ans <= n else0

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

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

classSolution:defminWindow(self, s:str, t:str)->str: cnt_win = Counter()# s的滑窗字符计数器 cnt_t = Counter(t)# t的字符计数器 ans_left, ans_right =-inf, inf left =0for right, x inenumerate(s):# 枚举右端点 cnt_win[x]+=1while cnt_win >= cnt_t:# s滑窗能覆盖tif right - left < ans_right - ans_left:# 找到了更短字符串，更新答案 ans_left, ans_right = left, right cnt_win[s[left]]-=1# 丢掉左端点 left +=1return s[ans_left:ans_right+1]if ans_left >=0else""

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

思路：滑动窗口

classSolution:deflengthOfLongestSubstring(self, s:str)->int: n =len(s) ans =0 visited =set()# 用set检测重复元素 left =0for 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

排列

冒泡排序【排序模板】

classSolution(object):defsortArray(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

快速排序【排序模板】

classSolution:defsortArray(self, nums: List[int])-> List[int]:defquicksort(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 defpartition(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排列

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

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

classSolution(object):defmoveZeroes(self, nums):""" :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ right =len(nums)-1 left =0while left < right:if nums[left]==0: nums[right], nums[left]= nums[left], nums[right] right -=1 left +=1return nums

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

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

75. 颜色分类【中等】

思路：三指针，p0左侧保持全0，p2右侧保持全2，i从左往右遍历数组
细节：如果i遇到0，swap后i继续走，如果i遇到2，swap后i先别动（因为可能把后面的0交换到前面了，下次应该直接在该位置i和p0交换）

classSolution:defsortColors(self, nums: List[int])->None:""" Do not return anything, modify nums in-place instead. """ n =len(nums) p0, p2 =0, n -1 i =0while i <= p2:if nums[i]==2: nums[i], nums[p2]= nums[p2], nums[i] p2 -=1elif nums[i]==0: nums[i], nums[p0]= nums[p0], nums[i] p0 +=1 i +=1elif nums[i]==1: i +=1

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

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

classSolution:defreconstructQueue(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]))# print(f'people_sort: {people_sort}')for person in people_sort: ans.insert(person[1], person)# print(ans)return ans

看下具体的输出帮助理解：

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

思路：相向双指针

classSolution:defsortedSquares(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 -=1elif nums[left]**2> nums[right]**2: ans.append(nums[left]**2) left +=1return ans[::-1]

31. 下一个排列【中等】

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

classSolution:defnextPermutation(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 -2while i >=0and nums[i]>= nums[i +1]: i -=1# 如果找到了nums[i]，继续找nums[i]右边大于它且最小的元素nums[j]if i >=0: j = n -1while nums[j]<= nums[i]: j -=1 nums[i], nums[j]= nums[j], nums[i]# 交换两个元素# 将右侧的元素翻转：从递减到递增，保证右侧字典序最小# 如果找不到（即i=-1），说明当前是最大排列，直接翻转即可得到最小排列 left, right = i +1, n -1while left < right: nums[left], nums[right]= nums[right], nums[left] left +=1 right -=1

组合

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

思路：用字典的相同key映射多个字母异位词（用value列表存）

classSolution(object):defgroupAnagrams(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是往列表中添加一整个元素）

classSolution(object):defsubsets(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. 全排列【中等】

思路：回溯

classSolution:defpermute(self, nums: List[int])-> List[List[int]]: n =len(nums) ans =[]# 回溯法defdfs(start):# 固定一个元素if start == n:# 所有元素都确定，记录当前组合 ans.append(nums[:])# 注意！这里需要用list(nums)活着nums[:]，相当于对nums进行了一次浅拷贝returnfor 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题的回溯，但是需要用哈希去重

classSolution:defpermuteUnique(self, nums: List[int])-> List[List[int]]: n =len(nums) ans =[]# 回溯法defdfs(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))实现去重

classSolution:defgoodsOrder(self, goods:str)-> List[str]: n =len(goods) lst =list(goods)# 必须把字符串转list，才支持在回溯时交换元素 ans =[]# 回溯法defdfs(start):if start == n: ans.append(''.join(lst))returnfor 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. 反转链表【简单】

思路：用双指针，挨个位置反转箭头的方向

classSolution(object):defreverseList(self, head):""" :type head: Optional[ListNode] :rtype: Optional[ListNode] """ prev =None curr = head while curr:next= curr.next# 先把本来的curr.next拿到 curr.next= prev # curr的后面接prev，即链表方向反转# prev和curr一起往后走 prev = curr curr =nextreturn prev

92. 反转链表 II【中等】

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

classSolution:defreverseBetween(self, head: Optional[ListNode], left:int, right:int)-> Optional[ListNode]:ifnot head:returnNone# 用p0节点定位left位置左边的节点# 需要加入哨兵节点，为什么？因为当left=1时，left位置左边不存在节点，哨兵节点用于处理特殊情况 dummy = ListNode(next=head) p0 = dummy for _ inrange(left -1): p0 = p0.next# 此时，p0走到了left位置的左边 cur, prev = p0.next,Nonefor _ inrange(right - left +1):# 反转中间的元素next= cur.next cur.next= prev prev = cur cur =next# 处理最后两个指向 p0.next.next= cur # 把图中的1指向5 p0.next= prev # 把图中的1指向4return dummy.next

234. 回文链表【简单】

思路：遍历链表，把值存储在列表中，判断列表是否是回文的

classSolution(object):defisPalindrome(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

classSolution:defgetIntersectionNode(self, headA: ListNode, headB: ListNode)-> Optional[ListNode]:ifnot headA ornot headB:returnNone 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.nextreturnNone

141. 环形链表【简单】

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

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

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

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

142. 环形链表 II【中等】

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

classSolution:defdetectCycle(self, head: Optional[ListNode])-> Optional[ListNode]:ifnot head:returnNone 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跳出循环returnNone

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

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

148. 排序链表【中等】

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

classSolution:defsortList(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 =0while cur: cur.val = head_list[i] i +=1 cur = cur.nextreturn head

归并排序

classSolution:defsortList(self, head: Optional[ListNode])-> Optional[ListNode]:ifnot head ornot head.next:return head # 步骤1. 递归每次分割成2组 slow, fast = head, head.nextwhile 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.nextelse: cur.next= right right = right.next cur = cur.next# 处理不同长度if left: cur.next= left else: cur.next= right return ans.next

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

classSolution:defdeleteNode(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

lass Solution:defremoveNthFromEnd(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. 删除排序链表中的重复元素【简单】

思路：直接判断下一个节点是否值相同

classSolution:defdeleteDuplicates(self, head: Optional[ListNode])-> Optional[ListNode]:ifnot head:returnNone 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的值，然后用循环去跳过所有相同值的节点

classSolution:defdeleteDuplicates(self, head: Optional[ListNode])-> Optional[ListNode]: dummy = ListNode(next=head) cur = dummy while cur.nextand cur.next.next:# 保证下个节点和下下个节点存在 val = cur.next.val # 下个节点的值if cur.next.next.val == val:# 发现相同值的节点了！要通过循环从cur.next开始跳过while cur.nextand cur.next.val == val: cur.next= cur.next.nextelse: cur = cur.nextreturn dummy.next

为什么需要哨兵节点，因为头节点可能被删除。

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

思路：用哨兵节点，迭代判断

classSolution:defremoveElements(self, head: Optional[ListNode], val:int)-> Optional[ListNode]:ifnot head:returnNone dummy = ListNode(next=head)# 哨兵节点，处理头节点被删除的情况 cur = dummy while cur and cur.next:if cur.next.val == val:# 注意提前一个节点开始判断，方便跨过 cur.next= cur.next.nextelse: cur = cur.nextreturn dummy.next

2. 两数相加【中等】

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

classSolution:defaddTwoNumbers(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.nextif l1: l1 = l1.nextif l2: l2 = l2.nextif carry: cur.next= ListNode(carry)return ans.next

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

思路：双指针，取较小的，并移动其指针

classSolution:defmergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode])-> Optional[ListNode]:ifnot list1 andnot list2:returnNone ans = ListNode()# 答案链表，初始化一个dummy节点，答案节点都存储在后面 cur = ans while list1 and list2:# 先处理共同长度的部分# 思路：先取较小的，然后移动其指针if list1.val < list2.val: cur.next= list1 list1 = list1.nextelse: 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 个升序链表【困难】

思路：两两合并，分治处理

classSolution:defmergeKLists(self, lists: List[Optional[ListNode]])-> Optional[ListNode]:# 先写两个有序链表的合并defmergeTwoLists(list1, list2): dummy = ListNode()# 哨兵节点简化代码 cur = dummy while list1 and list2:# 先处理链表等长的部分if list1.val < list2.val: cur.next= list1 list1 = list1.nextelse: 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:returnNoneif n ==1:return lists[0] left = self.mergeKLists(lists[:n //2])# 递归合并前半部分 right = self.mergeKLists(lists[n //2:])# 递归合并后半部分return mergeTwoLists(left, right)# 合并前后两个部分

位运算

461. 汉明距离【简单】

比特位的模板解法：

classSolution:defhammingDistance(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的每一位是否为1if one_bit_x != one_bit_y: dist +=1return dist

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

classSolution(object):defhammingDistance(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. 比特位计数【简单】

比特位的模板解法：

classSolution:defcountBits(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

思路：转二进制然后计数

classSolution(object):defcountBits(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的个数【简单】

思路：通过“与”进行逐位判断

classSolution:defhammingWeight(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的个数

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

数组计算

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

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

classSolution:defproductExceptSelf(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]print(f'front_mul: {front_mul}')# 计算后缀元素乘积 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]print(f'behind_mul: {behind_mul}')# 把前缀乘积和后缀成绩再乘起来得到答案for i inrange(n): ans[i]= front_mul[i]* behind_mul[i]return ans

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

思路：考虑到正负号交替，需要同时存当前最大乘积和最小乘积（因为最小乘积和后面的负数相乘后会反转为最大乘积）

classSolution:defmaxProduct(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模板

classSolution:defmaxSubArray(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

classSolution:deflengthOfLIS(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去判断存在性

classSolution:deflongestConsecutive(self, nums: List[int])->int: n =len(nums) hash_set =set(nums)# 去重且查找元素的效率高 ans =0for 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的写法：

classSolution:deffindAnagrams(self, s:str, p:str)-> List[int]: window_size =len(p) n =len(s) ans =[] p_cnt =[0]*26for c in p: p_cnt[ord(c)-ord('a')]+=1for 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]*26for 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

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

classSolution:deffindAnagrams(self, s:str, p:str)-> List[int]: window_size =len(p) n =len(s) ans =[] window_cnt =[0]*26# 维持一个随着窗口更新的字符统计分布（每次只改变2个） p_cnt =[0]*26for c in p: p_cnt[ord(c)-ord('a')]+=1for 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. 数组形式的整数加法【简单】

思路：逐位计算模板

classSolution:defaddToArrayForm(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 //=10if carry: ans.append(carry)return ans[::-1]

119. 杨辉三角 II【简单】

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

classSolution:defgetRow(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

classSolution:defrob(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题没有本质区别，不过首尾两间不能同时偷，所以需要分情况讨论首尾偷哪个

classSolution:defrob(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

classSolution:defrob(self, root: Optional[TreeNode])->int:defdfs(node):# 返回两个值：偷这个节点的最大收益、不偷这个节点的最大收益ifnot 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. 滑动窗口最大值【困难】

思路：滑窗+单调队列

classSolution:defmaxSlidingWindow(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. 合并区间【中等】

思路：先排序左端点，然后从左往右依次判断包含关系

classSolution:defmerge(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背包

classSolution:deffindTargetSumWays(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@cache# 用@cache实现“记忆化”搜索，缓存中间结果，避免重复计算（用空间换时间）defdfs(i, target):# dfs(i, target)表示nums前i个数中，选中数之和为target的方案数if i <0:# 没有数可选return1if target ==0else0# target==0表示刚好1种方案，返回1，否则返回0if 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. 零钱兑换【中等】

思路：完全背包

classSolution:defcoinChange(self, coins: List[int], amount:int)->int: n =len(coins)@cachedefdfs(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 ) O(1) O(1)的getRandom，但是insert和remove都需要判断元素存在性，所以复杂度是 O ( n ) O(n) O(n)的：

classRandomizedSet:def__init__(self): self.nums =[]definsert(self, val:int)->bool:if val notin self.nums: self.nums.append(val)returnTruereturnFalsedefremove(self, val:int)->bool:if val in self.nums: idx = self.nums.index(val)del self.nums[idx]returnTruereturnFalsedefgetRandom(self)->int:ifnot self.nums:return[]return choice(self.nums)

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

classRandomizedSet:def__init__(self): self.nums =[] self.hash={}# {val: index}definsert(self, val:int)->bool:if val notin self.hash: self.nums.append(val) self.hash[val]=len(self.nums)-1# {val: index}returnTruereturnFalsedefremove(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()# 丢弃末尾元素returnTruereturnFalsedefgetRandom(self)->int:ifnot self.nums:return[]return choice(self.nums)

146. LRU 缓存【中等】

思路：字典+双向链表

用Python库实现：

classLRUCache:def__init__(self, capacity:int): self.capacity = capacity self.cache = OrderedDict()# dict + 双向链表defget(self, key:int)->int:if key notin self.cache:# 找不到这个keyreturn-1 self.cache.move_to_end(key, last=False)# 找到这个key，移动到链表表头return self.cache[key]defput(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】：

classNode:# 提高访问属性的速度，并节省内存 __slots__ ='prev','next','key','value'def__init__(self, key=0, value=0): self.key = key self.value = value classLRUCache: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 对应的节点，同时把该节点移到链表头部defget_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 defget(self, key:int)->int: node = self.get_node(key)# get_node 会把对应节点移到链表头部return node.value if node else-1defput(self, key:int, value:int)->None: node = self.get_node(key)# get_node 会把对应节点移到链表头部if node:# 有这本书 node.value = value # 更新 valuereturn 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)# 去掉最后一本书# 删除一个节点（抽出一本书）defremove(self, x: Node)->None: x.prev.next= x.next x.next.prev = x.prev # 在链表头添加一个节点（把一本书放到最上面）defpush_front(self, x: Node)->None: x.prev = self.dummy x.next= self.dummy.next x.prev.next= x x.next.prev = x

矩阵

200. 岛屿数量【中等】

思路：DFS

classSolution:defnumIslands(self, grid: List[List[str]])->int:defdfs(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 =0for r inrange(row_num):for c inrange(col_num):if grid[r][c]=='1':# 遍历到了岛屿 dfs(grid, r, c)# 递归：深度优先搜索 ans +=1# 答案+1return ans

221. 最大正方形【中等】

思路：DP

classSolution:defmaximalSquare(self, matrix: List[List[str]])->int: rows, cols =len(matrix),len(matrix[0])if rows ==0or cols ==0:# 如果正方形不存在，返回0return0 dp =[[0]* cols for _ inrange(rows)]# dp[i][j]表示以(i, j)为右下角的正方形的边长 max_side =0for i inrange(rows):for j inrange(cols):if matrix[i][j]=='1':# 只有当遍历到'1'这个位置，才能去探索if i ==0and j ==0:# 右下角在边界上，边长只能是1 dp[i][j]=1else:# 当前右下角最大边长取决于左、上、左上角最大边长的最小值 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的位置，第二次修改原矩阵

classSolution:defsetZeroes(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时则改成1for r inrange(rows):for c inrange(cols):if matrix[r][c]==0:# 如果matrix某个元素是0，则把行列flag改成1 row_flag[r]=1 col_flag[c]=1for 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度=水平翻转+主对角线翻转（转置）

classSolution:defrotate(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]

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

classSolution:defrotate(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】

classSolution:defrotate(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. 转置矩阵【简单】

思路：行列元素交换，注意不一定是方阵

classSolution:deftranspose(self, matrix: List[List[int]])-> List[List[int]]: rows =len(matrix) cols =len(matrix[0]) ans =[[0]* rows for _ inrange(cols)]# cols * rowsfor i inrange(rows):for j inrange(cols): ans[j][i]= matrix[i][j]return ans

数学计算

69. x 的平方根【简单】

思路：二分法

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

思路：牛顿迭代
公式： x n + 1 = x n − f ( x n ) f ′ ( x n ) x_{n+1}=x_n - \frac{f(x_n)}{f'(x_n)} xn+1=xn−f′(xn)f(xn)
对于 x 2 = C x^2=C x2=C，有 f ( x ) = x 2 − C f(x)=x^2-C f(x)=x2−C，则 f ′ ( x ) = 2 x f'(x)=2x f′(x)=2x，所以 x n + 1 = x n − x n 2 − C 2 x n = 1 2 ( x n + C x n ) x_{n+1}=x_n-\frac{x_n^2-C}{2x_n}=\frac{1}{2}(x_n+\frac{C}{x_n}) xn+1=xn−2xnxn2−C=21(xn+xnC)

classSolution:defmySqrt(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 P(1)=p, P(0) =1-p P(1)=p,P(0)=1−p。
首先考虑一个更简单的问题，能否等概率生成0和1？可以，随机采样两次。
P ( 0 , 1 ) = ( 1 − p ) p , p ( 1 , 0 ) = p ( 1 − p ) P(0,1)=(1-p)p, p(1,0)=p(1-p) P(0,1)=(1−p)p,p(1,0)=p(1−p)，这两种情况概率一致，因此把 P ( 0 , 1 ) P(0,1) P(0,1)看作生成0， P ( 1 , 0 ) P(1,0) P(1,0)看作生成1即可。伪代码如下：

import random defrandom_coin(p):# 生成概率为p的0/1return1if random.random()< p else0defRand1(self):# 周期性地产生2个数，直到生成01或者10才满足 i1 = random_coin()# 生成0/1 i2 = random_coin()# 生成0/1if i1 ==0and i2 ==1:return0elif i1 ==1and i2 ==0:return1else:return Rand1()# 重新生成

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

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

343. 整数拆分【中等】

思路：DP

classSolution:defintegerBreak(self, n:int)->int:if n ==1:return1 dp =[0]*(n +1)# dp[i]表示整数i时的乘积最大值 dp[1]=1for 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

classSolution:defisUgly(self, n:int)->bool:if n <=0:returnFalsewhile n %2==0: n //=2while n %3==0: n //=3while n %5==0: n //=5returnTrueif n ==1elseFalse

264. 丑数 II【中等】

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

classSolution:defnthUglyNumber(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 +=1if a[i]== num3: p3 +=1if a[i]== num5: p5 +=1# 不能用elif的原因：6=3*2同时6=2*3，所以p2、p3都要加1才行return a[n]

258. 各位相加【简单】

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

classSolution:defaddDigits(self, num:int)->int:if num ==0:return0while num >=10:# 只要不是个位数，就要继续sum=0while num >0:sum+= num %10 num //=10 num =sumreturn num

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

classSolution:defaddDigits(self, num:int)->int:if num ==0:return0if num %9==0:return9return num %9

也可以统一写法如下：

classSolution:defaddDigits(self, num:int)->int:if num ==0:return0return(num -1)%9+1

202. 快乐数【简单】

思路：哈希判断重复元素

classSolution:defisHappy(self, n:int)->bool:if n ==1:returnTruedefcompute_next(n):sum=0while n >0:sum+=(n %10)**2 n //=10returnsum# 核心思想：如果结果回不到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:returnTruereturnFalse

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

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

图

207. 课程表【中等】

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

classSolution:defcanFinish(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表示找到了环defdfs(x): states[x]=1for node in graph[x]:if states[node]==1or(states[node]==0and dfs(node)==True):returnTrue states[x]=2returnFalsefor i, s inenumerate(states):if s ==0and dfs(i)==True:# 存在环returnFalsereturnTrue

64. 最小路径和【中等】

思路：DP

classSolution:defminPathSum(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]