题目链接
英文链接:https://leetcode.com/problems/2-keys-keyboard/
中文链接:https://leetcode-cn.com/problems/2-keys-keyboard/
题目详述
最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作:
- Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
- Paste (粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数,在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。
示例 1:
1 | 输入: 3 |
说明:
n 的取值范围是 [1, 1000] 。
题目详解
- 花费 2 步(Copy All, Paste)变成 2 倍,花费 3 步(Copy All, Paste,Paste)变成 3 倍,……,依此类推。
- 令
f(n)
代表得到 n 个 ‘A’ 需要的操作次数。 - 如果
n % 2 == 0
,那么f(n) = f(n / 2) + 2
。 - 如果
n % 3 == 0
,那么f(n) = f(n / 3) + 3
。 2 * 2 = 2 + 2
,2 * 3 > 2 + 3
,4 * 4 > 4 + 4
,……。对于正整数p
和q
,当p > 1, q > 1
时,可以得到p + q <= pq
,这是因为(p - 1)(q - 1) >= 1
,所以把pq
分解成p + q
会使最终结果变小。应该尽可能地把数进行分解,分解到不能再分,可以达到最少的操作次数。- 本题就转化为了求数
n
的所有质因子之和。
1 | public class LeetCode_00650 { |