剛做完 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
