LC 650. 只有两个键的键盘
题目描述
这是 LeetCode 上的 650. 只有两个键的键盘 ，难度为 中等。
最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：
Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。
示例 1：1
2
3
4
5
6
7
8
9输入：3
输出：3
解释：
最初, 只有一个字符 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 'AA'。
第 3 步, 使用 Paste 操作来获得 'AAA'。
示例 2：1
2
3输入：n = 1
输出：0
提示：
- $1 <= n <= 1000$
动态规划
定义 $f[i][j]$ 为经过最后一次操作后，当前记事本上有 $i$ 个字符，粘贴板上有 $j$ 个字符的最小操作次数。
由于我们粘贴板的字符必然是经过 Copy All 操作而来，因此对于一个合法的 $f[i][j]$ 而言，必然有 $j <= i$。
不失一般性地考虑 $f[i][j]$ 该如何转移：
最后一次操作是
Paste操作：此时粘贴板的字符数量不会发生变化，即有 $f[i][j] = f[i - j][j] + 1$；最后一次操作是
Copy All操作：那么此时的粘贴板的字符数与记事本上的字符数相等（满足 $i = j$），此时的 $f[i][j] = \min(f[i][x] + 1), 0 \leq x < i$。
我们发现最后一个合法的 $f[i][j]$（满足 $i = j$）依赖与前面 $f[i][j]$（满足 $j < i$）。
因此实现上，我们可以使用一个变量 $min$ 保存前面转移的最小值，用来更新最后的 $f[i][j]$。
再进一步，我们发现如果 $f[i][j]$ 的最后一次操作是由 Paste 而来，原来粘贴板的字符数不会超过 $i / 2$，因此在转移 $f[i][j]$（满足 $j < i$）时，其实只需要枚举 $[0, i/2]$ 即可。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
int INF = 0x3f3f3f3f;
public int minSteps(int n) {
int[][] f = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
f[i][j] = INF;
}
}
f[1][0] = 0; f[1][1] = 1;
for (int i = 2; i <= n; i++) {
int min = INF;
for (int j = 0; j <= i / 2; j++) {
f[i][j] = f[i - j][j] + 1;
min = Math.min(min, f[i][j]);
}
f[i][i] = min + 1;
}
int ans = INF;
for (int i = 0; i <= n; i++) ans = Math.min(ans, f[n][i]);
return ans;
}
}
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n^2)$
数学
如果我们将「$1$ 次 Copy All + $x$ 次 Paste」看做一次“动作”的话。
那么 一次“动作”所产生的效果就是将原来的字符串变为原来的 $x + 1$ 倍。
最终的最小操作次数方案可以等价以下操作流程：
- 起始对长度为 $1$ 的记事本字符进行 $1$ 次
Copy All+ $k_1 - 1$ 次Paste操作（消耗次数为 $k_1$，得到长度为 $k_1$ 的记事本长度）； - 对长度为为 $k_1$ 的记事本字符进行 $1$ 次
Copy All+ $k_2 - 1$ 次Paste操作（消耗次数为 $k_1 + k_2$，得到长度为 $k_1 * k_2$ 的记事本长度）
…
最终经过 $k$ 次“动作”之后，得到长度为 $n$ 的记事本长度，即有：
问题转化为：如何对 $n$ 进行拆分，可以使得 $k_1 + k_2 + … + k_x$ 最小。
对于任意一个 $k_i$（合数）而言，根据定理 $a * b >= a + b$ 可知进一步的拆分必然不会导致结果变差。
因此，我们只需要使用「试除法」对 $n$ 执行分解质因数操作，累加所有的操作次数，即可得到答案。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public int minSteps(int n) {
int ans = 0;
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
ans += i;
n /= i;
}
}
if (n != 1) ans += n;
return ans;
}
}
- 时间复杂度：$O(\sqrt{n})$
- 空间复杂度：$O(1)$
打表
我们发现，对于某个 $minSteps(i)$ 而言为定值，且数据范围只有 $1000$，因此考虑使用打表来做。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
static int N = 1010;
static int[] g = new int[N];
static {
for (int k = 2; k < N; k++) {
int cnt = 0, n = k;
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
cnt += i;
n /= i;
}
}
if (n != 1) cnt += n;
g[k] = cnt;
}
// System.out.println(Arrays.toString(g)); // 输出打表结果
}
public int minSteps(int n) {
return g[n];
}
}
1 | |
- 时间复杂度：将打表逻辑配合
static交给 OJ 执行，复杂度为 $O(C * \sqrt{C})$，$C$ 为常数，固定为 $1010$；将打表逻辑放到本地执行，复杂度为 $O(1)$ - 空间复杂度：$O(C)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.650 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
