面试手撕题
不同路径(美团)--动态规划¶
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
不同路径2--动态规划¶
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角(即 grid[0][0])。机器人尝试移动到 右下角(即 grid[m - 1][n - 1])。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。
数组中的第K个最大元素--快速选择¶
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
会议室2(腾讯PCG)¶
给你一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ,返回 所需会议室的最小数量 。
核心思路: 本质是求区间集合在任意时刻的最大重叠数——即同时处于"开始但尚未结束"状态的区间数量的峰值。
算法直觉: 将问题转化为"会议室资源调度":
贪心思想:当新会议到来时,优先复用最早结束的会议室。若其结束时间 ≤ 新会议开始时间,则腾出该房间供复用;否则必须新开一间。
最小堆维护"最早结束时间":堆顶始终是当前所有占用会议室中最早空闲的那个,O(log n) 完成插入与弹出。
import heapq
class Solution:
def minMeetingRooms(self, intervals):
"""
目标:给定一组会议 [start, end),求最少需要多少间会议室(同一时刻 end==start 不冲突)。
方法:最小堆(小根堆)按“结束时间”管理当前在开的会议;堆大小即并发会议数。
"""
if not intervals:
return 0
# 1) 先按开始时间排序,保证按时间线从早到晚处理
intervals.sort(key=lambda x: x[0])
heap = []
max_rooms = 0
# 2) 若前面会议的结束时间小于等于下一场会议开始的时间,则可共用一间会议室
for s, e in intervals:
while heap and heap[0] <= s:
heapq.heappop(heap)
heapq.heappush(heap, e) # 放在最前面,该会议结束时间一定是最早的
max_rooms = max(max_rooms, len(heap))
return max_rooms
test = [[0, 30], [5, 10], [15, 20]]
print(Solution().minMeetingRooms(test))
2
时间O(n log n):
- 排序 O(n log n);
- 每个区间各执行一次 push + 至多一次 pop,单次操作 O(log n),共 O(n log n)
空间:O(n); 最坏情况(所有会议完全重叠)堆中存放 n 个结束时间
解码方法(腾讯PCG)¶
一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
"1" -> 'A'
"2" -> 'B'
...
"25" -> 'Y'
"26" -> 'Z'
然而,在 解码 已编码的消息时,你意识到有许多不同的方式来解码,因为有些编码被包含在其它编码当中("2" 和 "5" 与 "25")。
例如,"11106" 可以映射为:
"AAJF" ,将消息分组为 (1, 1, 10, 6)
"KJF" ,将消息分组为 (11, 10, 6)
消息不能分组为 (1, 11, 06) ,因为 "06" 不是一个合法编码(只有 "6" 是合法的)。 注意,可能存在无法解码的字符串。
给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串,返回 0。
核心思想 加入的元素,分为两种情况,可以单独编码吗?可以组合编码吗?互相不冲突
- (1)当加入的一个数不是0,他一定可以单独编码,那么至少 dp i= dpi_1。
- (2)当加入的一个数可以与前面的组合编码,那么至少 dpi = dpi_2
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
if not s or s[0] == '0':
return 0
dpi_2, dpi_1 = 1, 1
for i in range(1, n):
dpi = 0
if s[i] != '0':
dpi = dpi_1
if s[i-1] == '1' or (s[i-1] == '2' and s[i] < '7'):
dpi += dpi_2
if dpi == 0:
return 0
dpi_2, dpi_1 = dpi_1, dpi
return dpi_1
s = "238"
print(Solution().numDecodings(s))
2
二叉树节点染色的最大权值问题(字节国际电商)¶
给定一个整数数组 nums,用来按层序(level order)表示一棵二叉树。
数组规则如下:
nums[i] 表示编号为 i 的节点的权重。
若 nums[i] 为 null(或某特殊标记),表示该位置不存在节点。
对于任意下标 i:
左子节点下标为 2*i + 1
右子节点下标为 2*i + 2
若子节点下标越界或该位置为 null,则该子节点不存在。
现在你可以对若干节点进行“染色”。
染色约束:
若某节点被染色,则它的父节点不能被染色;
若某节点被染色,则它的左右子节点不能被染色;
兄弟节点之间没有限制。
目标:
在满足上述约束的前提下,选择若干节点,使得被染色节点的权重之和最大。
返回这个最大值。
核心思路
假设:
left = (L0, L1) right = (R0, R1)
那么:
L0 = 不选左孩子时的最大值; L1 = 选左孩子时的最大值; R0 = 不选右孩子时的最大值; R1 = 选右孩子时的最大值。
状态转移
情况1:选当前节点
如果你选当前节点:
那么左右孩子都不能选。
所以:
choose = 当前权重 + L0 + R0
因为:
只能拿“不选孩子”的值。
情况2:不选当前节点
如果你不选当前节点:
左右孩子可以自由选择(选或不选)
所以:
not_choose = max(L0, L1) + max(R0, R1)
from typing import List, Optional
class Solution:
def maxColorValue(self, nums: List[Optional[int]]) -> int:
n = len(nums)
def dfs(i: int):
"""
返回:
(not_choose, choose)
not_choose: 不选当前节点的最大值
choose: 选当前节点的最大值
"""
# 越界 或 节点为空
if i >= n or nums[i] is None:
return (0, 0)
# 递归计算左右子节点
left = dfs(2 * i + 1)
right = dfs(2 * i + 2)
# 选当前节点
# 子节点必须不选
choose = nums[i] + left[0] + right[0]
# 不选当前节点
# 子节点可以选或不选,取最大
not_choose = max(left) + max(right)
return (not_choose, choose)
# 根节点开始
result = dfs(0)
# 最终可以选根,也可以不选根
return max(result)
nums = [3,2,3,None,3,None,1]
print(Solution().maxColorValue(nums))
7
代码infoNCE的函数计算公式(字节国际电商,主播自己项目所用)¶
import torch
import torch.nn.functional as F
def infoNCE(user_emb, item_emb, tempreture = 0.5):
B, D = user_emb.shape
# 归一化
user_emb = F.normalize(user_emb, dim = -1)
item_emb = F.normalize(item_emb, dim = -1)
# 相似矩阵
sim = torch.matmul(user_emb, item_emb.transpose(0, 1)) / tempreture
# 标签
label = torch.arange(B)
# 多类交叉熵计算
loss = F.cross_entropy(sim, label) # Compute the cross entropy loss between input logits and target.
return loss
user_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]])
item_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]])
print(infoNCE(user_emb, item_emb, 1))
tensor(1.1176)
import torch
import torch.nn.functional as F
def cross_entropy(logits, labels):
B, _ = logits.shape
max_logits = torch.max(logits, dim=-1, keepdim=True)[0] #返回(最大值数值,最大值的位置索引),取[0]表示取出最大值
stable_logits = logits - max_logits # B, D
log_sum_exp = torch.log(torch.sum(torch.exp(stable_logits), dim=-1)) #(B,)
pos_logits = stable_logits[torch.arange(B), labels] # (B,)
loss = - pos_logits + log_sum_exp
return loss.mean()
def infoNCE(user_emb, item_emb, tempreture=0.7):
B, D = user_emb.shape
user_emb = F.normalize(user_emb, dim=-1)
item_emb = F.normalize(item_emb, dim=-1)
sim = torch.matmul(user_emb, item_emb.transpose(0,1)) / tempreture
label = torch.arange(B)
loss = cross_entropy(sim, label)
return loss
user_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]])
item_emb = torch.tensor([[1.1, 24.0, 5.9], [3.3, 9.2, 32.1], [12.1, 11.1, 15.3], [0.8, 0.1, 0.4]])
print(infoNCE(user_emb, item_emb, 1))
tensor(1.1176)
121. 买卖股票的最佳时机(字节)¶
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0
核心思想
在遍历到第 i 天时, 假设第 i 天卖出,最大利润是多少?
利润 = 当前价格 − 之前某一天的最低价格
因此算法维护两个量:
cur_min_price:到当前为止出现过的最低价格(即最优买入点)。
max_profit:到当前为止能获得的最大利润。
一次遍历 + 动态维护历史最低价。
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
cur_min_price = prices[0]
max_profit = 0
for i in range(1, n):
cur_min_price = min(cur_min_price, prices[i])
max_profit = max(max_profit, prices[i] - cur_min_price)
return max_profit
prices = [7, 1, 5, 3, 6, 4]
print(Solution().maxProfit(prices))
5
时间复杂度 O(n)
空间复杂度 O(1)
105. 岛屿的最大面积(腾讯WXG)¶
给定一个由 0 和 1 组成的非空二维数组 grid ,用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。
这是一个典型的二维网格 DFS / BFS 遍历问题。本质是: 遍历每个位置,遇到 1 时,向四个方向扩散,把整块连通区域面积统计出来,并取最大值。
核心思想:
外层双重循环遍历整个 grid
遇到 1 时启动 DFS
DFS 负责:
- 累加面积
- 把访问过的 1 置为 0(避免重复访问)
- 向四个方向继续扩散
from typing import List
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
rows = len(grid)
cols = len(grid[0])
max_area = 0
# 定义 DFS
def dfs(r: int, c: int) -> int:
# 越界 或 当前是水,返回 0
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
return 0
# 访问过的陆地置为 0,避免重复访问
grid[r][c] = 0
# 当前格子面积为 1
area = 1
# 向四个方向扩散
area += dfs(r + 1, c)
area += dfs(r - 1, c)
area += dfs(r, c + 1)
area += dfs(r, c - 1)
return area
# 遍历每一个位置
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
# 每次发现新岛屿,计算面积
current_area = dfs(i, j)
max_area = max(max_area, current_area)
return max_area
grid = [
[1, 1, 0, 0, 1, 1],
[1, 1, 1, 0, 1, 1],
[0, 1, 1, 0, 1, 0]
]
print(Solution().maxAreaOfIsland(grid))
7
时间复杂度:
O(m × n)
每个格子最多被访问一次。
空间复杂度:
O(m × n)(最坏情况下递归栈深度为整个网格大小,例如全是 1)
如果是正常岛屿分布,递归深度通常为单个岛屿面积。
200. 岛屿数量¶
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
rows = len(grid)
cols = len(grid[0])
count = 0
def dfs(r: int, c: int) -> None:
# 越界 或 当前是水,直接返回
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == "0":
return
# 淹掉当前陆地
grid[r][c] = "0"
# 扩散四个方向
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for i in range(rows):
for j in range(cols):
if grid[i][j] == "1":
count += 1 # 发现一个新岛屿
dfs(i, j) # 把整座岛淹掉
return count
时间复杂度:
O(m × n)
每个格子最多访问一次。
空间复杂度:
O(m × n)
最坏情况递归深度为整个网格。
最长公共子序列,输出公共子序列(字节国际电商)¶
给定两个字符串 text1 和 text2,请返回它们的最长公共子序列(Longest Common Subsequence, LCS)。
如果不存在公共子序列,返回空字符串 ""。
说明:
子序列是指在不改变字符相对顺序的情况下,通过删除某些字符(或不删除)得到的新字符串。
一个字符串的子序列可以是该字符串本身。
如果存在多个最长公共子序列,返回其中任意一个即可。
示例:
输入: text1 = "abcde" text2 = "ace"
输出: "ace"
核心思想:
需要用到输出最长公共子序列长度
1)DP 表记录的是“最优值结构”
2)回溯是在“最优值结构”上反向找路径
- 当字符相等时,一定来自左上角。
- 当字符不等时,一定来自上或左,选值更大的方向。
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> str:
m, n = len(text1), len(text2)
# dp[i][j] 表示 text1[:i] 和 text2[:j] 的 LCS 长度
dp = [[0] * (n + 1) for _ in range(m + 1)]
print(dp)
# 1. 先计算长度
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# 2. 回溯构造字符串
print(dp)
i, j = m, n
res = []
while i > 0 and j > 0:
# 当前字符相同,说明一定在 LCS 里
if text1[i - 1] == text2[j - 1]:
res.append(text1[i - 1])
i -= 1
j -= 1
# 否则看是从哪里转移过来的
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
# 因为是从后往前加的,需要反转
return ''.join(reversed(res))
text1 = "abcdefgadc"
text2 = "acebbfdc"
print(Solution().longestCommonSubsequence(text1, text2))
[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]] [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1, 1, 1, 1], [0, 1, 1, 1, 2, 2, 2, 2, 2], [0, 1, 2, 2, 2, 2, 2, 2, 3], [0, 1, 2, 2, 2, 2, 2, 3, 3], [0, 1, 2, 3, 3, 3, 3, 3, 3], [0, 1, 2, 3, 3, 3, 4, 4, 4], [0, 1, 2, 3, 3, 3, 4, 4, 4], [0, 1, 2, 3, 3, 3, 4, 4, 4], [0, 1, 2, 3, 3, 3, 4, 5, 5], [0, 1, 2, 3, 3, 3, 4, 5, 6]] acefdc
最大化分堆后的最小堆大小(抖音)¶
给定一个整数数组 stones,其中 stones[i] 表示第 i 类石头的数量。每一类石头需要 单独进行拆分,不同类型之间 不能混合到同一堆中。
现在需要将所有石头拆分成 恰好 m 堆。拆分规则如下:
- 每一类石头
stones[i]可以被拆分成若干堆。 - 每一堆只能包含 同一种类型的石头。
- 所有类型拆分后的堆数之和必须 恰好等于
m。 - 每一堆的大小为正整数。
- 记所有堆的大小为
g₁, g₂, ..., gₘ,目标是 最大化
$$ \min(g_1, g_2, ..., g_m) $$
即希望所有堆中 最小的堆尽可能大。
输出需要包含:
- 最大可能的最小堆大小
k - 每个
stones[i]的具体拆分方案
输出格式
返回一个结果:
[k, groups]
其中:
k表示最小堆大小groups[i]表示stones[i]的拆分结果
示例
输入
stones = [5, 8]
m = 5
解释:
- 第一类石头数量为
5 - 第二类石头数量为
8 - 需要最终得到
5堆
一种最优拆分方案:
5 → [2,3]
8 → [2,3,3]
最终所有堆为:
[2,3,2,3,3]
最小堆大小:
min = 2
输出:
[2, [[2,3], [2,3,3]]]
def solve(stones: list[int], m: int):
"""
最大化分堆后的最小堆大小
Args:
stones: 各类石头数量
m: 目标总堆数(恰好)
Returns:
[k, groups] k=最优最小堆大小, groups[i]=第i类的具体拆分列表
"""
n = len(stones)
# ── 边界检查 ──────────────────────────────────────────────────────────────
# 每类石头至少需要独立 1 堆,因此 m 不能小于 n
if m < n:
raise ValueError(f"m={m} < n={n},堆数不足以覆盖所有类型")
# ── Step 1: 二分搜索最优 k ────────────────────────────────────────────────
def feasible(k: int) -> bool:
"""
判断"最小堆大小为 k"是否可行:
- 每类石头必须 >= k(才能凑出至少 1 堆)
- 所有类合计最多能拆出的堆数 >= m
"""
total_max_heaps = 0
for s in stones:
if s < k: # 连 1 堆都凑不出来
return False
total_max_heaps += s // k
return total_max_heaps >= m
lo, hi = 1, max(stones)
while lo < hi:
mid = (lo + hi + 1) // 2 # 上取中,防止死循环(向上逼近)
if feasible(mid):
lo = mid # mid 可行 → 尝试更大
else:
hi = mid - 1 # mid 不可行 → 缩小上界
k = lo # 最终最优最小堆大小
# ── Step 2: 分配各类石头的堆数 c[i] ─────────────────────────────────────
# 约束:1 ≤ c[i] ≤ floor(stones[i]/k),且 sum(c) = m
# 策略:先每类分 1 堆,再把剩余堆数按"可用容量"贪心分配
c = [1] * n
remaining = m - n # 还需额外分配的堆数
for i in range(n):
if remaining == 0:
break
max_extra = stones[i] // k - 1 # 第 i 类还能额外承接的堆数
add = min(remaining, max_extra)
c[i] += add
remaining -= add
# ── Step 3: 按 c[i] 均匀拆分每类石头 ────────────────────────────────────
# 将 stones[i] 拆成 c[i] 堆,尽量均匀:
# r = stones[i] % c[i] 堆大小为 q+1,其余 c[i]-r 堆大小为 q
# 保证每堆 >= k(因为 c[i] <= floor(stones[i]/k) → q = floor(stones[i]/c[i]) >= k)
groups = []
for i in range(n):
q, r = divmod(stones[i], c[i])
group = [q + 1] * r + [q] * (c[i] - r)
groups.append(group)
return [k, groups]
## 运行结果
stones = [6, 5, 10, 9]
m = 8
print(solve(stones, m))
[3, [[3, 3], [5], [4, 3, 3], [5, 4]]]
a的b次方(阿里)¶
def fast_pow(a: float, b: int) -> float:
"""
计算 a 的 b 次方(a^b),使用快速幂算法(O(log n))
参数:
a: 底数(可以是浮点数)
b: 指数(可以是负数、0、正数)
返回:
a^b 的结果
"""
# 1. 特殊情况:b == 0
# 任何数的 0 次方为 1(包括负数和正数)
if b == 0:
return 1.0
# 2. 处理负指数
# a^(-b) = 1 / (a^b)
if b < 0:
return 1 / fast_pow(a, -b)
# 3. 初始化结果
result = 1.0
# 4. 快速幂核心
while b > 0:
# 如果当前 b 是奇数
if b % 2 == 1:
result *= a # 乘上当前底数
# 底数平方
a *= a
# 指数右移(等价于 b //= 2)
b //= 2
return result
a = 4
b = 5
print(fast_pow(a, b))
1024.0
可以把这段算法理解为:一边读取指数 (b) 的二进制,一边决定“这一位要不要用”,同时把底数不断升级为更高次幂。
用一个具体例子说明:计算 (2^{13})。
先把 13 写成二进制: $ 13 = 1101_2 = 1 + 4 + 8 $
算法从最低位开始处理(从右往左):
- 初始:a = 2,b = 13,result = 1
第1轮:b=13(奇数)
- “奇数”意味着:当前二进制最低位是 1 → 这一位要用
- 所以:result *= a → result = 2
- 然后 a 平方:a = 4(表示下一位对应的 (2^2))
- b 整除 2:b = 6(相当于右移一位,从 1101 → 110)
第2轮:b=6(偶数)
- 偶数 → 当前位是 0 → 这一位不用
- result 不变
- a 平方:a = 16(现在表示 (2^4))
- b // 2:b = 3(110 → 11)
第3轮:b=3(奇数)
- 奇数 → 当前位是 1 → 要用
- result *= a → result = 2 × 16 = 32
- a 平方:a = 256(表示 (2^8))
- b // 2:b = 1(11 → 1)
第4轮:b=1(奇数)
- 奇数 → 要用
- result *= a → result = 32 × 256 = 8192
- a 平方(无所谓了)
- b // 2 → 0(结束)
核心本质(关键解释你卡住的点)
“b 是奇数 → 乘” 本质是:当前二进制位是 1,需要把这一位对应的幂乘进去
“b //= 2” 本质是:把指数右移一位,去看下一位(二进制)
一句话总结
这段代码其实是在做:
从低位到高位扫描 b 的二进制:遇到 1 就乘当前幂,同时每一步把底数平方以对应更高位。
如果用最直观的话讲:
“b 是奇数”不是数学技巧,而是“这一位是 1”; “b 除以 2”也不是随便除,而是“去看下一位”。
经典鸡蛋掉落问题¶
给定 k 个鸡蛋 和一栋共有 n 层楼 的建筑,存在一个未知的临界楼层 (f)(满足 (0 \le f \le n)),使得:
- 从 高于第 (f) 层 的楼层扔下鸡蛋,鸡蛋一定会碎;
- 从 第 (f) 层或以下 的楼层扔下鸡蛋,鸡蛋一定不会碎;
- 每次只能选择一个鸡蛋,从任意一层楼扔下;
- 一旦鸡蛋碎掉,该鸡蛋不能再使用;
- 未碎的鸡蛋可以重复使用。
目标是:
设计一种策略,在 最坏情况下测试次数最少,确定这个临界楼层 (f) 的具体数值。
需要求解的问题是:
在给定 k 个鸡蛋 和 n 层楼 的条件下,最少需要多少次测试(最坏情况下),才能保证一定能够确定临界楼层 (f)。
形式化表达为:
输入:
- 整数 (k):鸡蛋数量
- 整数 (n):楼层数量
输出:
- 一个整数,表示最坏情况下确定临界楼层所需的最少测试次数
例如:
示例 1: 输入: k = 1, n = 2 输出: 2 解释: 只有一个鸡蛋时只能线性扫描:从第 1 层开始逐层测试。
示例 2: 输入: k = 2, n = 6 输出: 3
示例 3: 输入: k = 3, n = 14 输出: 4
整体分析¶
在正式进入两种思路之前,我想先帮你理清这道题为什么"难",以及难在哪里。
这道题的本质困难在于:我们面对的是一个"最坏情况下的最优策略"问题。注意这两个关键词的叠加——"最坏情况"意味着对手会专门选择让你测试次数最多的临界层;"最优策略"意味着你需要在这种假设下,找到一个让总次数尽可能少的方法。因此它既不是纯粹的贪心,也不是简单的二分,而是一个需要通过动态规划来穷举所有策略并取最优的过程。
很多同学做不出来,往往卡在一个思维定势上:直觉上会想"我能不能二分?"答案是不完全能——鸡蛋数量的限制打破了二分的前提条件。如果你只有一个鸡蛋,你根本不敢从中间层扔,因为一旦碎了就再也无法向上探索。这个"资源约束"是这道题核心复杂性的来源。
两种思路的区别在于如何定义状态。思路一是"正向思维":给定资源(蛋数和楼层),求代价(测试次数)。思路二是"逆向思维":给定资源(蛋数)和代价(测试次数的预算),求能力(能确定多少层)。后者更为精妙,也是这道题最优解的来源。
思路一:dp[i][j] — 给定 i 个蛋、j 层楼,最少需要多少次?¶
核心状态定义
令 dp[i][j] 表示:在有 i 个鸡蛋、楼层数为 j 的情况下,最坏情况下确定临界层所需的最少测试次数。
这是最自然的定义方式,你已经比较熟悉它,所以我在这里重点讲状态转移方程的推导逻辑,确保你真正吃透。
状态转移的推导
假设我们有 i 个鸡蛋、j 层楼,我们决定在第 x 层(1 ≤ x ≤ j)扔下一个鸡蛋,此时有两种结果:
第一,鸡蛋碎了。说明临界层在第 x 层以下(1 到 x-1 层),我们损失了一个鸡蛋,此后子问题规模变为 dp[i-1][x-1]。
第二,鸡蛋没碎。说明临界层在第 x 层及以上(x 到 j 层),鸡蛋完好,此后子问题规模变为 dp[i][j-x](因为 x 层以上还有 j-x 层未确认)。
由于对手会选对我们最不利的结果,所以这次扔蛋的"实际代价"是两种结果中的最大值(最坏情况)。我们在所有可能的楼层 x 中选择让这个最大值最小的那个,因此:
dp[i][j] = 1 + min over x in [1, j] of { max(dp[i-1][x-1], dp[i][j-x]) }
这里的 1 代表这一次扔蛋本身消耗了一次机会。
一个关键的优化观察
朴素地枚举所有 x 的时间复杂度是 O(k·n²),对于 n=10000 这样的数据会超时。注意到:随着 x 增大,dp[i-1][x-1] 单调递增(楼层越多越难确定),而 dp[i][j-x] 单调递减(剩余楼层越少越容易)。最优的 x 就在这两条曲线的交叉点附近,可以用二分搜索来定位,将时间复杂度降至 O(k·n·log n)。
Python 代码实现
def superEggDrop_dp1(k: int, n: int) -> int:
# dp[i][j] 表示 i 个蛋、j 层楼时的最少测试次数
# 用字典做记忆化,避免初始化整个二维数组
from functools import lru_cache
@lru_cache(maxsize=None)
def dp(eggs, floors):
# 边界条件
if eggs == 1:
return floors # 只有一个蛋,只能逐层线性扫描
if floors == 0:
return 0 # 没有楼层,不需要测试
if floors == 1:
return 1 # 只有一层,测一次即可
# 二分搜索最优的扔蛋楼层 x
lo, hi = 1, floors
while lo + 1 < hi:
mid = (lo + hi) // 2
# 蛋碎(往下找)vs 没碎(往上找)的代价
break_case = dp(eggs - 1, mid - 1) # 蛋碎,检查 mid 以下
safe_case = dp(eggs, floors - mid) # 没碎,检查 mid 以上
if break_case < safe_case:
lo = mid # 往上移动以减小 safe_case
elif break_case > safe_case:
hi = mid # 往下移动以减小 break_case
else:
lo = hi = mid
# 在 lo 和 hi 两个候选点取最优
ans = 1 + min(
max(dp(eggs - 1, lo - 1), dp(eggs, floors - lo)),
max(dp(eggs - 1, hi - 1), dp(eggs, floors - hi))
)
return ans
return dp(k, n)
思路一的好处是直观,状态含义清晰;缺点是即使加了二分优化,对于极大的 n(如 10^9)仍然无法应对。这就引出了思路二的必要性。
思路二:dp[k][m] — 给定 k 个蛋、m 次机会,最多能确定多少层?¶
核心状态定义(思维反转)
这是这道题最精彩的洞见。我们不再问"需要多少次",而是反过来问"给我 m 次机会,我能确定多少层"。
令 dp[k][m] 表示:有 k 个鸡蛋、恰好 m 次测试机会,在最优策略下,最多能确定(即:保证一定能找到临界层)的楼层总数。
最终答案就是:找到最小的 m,使得 dp[k][m] ≥ n。
状态转移的推导(这是精华)
有 k 个蛋、m 次机会,我们从某一层 x 扔下一个蛋,仍然有两种结果:
第一,蛋碎了。剩余资源变为 k-1 个蛋、m-1 次机会。根据 dp 定义,这能够确定 dp[k-1][m-1] 层楼(即 x 层以下这么多层)。
第二,蛋没碎。剩余资源变为 k 个蛋、m-1 次机会,能够确定 dp[k][m-1] 层楼(即 x 层以上这么多层)。
加上第 x 层本身(这一层已经通过这次测试被确认了),我们总共能覆盖的楼层数为:
dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1
这个公式之所以优美,是因为它与 x 的选择完全无关——无论我们选在哪一层扔,能覆盖的总楼层数都是这个值。这意味着最优策略天然地将两部分分配均衡,不需要额外优化。
边界条件
dp[0][m] = 0(没有蛋,什么都确认不了),dp[k][0] = 0(没有机会,什么都确认不了),dp[1][m] = m(一个蛋只能线性扫描,m 次最多确认 m 层)。
Python 代码实现
def superEggDrop_dp2(k: int, n: int) -> int:
# dp[k][m] = 有 k 个蛋、m 次机会,最多能确定多少层
# m 的上界不超过 n(最坏情况也就用 n 次)
# 用一维滚动数组节省空间:dp[j] 表示当前蛋数下,j 次机会能确定的楼层数
# 从 m=1 开始迭代,直到 dp[k] >= n 为止
dp = [0] * (n + 1) # dp[m],初始蛋数为 1 时,m 次=m 层(稍后处理)
# 外层循环:测试次数 m 从 1 开始递增
# 内层循环:蛋的数量从 k 递减到 1(注意更新顺序很关键)
# 重新用二维 dp 让逻辑更清晰
# dp2[i][j] 表示 i 个蛋 j 次机会能确定的楼层数
# 为节省空间,用两行滚动
prev = list(range(n + 1)) # 1 个蛋时:dp[1][m] = m
for eggs in range(2, k + 1):
curr = [0] * (n + 1)
for moves in range(1, n + 1):
# 核心递推式
curr[moves] = prev[moves - 1] + curr[moves - 1] + 1
# 一旦能确定 >= n 层,后续的 moves 不需要再算了
if curr[moves] >= n:
# 此时 moves 就是答案(对于这个 eggs 数量)
# 但我们继续填满数组以备后用
pass
prev = curr
# 找最小的 m 使得 prev[m] >= n
for m in range(1, n + 1):
if prev[m] >= n:
return m
return n # 保底(理论上不会到这里)
# 更简洁的版本,直接找答案
def superEggDrop_dp2_clean(k: int, n: int) -> int:
# dp[j] 代表当前蛋数 + j 次机会能覆盖的最大楼层数
# 初始化为 1 个蛋的情况
dp = list(range(n + 1)) # dp[m] = m(1个蛋时,m次能查m层)
for _ in range(k - 1): # 蛋从 2 增加到 k,共需迭代 k-1 次
new_dp = [0] * (n + 1)
for m in range(1, n + 1):
new_dp[m] = dp[m - 1] + new_dp[m - 1] + 1
# 提前退出:一旦已经可以覆盖 n 层就不必继续
dp = new_dp
# 找最小的 m 使得 dp[m] >= n
for m in range(1, n + 1):
if dp[m] >= n:
return m
return n
思路二的最大优势在于:m 的最大值不超过 O(log n)(因为即使是二分搜索,log₂(10^9) ≈ 30),所以整体时间复杂度是 O(k log n),可以轻松应对 n 极大的情况。
两种思路的对比总结¶
思路一的状态 dp[i][j] 直接对应问题描述,容易理解,适合作为入门解法;其瓶颈在于对极大 n 无能为力。思路二的状态 dp[k][m] 来自一个"维度互换"的洞见——将"需要多少次"变成"给定次数能覆盖多少",不仅推导出了优雅的递推式,还将时间复杂度从 O(kn) 压缩到了 O(k log n),是面试中体现深度思维的解法。
如何培养动态规划思维¶
这是你问的最有价值的问题。动态规划能力的核心不是"记住模板",而是培养三种感知能力。
第一,识别"最优子结构 + 重叠子问题"的嗅觉。 每当你看到"最少/最多/最大/最小",同时问题的规模可以通过决策分解为更小的同类问题时,就应该条件反射地想到 DP。鸡蛋问题中,"最少次数"和"可以递归拆分为更小的蛋数+楼层子问题"这两个信号同时出现。
第二,学会从多角度定义状态。 这是最难培养的能力,也是区分普通解法与优雅解法的关键。对同一个问题,不同的状态定义会导致截然不同的时间复杂度(如本题的 O(kn²) vs O(k log n))。训练方法是:做完一道题后,强迫自己换一个视角重新定义状态,看看能否推导出新的递推式,再比较两种方法的优劣。
第三,区间、序列、树形 DP 的模式识别。 大多数 DP 题目属于几个固定的范式:线性 DP(如爬楼梯、打家劫舍)、区间 DP(如矩阵链乘、括号问题)、背包类(如 0/1 背包、完全背包)、树形 DP(如二叉树上的最优路径)。鸡蛋问题属于比较特殊的"资源约束下的策略优化"类型,与这些主流范式都有所不同,需要单独积累。
推荐训练路径,按梯度排列如下。LeetCode 上有一条官方的 DP 学习路径,建议严格按顺序完成:从第 70 题(爬楼梯)、第 198 题(打家劫舍)建立基础直觉,然后挑战第 322 题(零钱兑换)掌握一维背包,再到第 1143 题(最长公共子序列)理解二维 DP,最终攻克第 312 题(戳气球)这样的区间 DP 难题,以及本题(第 887 题)这样的高阶题目。
在思维方法论上,强烈推荐阅读《算法导论》第 15 章(动态规划),它对"最优子结构的证明"有非常严格的讲解,读完后你对 DP 的理解会从"会用"上升到"知其所以然"。此外,neetcode.io 提供了分类清晰的视频讲解,每道题都有从暴力到最优的完整推导过程,非常适合你这个阶段使用。
最后一个窍门:每道 DP 题做完后,写下"如果把状态定义换一种方式,会发生什么"这样的反思笔记。 鸡蛋问题的思路二就是这样被发现的——有人在思路一的基础上问了一句"如果我把代价和能力互换,会得到什么",然后推导出了更优雅的解法。这种主动换视角的习惯,是区分能解题和真正理解 DP 的核心差异。
def superEggDrop(k: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(k + 1)]
for j in range(1, n + 1):
dp[1][j] = j
for i in range(2, k + 1):
for j in range(1, n + 1):
dp[i][j] = float('inf')
for x in range(1, j + 1):
worst = 1 + max(dp[i - 1][x - 1], dp[i][j - x])
dp[i][j] = min(dp[i][j], worst)
return dp[k][n]
k, n = 2, 10
print(superEggDrop(k, n))
4
先建立一个关键直觉:你的"预算"和"步长"必须匹配
我先不讲代码,先讲一个思维实验。假设你只有 2 个鸡蛋、10 层楼,然后我问你:你敢不敢从第 5 层开始扔?
你应该感到不安。为什么?因为一旦鸡蛋在第 5 层碎了,你只剩 1 个蛋,而你还不知道临界层在 1、2、3、4 层中的哪一层,你只能从第 1 层开始一层一层往上试。这 4 层就要花掉你 4 次,加上之前在第 5 层的那 1 次,总共 5 次。
然后你从第 5 层换到第 8 层继续,如果在第 8 层碎了,你又要线性扫描第 6、7 层,又要花 2 次,加上第 8 层那 1 次,总共已经用了 1(第5层)+ 1(第8层)+ 2 = 4次……等等,其实在不同楼层决策,最坏情况的次数是不同的。这里直觉已经开始混乱了——这正是你感到"想不出来"的根本原因:层与层之间的代价是不均衡的。
两个鸡蛋问题的核心约束:你的步长必须"递减"
现在我来给你建立正确的直觉。
用 2 个蛋解决问题,本质上是一个"一次性探测 + 线性兜底"的两阶段策略。第一个蛋负责"跳跃式定位大区间",一旦它碎了,第二个蛋就只能在那个小区间里逐层线性扫描。
这意味着:如果你第一个蛋用了 m 次跳跃,那每次跳跃后,万一碎了,你的线性扫描代价必须控制在剩余次数之内。
具体来说,假设你给自己设定总次数预算为 t 次,那么:
第 1 次扔,你选择第 t 层。为什么是 t 层?因为如果它碎了,你还剩 t-1 次和 1 个蛋,你最多能线性扫描 t-1 层(即第 1 层到第 t-1 层),恰好够用。
如果第 1 次没碎,你上移,第 2 次扔第 t + (t-1) 层。为什么步长变成了 t-1?因为此时你已经花掉了 1 次,预算只剩 t-1,万一碎了,你只能再扫描 t-2 层,所以这个区间的大小只能是 t-1。
以此类推,每上跳一次,步长就减少 1。这就是"递减步长"策略,也是 2 个蛋问题的最优解结构。
那么 t 次总共能覆盖多少层?就是 t + (t-1) + (t-2) + ... + 1 = t(t+1)/2。
现在直接回答:2个蛋10层楼最坏需要几次?
你需要找最小的 t,使得 t(t+1)/2 ≥ 10:
当 t = 3 时:3×4/2 = 6,覆盖不了 10 层,不够。
当 t = 4 时:4×5/2 = 10,恰好覆盖 10 层,答案就是 4 次。
具体策略是这样执行的:第一次在第 4 层扔(步长 4),第二次在第 7 层扔(步长 3),第三次在第 9 层扔(步长 2),第四次在第 10 层扔(步长 1)。我来逐一验证最坏情况:
场景一:第 4 层碎了 → 线性扫描 1、2、3 层 → 最多再用 3 次 → 总共 1 + 3 = 4 次。
场景二:第 4 层没碎,第 7 层碎了 → 线性扫描 5、6 层 → 再用 2 次 → 总共 1 + 1 + 2 = 4 次。
场景三:第 4、7 层没碎,第 9 层碎了 → 线性扫描第 8 层 → 再用 1 次 → 总共 1 + 1 + 1 + 1 = 4 次。
场景四:第 4、7、9 层都没碎,第 10 层扔下去 → 无论碎没碎都能确定答案 → 总共 4 次。
每种最坏情况都恰好是 4 次。这正是"递减步长"策略的精妙之处:它让每种最坏情况的代价完全均等,没有任何一种情况比其他情况多花一次,这就是最优性的体现。
回到你的代码:x 的枚举到底在做什么?
现在你再看这段代码,感觉就不一样了:
for x in range(1, j + 1):
worst = 1 + max(dp[i - 1][x - 1], dp[i][j - x])
dp[i][j] = min(dp[i][j], worst)
这里枚举 x 的本质,就是在模拟"我在哪一层扔第一个蛋"这个决策。对于每一个候选的 x,max(...) 计算了在那一层扔下去之后的最坏情况代价,而 min(...) 则是在所有候选楼层中挑出让最坏情况最轻的那个决策——也就是我们上面分析的"步长递减"策略在数学上的等价表达。
你之前卡壳的点是"没想到要枚举 x",其实这恰恰是 DP 里最重要的思维动作:用穷举来代替"直觉上找不到规律"的决策。当你无法直接想清楚"应该在哪层扔最优"时,就枚举所有可能,让 min-max 结构替你找出最优决策。这个模式在很多 DP 题里反复出现,比如矩阵链乘、戳气球,本质都是"枚举决策点,取最优"。
建立这种直觉的方法很简单:下次遇到最优化 + 递归子结构的题,先问自己"这道题的核心决策是什么",再问"这个决策有哪些候选值",然后大胆地全部枚举,用 min/max 取优。不要一开始就想"哪个选择最优"——你可能根本想不出来,但机器可以帮你枚举出来。先把"穷举 + 剪枝"的框架搭对,优化(比如二分加速)是后面的事。
题目:长度不超过 k 的连续子数组最大和¶
给定一个整数数组 nums(长度为 n,元素可正可负)以及一个正整数 k,请找出所有长度不超过 k 的非空连续子数组中,和最大的那个,返回该最大和。
输入:整数数组 nums,正整数 k(1 ≤ k ≤ n)。
输出:一个整数,表示所有满足条件的连续子数组中的最大和。
示例:
输入:nums = [2, -1, 5, -3, 4],k = 3
输出:6
解释:子数组 [2, -1, 5] 长度为 3,不超过 k=3,其和为 6,是所有合法子数组中最大的。
约束条件:
1 ≤ k ≤ n ≤ 10^5
-10^4 ≤ nums[i] ≤ 10^4
def maxSumWithLengthK_brute(nums, k):
n = len(nums)
# 前缀和
P = [0] * (n + 1)
for i in range(n):
P[i + 1] = P[i] + nums[i]
ans = float('-inf')
for j in range(1, n + 1): # 右端点
for i in range(max(0, j - k), j): # 左端点,窗口长度不超过k
ans = max(ans, P[j] - P[i])
return ans
nums = [1, 2, 4, 10, 5, 0, 100]
k = 3
print(maxSumWithLengthK_brute(nums, k))
105
暴力枚举时,固定右端点 j,然后遍历所有合法左端点 i,逐个计算 P[j] - P[i] 并取最大值。当右端点移动到 j+1 时,又重新遍历一遍合法左端点。这里的冗余是:对左端点集合的"找最小值"操作,在每个右端点处都从零开始重做了一遍,但左端点集合的变化其实非常有规律——每次只是右边新增一个候选、左边可能淘汰一个过期的。
对于右端点 j,我们需要的不是"把所有合法左端点都比一遍",而是"直接知道合法左端点中前缀和最小的那一个"。如果我们能始终维护一个数据结构,使得这个最小值随时可以 O(1) 读取,那么每个右端点只需要做一次减法,整体就降为 O(n)。 单调队列正是这个数据结构。它的队头,始终存放的是当前合法窗口内前缀和最小的左端点。右端点每向右移动一步,队列只做两件轻量的事情:从左边淘汰过期的下标,从右边加入新候选并维护单调性。读答案时直接用 running - dq[0],不需要任何遍历。
用一句话总结:
暴力的代价在于:每个右端点都重新"扫描"一遍左端点集合来找最小值。单调队列的贡献在于:把这个"找最小值"的过程增量化——左端点集合每次只变化一点点,队列以 O(1) 摊还代价跟踪这个变化,使得每个右端点可以直接 O(1) 读取最优左端点,而不是重新扫描。
from collections import deque
def maxSumWithLengthK(nums, k):
n = len(nums)
# 前缀和
P = [0] * (n + 1)
for i in range(n):
P[i + 1] = P[i] + nums[i]
ans = float('-inf')
dq = deque() # 存下标,队头到队尾 P[i] 单调递增
for j in range(1, n + 1):
# 1. 先把合法的左端点 i = j - k 加入队列
i = j - 1 # 当前右端点 j 对应的新候选左端点
# 队尾弹出:维护单调递增(P[i] 更小,队尾更大的没有意义)更小的前缀和永远更优
while dq and P[dq[-1]] >= P[i]:
dq.pop()
dq.append(i)
# 2. 队头弹出:左端点过期(窗口长度超过 k)
# 合法左端点范围:i >= j - k
while dq and dq[0] < j - k:
dq.popleft()
# 3. 队头就是当前窗口内 P[i] 最小的左端点
ans = max(ans, P[j] - P[dq[0]])
return ans