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

- 思路:递归、最终深度需要 +1
():
():
root :
:
left_height = .maxDepth(root.left)
right_height = .maxDepth(root.right)
(left_height, right_height) +
本文整理了 LeetCode 热题 HOT 100 中的经典算法题 Python 解法,涵盖树、字符串、搜索查找、排列、链表、位运算、数组计算、数据结构设计、矩阵及数学计算等多个模块。内容包括二叉树遍历、动态规划、双指针、滑动窗口、回溯法等核心算法思想,并提供了完整的代码实现与思路解析,适合 Python 开发者进行算法训练与面试准备。

():
():
root :
:
left_height = .maxDepth(root.left)
right_height = .maxDepth(root.right)
(left_height, right_height) +

class Solution(object):
def inorderTraversal(self, root):
""" :type root: Optional[TreeNode] :rtype: List[int] """
if root is None:
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]

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

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 得到路径长

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

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

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

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

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)


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

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)

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) # 把一棵树看作左右两棵树

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

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

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

# 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)

思路:遇到左符号直接入栈,右符号则开始匹配,匹配标准是 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

思路:栈存储下标而非元素值,这样就可以在后面用下标减法来计算长度。注意需要在开头插入 -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

思路:中心扩展(分奇数和偶数长度的回文)
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

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]

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

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 个字符的最小操作数

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])

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

思路:不能用 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

思路:集合 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

思路:二分查找
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

暴力写法,复杂度 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

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
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] # 最后持有股票一定不如清仓

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

最暴力的写法是 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

最暴力的做法就是双重循环:
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})

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]

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


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]

下面是最暴力的做法,用到了排序,复杂度 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

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])

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

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

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

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]

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

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)

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
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""

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

思路:双指针(都从左侧开始,才能保证元素的相对顺序),实现 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


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

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
看下具体的输出帮助理解:


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]

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

思路:用字典的相同 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()

思路:维护一个 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

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

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

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 去重

思路:用双指针,挨个位置反转箭头的方向
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


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

思路:遍历链表,把值存储在列表中,判断列表是否是回文的
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

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

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

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

最暴力的做法,转列表排序后放回链表:
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
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

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
什么时候需要哨兵节点?头节点可能被删除的情况需要。

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
为什么不需要哨兵节点?因为头节点不会被删除。

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
为什么需要哨兵节点,因为头节点可能被删除。

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

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

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 节点

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) # 合并前后两个部分

比特位的模板解法:
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

比特位的模板解法:
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

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

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


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

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

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)

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)

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

下面是最简单,但是会 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

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]

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]

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]

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)

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))

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

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

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)

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

最简单的写法,纯用 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)

用 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

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

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

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

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]

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

class Solution:
def mySqrt(self, x:int)->int:
left, right =0, x
ans =-1
while left <= right:
mid =(left + right)//2
if mid **2<= x:
ans = mid
left = mid +1
else:
right = mid -1
return ans
class Solution:
def mySqrt(self, x:int)->int:
if x ==0:
return0
x0 = x
whileTrue:
x1 =0.5*(x0 + x / x0)
ifabs(x0 - x1)<1e-6:
break
x0 = x1
returnint(x0)
题目:一个随机变量 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)

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]

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

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]

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

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 指针走两步

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

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]

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具,curl 转代码在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online