LeetCode 650. 两个键的键盘
题目描述
题意分析
记事本初始有一个 A，只能复制全部内容或粘贴剪贴板内容，求得到恰好 n 个 A 的最少操作数。
解法：质因数分解求和
核心思路
[!blue]
将有效操作按“复制一次，随后粘贴若干次”分段。 连续复制而不粘贴、或最后复制却不再使用，都不会增加字符数，可以从最优方案中去掉。因此每段都至少粘贴一次：从 $x$ 个 A 复制一次，再粘贴 $p-1$ 次，就得到 $xp$ 个，共花费 $p$ 次操作，其中 $p\ge2$。从一个 A 出发，所有段的乘数之积必须恰好为 $n$，总代价则是这些乘数之和。反过来，任何这样的因数分解也都能按对应的复制、粘贴段实现，所以问题等价于寻找乘积为 $n$、总和最小的一组因子。
若某个因子是合数 $ab$，其中 $a,b\ge2$，就能改成先乘 $a$、再乘 $b$ 两段。字符总数不变，代价从 $ab$ 变成 $a+b$；因为 $ab-a-b=(a-1)(b-1)-1\ge0$，拆分不会更差。反复拆到全部为质数，得到的就是 $n$ 的质因数及其重数。任意方案的代价都不小于这个质因数和，而该和又能实际达到，因此它就是最优答案。
代码从 2 开始试除剩余的
n。每次整除都累加因子并缩小n，同一因子可能贡献多次；较小质因子已被除尽，之后真正能整除的因子也必然是质数。若试除到d * d > n后仍有n > 1，剩余值不可能再是合数，否则它还应有一个未被处理的小因子，因此将它整体加入答案。
n = 1时已经有目标字符数，试除循环与最后的补加分支都不会执行，答案自然为 0。合数拆分时等号可能成立，所以质因子方案给出最优次数，但不一定是唯一的操作安排。
解题步骤
- 从因子二开始试除。
- 同一因子能整除就反复除，每次累加该因子。
- 试除结束后，剩余值大于一则作为最后一个质因子加入。
- 返回质因子之和。
代码实现
class Solution {
public int minSteps(int n) {
int answer = 0;
for (int d = 2; d * d <= n; d++) {
// 同一质因子可能出现多次，每一份都需要累加。
while (n % d == 0) {
answer += d;
n /= d;
}
}
// 试除结束后的剩余质因子仍需计入。
if (n > 1) {
answer += n;
}
return answer;
}
}
func minSteps(n int) int {
answer := 0
for d := 2; d*d <= n; d++ {
// 同一质因子可能出现多次，每一份都需要累加。
for n%d == 0 {
answer += d
n /= d
}
}
// 试除结束后的剩余质因子仍需计入。
if n > 1 {
answer += n
}
return answer
}
复杂度分析
- 时间复杂度：$O(\sqrt n)$ 上界，以原输入 n 计。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 每个因子的代价包含一次复制。
- 重复质因子按出现次数逐个计入。
- 剩余大于一的值是质数，不应遗漏。
易错点总结
[!yellow]
- 内层只除一次：会漏掉同一质因子重复出现的贡献。
- 只统计因子个数：代价是因子值之和。
- 从因子一开始：除以一不会缩小剩余值。
- 只统计粘贴，不统计复制：每段操作少算一次。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 153. 整数的质因数分解 | 简单 | 最少复制粘贴操作数等于n的质因数之和，可复用试除分解并累计重数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！