題目一：最大累積得分遊戲
問題描述
一個遊戲規則如下：
- 玩家從第0個格子開始，初始得分為0
- 有n個格子，編號從0到n-1，每個格子有一個分值
- 第0個格子的分值始終為0
- 每次移動可以：
- 向右移動1步，或
- 向右移動p步，其中p是個位數為3的素數（如3、13、23、43等）
- 玩家不能超過最後一個格子
- 當玩家落在某個格子時，該格子的分值會加到總分中
- 遊戲在玩家到達第n-1個格子時結束
求：到達終點的最大可能得分
解題思路
第一步：預處理素數
首先需要找出所有個位數為3的素數。這些素數是：3、13、23、43、53、73、83等。
def get_primes_ending_with_3(max_n):
"""獲取所有不超過max_n且個位數為3的素數"""
primes = []
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
for i in range(3, int(num**0.5) + 1, 2):
if num % i == 0:
return False
return True
for num in range(3, max_n, 10): # 個位數為3的數：3, 13, 23, 33...
if is_prime(num):
primes.append(num)
return primes
第二步：動態規劃求解
使用DP數組，其中dp[i]表示到達第i個格子的最大得分。
關鍵思路：
- 初始化：
dp[0] = 0（起點），其他位置初始化為負無窮（表示不可達） - 狀態轉移：對於每個可達的位置i，嘗試所有可能的移動方式
- 移動1步到i+1
- 移動p步到i+p（p為個位數為3的素數）
- 取較大值更新目標位置
def max_score_game(cells, n):
"""
求最大累積得分
Args:
cells: 格子分值數組
n: 格子總數
Returns:
到達終點的最大得分
"""
# 預處理素數
primes = get_primes_ending_with_3(n)
# DP初始化
dp = [-float('inf')] * n
dp[0] = cells[0] # 起點分值為0
# 狀態轉移
for i in range(n):
if dp[i] == -float('inf'):
continue # 不可達的位置跳過
# 嘗試移動1步
if i + 1 < n:
dp[i + 1] = max(dp[i + 1], dp[i] + cells[i + 1])
# 嘗試移動p步（p為個位數為3的素數）
for p in primes:
if i + p < n:
dp[i + p] = max(dp[i + p], dp[i] + cells[i + p])
else:
break # 後續素數更大，不需要繼續
return dp[n - 1]
第三步：示例演算
以題目給定的例子：cells = [0, -10, -20, -30, 50]，n = 5
- 起點：dp[0] = 0
- 從0出發：
- 移動1步到1：dp[1] = 0 + (-10) = -10
- 移動3步到3：dp[3] = 0 + (-30) = -30
- 從1出發（dp[1] = -10）：
- 移動1步到2：dp[2] = -10 + (-20) = -30
- 移動3步到4：dp[4] = -10 + 50 = 40 ✓
- 從2出發（dp[2] = -30）：
- 移動1步到3：dp[3] = max(-30, -30 + (-30)) = -30
- 移動3步到5：超出範圍
- 從3出發（dp[3] = -30）：
- 移動1步到4：dp[4] = max(40, -30 + 50) = 40
最終答案：40
時間複雜度分析
- 預處理素數：O(n log log n)（篩法）
- DP遍歷：O(n × k)，其中k是個位數為3的素數個數（通常很小）
- 總體：O(n log log n)
常見陷阱
❌ 陷阱1：忘記初始化為負無窮，導致不可達位置被錯誤計算 ✅ 解決：明確區分可達和不可達狀態
❌ 陷阱2：素數預處理不完整，遺漏某些素數 ✅ 解決：使用篩法或逐一檢驗，確保所有個位數為3的素數都被找到
❌ 陷阱3：沒有考慮負數分值的情況 ✅ 解決：DP初始化為負無窮，正確處理所有分值
題目二：最少操作次數
問題描述
給定一個正整數n，每次操作可以：
- 加上2^i（i ≥ 0），或
- 減去2^i（i ≥ 0）
求：將n變為0的最少操作次數
解題思路
核心觀察：二進制貪心
這道題的關鍵在於觀察n的二進制表示，並利用二進制進位的性質。
關鍵規律：
- 如果當前位是0，直接右移（相當於除以2）
- 如果當前位是1，需要通過加或減來消除這個1
詳細算法
def min_operations(n):
"""
求將n變為0的最少操作次數
Args:
n: 正整數
Returns:
最少操作次數
"""
operations = 0
while n > 0:
# 觀察n的最後兩位二進制
last_two_bits = n & 3 # 取最後兩位：n % 4
if last_two_bits == 0:
# 00：直接右移
n >>= 1
elif last_two_bits == 1:
# 01：減1（變成00），然後右移
n -= 1
operations += 1
elif last_two_bits == 2:
# 10：直接右移
n >>= 1
else: # last_two_bits == 3
# 11：加1（進位變成100），然後右移
n += 1
operations += 1
operations += 1 # 右移操作計數
return operations
算法解釋
為什麼這樣做？
觀察二進制的最後兩位：
- 00：最後一位是0，直接右移即可
- 01：最後一位是1，需要減1變成00，然後右移
- 10：最後一位是0，直接右移即可
- 11：最後兩位都是1，加1會產生進位（變成100），然後右移
這樣做的好處是：
- 每次操作都能消除至少一位
- 通過進位可以合併多個1
- 貪心策略保證最優性
示例演算
以n = 5為例：
n = 5 = 101₂
第1步：最後兩位是01
- 減1：5 - 1 = 4 = 100₂（操作1）
- 右移：4 >> 1 = 2 = 10₂（操作2）
第2步：最後兩位是10
- 右移：2 >> 1 = 1 = 1₂（操作3）
第3步：最後兩位是01
- 減1：1 - 1 = 0（操作4）
- 右移：0 >> 1 = 0（操作5）
總操作數：5
驗證：5 → 4 → 2 → 1 → 0
(減1) (÷2) (÷2) (減1)
等等，讓我重新計算。題目說的是"操作"，每次操作是加或減2^i。
重新理解題意
實際上，我們需要重新理解這個問題：
- 每次操作是加或減一個2的冪次
- 目標是用最少的操作次數將n變為0
更優的思路：這等價於用最少個數的2的冪次來表示n。
例如：
- n = 5 = 4 + 1 = 2² + 2⁰（2個操作）
- n = 5 = 8 - 3 = 8 - 2 - 1 = 2³ - 2¹ - 2⁰（3個操作）
所以最優是2個操作。
改進的算法
def min_operations_v2(n):
"""
求將n變為0的最少操作次數（改進版）
使用二進制表示的1的個數作為基礎
"""
operations = 0
while n > 0:
last_two_bits = n & 3
if last_two_bits == 0:
# 00：直接右移
n >>= 1
elif last_two_bits == 1:
# 01：減1
n -= 1
operations += 1
elif last_two_bits == 2:
# 10：直接右移
n >>= 1
else: # last_two_bits == 3
# 11：加1（進位）
n += 1
operations += 1
return operations
對於n = 5：
5 = 101₂
最後兩位是01 → 減1 → 4 = 100₂（操作1）
最後兩位是00 → 右移 → 2 = 10₂
最後兩位是10 → 右移 → 1 = 1₂
最後兩位是01 → 減1 → 0（操作2）
總操作數：2 ✓
時間複雜度分析
- 循環次數：O(log n)（每次至少右移一位）
- 每次迭代：O(1)
- 總體：O(log n)
常見陷阱
❌ 陷阱1：混淆"操作次數"和"右移次數" ✅ 解決：只有加或減才算操作，右移是免費的
❌ 陷阱2：沒有利用進位的性質 ✅ 解決：當最後兩位是11時，加1會產生進位，可以合併多個1
❌ 陷阱3：貪心策略不正確 ✅ 解決：觀察最後兩位，按規律處理
面試應對策略
時間管理
題目一（最大累積得分）：
- 理解題意：3-5分鐘
- 設計算法：5-7分鐘
- 編碼實現：10-15分鐘
- 測試驗證：5分鐘
- 總計：25-35分鐘
題目二（最少操作次數）：
- 理解題意：2-3分鐘
- 分析二進制規律：5-8分鐘
- 編碼實現：8-10分鐘
- 測試驗證：3-5分鐘
- 總計：18-26分鐘
臨場技巧
題目一：
- 先確認素數的定義（個位數為3）
- 明確邊界條件（不能超過n-1）
- 從簡單例子開始推導
題目二：
- 先用幾個例子找規律
- 觀察二進制表示
- 解釋為什麼加1或減1是最優的
常見問題
Q：如果n很大（接近2^60），算法還能工作嗎？
A：可以。題目二的時間複雜度是O(log n)，即使n = 2^60也只需要約60次迭代。題目一需要預處理素數，但個位數為3的素數密度足夠大，不會成為瓶頸。
Q：題目一中，如果所有格子分值都是負數怎麼辦？
A：仍然需要到達終點，所以選擇分值最小的路徑。DP算法會自動處理這種情況。
Q：能否用其他方法解題目二？
A：可以。題目二本質上是求用最少個數的2的冪次表示n。也可以用BFS或記憶化搜索，但二進制貪心是最優的。
完整代碼實現
def get_primes_ending_with_3(max_n):
"""獲取所有不超過max_n且個位數為3的素數"""
primes = []
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
for i in range(3, int(num**0.5) + 1, 2):
if num % i == 0:
return False
return True
for num in range(3, max_n, 10):
if is_prime(num):
primes.append(num)
return primes
def max_score_game(cells):
"""求最大累積得分"""
n = len(cells)
primes = get_primes_ending_with_3(n)
dp = [-float('inf')] * n
dp[0] = cells[0]
for i in range(n):
if dp[i] == -float('inf'):
continue
# 移動1步
if i + 1 < n:
dp[i + 1] = max(dp[i + 1], dp[i] + cells[i + 1])
# 移動p步
for p in primes:
if i + p < n:
dp[i + p] = max(dp[i + p], dp[i] + cells[i + p])
else:
break
return dp[n - 1]
def min_operations(n):
"""求最少操作次數"""
operations = 0
while n > 0:
last_two_bits = n & 3
if last_two_bits == 0:
n >>= 1
elif last_two_bits == 1:
n -= 1
operations += 1
elif last_two_bits == 2:
n >>= 1
else: # last_two_bits == 3
n += 1
operations += 1
return operations
# 測試
if __name__ == "__main__":
# 測試題目一
cells = [0, -10, -20, -30, 50]
print(f"最大得分: {max_score_game(cells)}") # 輸出: 40
# 測試題目二
print(f"最少操作次數: {min_operations(5)}") # 輸出: 2
🚀 需要面試輔助？
oavoservice 提供專業的 OA/VO 輔助服務，幫助你快速通過微軟、亞馬遜等大廠的技術面試。
👉 立即添加微信：Coding0201