刚做完 Uber SWE OA （3月26日），90分钟 2题，平台 HackerRank。一句话总结：两题都是 Hard 级 DP，难度明显高于普通 OA，时间卡得非常紧！尤其是第二题的换根 DP，如果没见过类似题型很容易卡住。下面把完整题目 + 解题思路 分享给大家，造福正在冲 Uber 的同学。
题目 1：Prime Jumps
题目描述 从 0 号格子出发，初始分数为 0。 每一步可以：
- 向右走 1 步，或
- 向右走 p 步（p 是末位为 3 的质数，例如 3、13、23 等）。 落在格子 i 时，加上 cell[i] 的分数。 求到达 n-1 号格子的最大可能分数。
示例 cell = [0, -10, -20, -30, 50] 最大分数 = 40（路径 0→1→4）
约束：n ≤ 10⁴，cell[i] ∈ [-10⁴, 10⁴]
解题思路 经典 DP + 质数预处理
- 先用埃氏筛筛出所有 ≤ n-1 且末位为 3 的质数
- dp[i] = 到达 i 号格子的最大分数
- 转移：dp[i] = max(dp[i-1] + cell[i], 所有合法 p 的 dp[i-p] + cell[i])
参考代码（Python）
Python
def maxGameScore(cell):
n = len(cell)
if n == 1:
return cell[0]
# 埃氏筛：找出所有 <= n-1 且末位为3的质数
max_p = n - 1
is_prime = [True] * (max_p + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(max_p**0.5) + 1):
if is_prime[i]:
for j in range(i*i, max_p + 1, i):
is_prime[j] = False
primes = [p for p in range(2, max_p + 1) if is_prime[p] and p % 10 == 3]
# DP
INF = float('-inf')
dp = [INF] * n
dp[0] = cell[0]
for i in range(1, n):
# 走1步
if dp[i-1] != INF:
dp[i] = dp[i-1] + cell[i]
# 走质数步
for p in primes:
if i >= p and dp[i-p] != INF:
dp[i] = max(dp[i], dp[i-p] + cell[i])
return dp[n-1]
# 测试
cell = [0, -10, -20, -30, 50]
print(maxGameScore(cell)) # 40题目 2：Minimum Reversal
题目描述 给定一个 n 个节点的有向树（n-1 条边），选择一个根节点，使所有边都从根向外指向所需反转边的最小次数，返回该最小次数。
示例 n=4，边 1→4、2→4、3→4 选择 2 为根时，最少需要反转 2 次。
解题思路 树形 DP + 换根 DP（rerooting） 经典题
- 第一次 DFS：以任意节点（1号）为根，计算反转次数
- 第二次 DFS：换根时，只需调整父子边方向，O(1) 更新总次数
- 最终取所有节点 res 中的最小值
参考代码（Python）
Python
from collections import defaultdict
def minReversal(g_nodes, g_from, g_to):
adj = defaultdict(list)
for u, v in zip(g_from, g_to):
adj[u].append((v, 0)) # 原方向 u→v，无需反转
adj[v].append((u, 1)) # 反方向 v→u，需要反转1次
res = [0] * (g_nodes + 1)
visited = [False] * (g_nodes + 1)
# 第一次 DFS：以1为根计算 res[1]
def dfs1(u):
visited[u] = True
total = 0
for v, cost in adj[u]:
if not visited[v]:
total += cost + dfs1(v)
return total
res[1] = dfs1(1)
visited = [False] * (g_nodes + 1)
# 第二次 DFS：换根
def dfs2(u):
visited[u] = True
for v, cost in adj[u]:
if not visited[v]:
res[v] = res[u] + (1 if cost == 0 else -1)
dfs2(v)
dfs2(1)
return min(res[1:g_nodes+1])
# 测试
g_nodes = 4
g_from = [1, 2, 3]
g_to = [4, 4, 4]
print(minReversal(g_nodes, g_from, g_to)) # 2Uber OA 备战建议
- 这两题都偏 Hard，普通 LeetCode 中等题已经不够用了
- 重点复习：跳跃类 DP + 质数预处理、树上换根 DP
- 时间非常紧，建议先写核心逻辑，再补边界和优化
需要更多 2026 Uber 最新 OA 真题、这两题的 Java/C++ 版本，或者 OA 代写 / VO 实时辅导，随时私信我。
Programhelp可以提供：
- 100% 通过的 OA 代写（HackerRank / CodeSignal）
- VO 实时思路引导
- 全程 Offer 协助
祝大家早日 Uber Offer 到手！
End of Text
