题目一：最大累积得分游戏
问题描述
一个游戏规则如下：
- 玩家从第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