只有两个键的键盘 图解题解
这道题到底在问什么
- 输入
- n = 3
- 输出
- 3 （复制 1 次，粘贴 2 次）
- 输入
- n = 1
- 输出
- 0 （初始已经是 1 个，不用操作）
- 输入
- n = 9
- 输出
- 6 （拆成 3 乘 3，每段 3 步）
最优解：一步一步想明白
- 3记住这条:答案 = n 的所有质因子相加。下面用 n=60 一步步试除，把 60 拆成 2 x 2 x 3 x 5。
- 6开局:要分解 60。从最小质数 d=2 开始试除，能整除就把 d 收进答案。
- 7轮到 d=2（紫色）。先看 2×2=4 是否 ≤ 剩余 n=60，成立才继续试除；若 d×d 已大于剩余 n，说明没有更小因子可拆，循环退出，再把剩余 n（若 > 1）作为最后一个质因子补加。
- 860 能被 2 整除。说明这一段要把长度扩大 2 倍，花 2 步。把 2 收进答案。
- 9收下质因子 2（绿色）:ans 加 2 变成 2，剩余 n 缩成 30。继续看 30 还能不能再被 2 整除。
- 1030 能被 2 整除。说明这一段要把长度扩大 2 倍，花 2 步。把 2 收进答案。
- 11收下质因子 2（绿色）:ans 加 2 变成 4，剩余 n 缩成 15。继续看 15 还能不能再被 2 整除。
- 1215 不再被 2 整除，d=2 这一段拆完了。d 加 1，看下一个候选。
- 13轮到 d=3（紫色）。先看 3×3=9 是否 ≤ 剩余 n=15，成立才继续试除；若 d×d 已大于剩余 n，说明没有更小因子可拆，循环退出，再把剩余 n（若 > 1）作为最后一个质因子补加。
- 1415 能被 3 整除。说明这一段要把长度扩大 3 倍，花 3 步。把 3 收进答案。
- 15收下质因子 3（绿色）:ans 加 3 变成 7，剩余 n 缩成 5。继续看 5 还能不能再被 3 整除。
- 165 不再被 3 整除，d=3 这一段拆完了。d 加 1，看下一个候选。
- 17试除循环结束后还剩 n=5，且 5 > 1，说明它是一个大质因子（再没有更小因子能拆它），直接收进答案。
- 18加上最后这个质因子 5，ans = 12，剩余 n 归 1。60 = 2 × 2 × 3 × 5，质因子之和 = 12，就是最少操作次数。
⚠️ 容易写错的地方
✗ 错：收因子时 ans 加的是「次数」如 +1
✓ 对：ans 加的是因子本身 d
扩大到 d 倍要复制 1 次加粘贴 d-1 次，共 d 次，所以加 d
✗ 错：试除到 n 才停，O(n)
✓ 对：d×d ≤ n 即停，O(√n)
大于 √n 的因子最多剩一个，循环后单独加即可
✗ 错：忘了循环结束后剩余 n > 1 要补加
✓ 对：末尾 ans += (n > 1 ? n : 0)
n 本身是质数（如 7、13）时循环里根本没除到它
✗ 错：n = 1 时返回 1
✓ 对：n = 1 返回 0
初始已有 1 个 A，无需任何操作
完整代码（Python / C++ / Java）
Python
class Solution:
def minSteps(self, n: int) -> int:
ans = 0
d = 2
while d * d <= n:
while n % d == 0:
ans += d
n //= d
d += 1
return ans + (n if n > 1 else 0)C++
class Solution {
public:
int minSteps(int n) {
int ans = 0;
for (int d = 2; d * d <= n; ++d) {
while (n % d == 0) { ans += d; n /= d; }
}
return ans + (n > 1 ? n : 0);
}
};Java
import java.util.*;
class Solution {
public int minSteps(int n) {
int ans = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) { ans += d; n /= d; }
}
return ans + (n > 1 ? n : 0);
}
}复杂度
时间
O(√n)
d 只需试到 √n，最多 √n 次
空间
O(1)
只用 ans、d、n 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 只有两个键的键盘 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么质因数分解一定最优，而不是别的拆法？+
把长度扩大 a×b 倍，分两步要 a+b 步；而对任意 a,b ≥ 2 都有 a+b ≤ a×b。所以只要某个因子还是合数（能写成 a×b），就拆开它，总步数不增。一直拆到不能再拆，剩下的全是质数，此时和最小。
也能用动态规划做吗？复杂度如何？+
可以:dp[i] = 凑出 i 个 A 的最少步数，枚举 i 的每个因子 j，dp[i] = min(dp[j] + i/j)。这是 O(n√n) 或 O(n²)，比质因数分解的 O(√n) 慢，但更通用、更直观，面试两种都值得会。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 只有两个键的键盘 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。