650. 只有两个键的键盘

1. 题目

最初在一个记事本上只有一个字符 ‘A‘。你每次可以对这个记事本进行两种操作:

Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数,在记事本中打印出恰好 n 个 ‘A‘。输出能够打印出 n 个 ‘A‘ 的最少操作次数。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/2-keys-keyboard
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 示例

输入: 3
输出: 3
解释:
最初, 我们只有一个字符 ‘A‘。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 ‘AA‘。
第 3 步, 我们使用 Paste 操作来获得 ‘AAA‘。

3. 题解

很明显,这是递归题。

尝试着写几个数观察最后复制的数:

输入3,最后复制1;

输入5,最后复制1;

输入12,最后复制6;

输入24,最后复制12;

观察发现,其实求的就是一个数的最大公约数。

4. 实现

 1 public class MinStepsA {
 2     public int minSteps(int n) {
 3         if(n == 1) {
 4             return 0;
 5         }
 6         int temp = maxGYS(n);
 7         int sum = 0;
 8         while(temp != 1) {
 9             sum += n / temp;
10             n = temp;
11             temp = maxGYS(n);
12         }
13         return sum + n;
14     }
15 
16     public static int maxGYS(int num) {
17         if(num == 1) {
18             return num;
19         }
20         int temp = num - 1;
21         while (temp > 0) {
22             if(num % temp == 0) break;
23             temp--;
24         }
25         return temp;
26     }
27 
28     public static void main(String[] args) {
29         int num = 1;
30         System.out.println(new MinStepsA().minSteps(num));
31     }
32 }

5. 结语

  努力去爱周围的每一个人,付出,不一定有收获,但是不付出就一定没有收获! 给街头卖艺的人零钱,不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)!

  如果客官喜欢小生的园子,记得关注小生哟,小生会持续更新(#^.^#)(#^.^#)。

 

650. 只有两个键的键盘

上一篇:Git代码管理


下一篇:LVM与磁盘配额