650. 只有两个键的键盘——【Leetcode每日一题】

淩亂°似流年 2024-03-26 21:12 58阅读 0赞

### 650. 只有两个键的键盘 ###

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

*  `Copy All`（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
 *  `Paste`（粘贴）：粘贴 **上一次** 复制的字符。

给你一个数字 `n` ，你需要使用最少的操作次数，在记事本上输出 恰好 `n` 个 `'A'`。返回能够打印出 `n` 个 `'A'` 的最少操作次数。

##### 示例 1： #####

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

##### 示例 2： #####

> 输入：n = 1  
> 输出：0

##### 提示： #####

*  1 <= n <= 1000

#### 思路：(动态规划) ####

1.  动态规划问题最重要的是先**确定一共有哪些状态**；
2.  然后分析每种状态的关系，从而确定 **状态转移方程**。

**第一步：确定所有的状态：**

随意看其中的一步，就两种状态，不是先复制记事本字符的全部再粘贴，就是粘贴已经在粘贴板上的：

*  1、**复制再粘贴**
 *  2、**粘贴**

**第二步：分析每种状态的关系，确定状态转移方程：**

*  1、**复制再粘贴**：只有当前**记事本上的字符数**，是目标数的**因子**，即能**整除目标数**，此时才能复制完，再粘贴，进而能得到目标数；
    
     *  复制一次+粘贴一次，此时的操作数总数+2，即**总操作数**为:  a n s + = 2 ans += 2 ans\+=2
     *  粘贴板上字符的长度为复制前记事本上的字符数，即**粘贴板上字符数**为： p a s t e = n u m paste = num paste=num
     *  粘贴后记事本上的字符数要加上粘贴的字符数，即**完成一次复制粘贴记事本上的字符数**为： n u m + = p a s t e num += paste num\+=paste
 *  2、**粘贴**，此时**记事本上的字符数**不能**整除\*\*\*\*目标数**，则复制当前记事本上的长度一定到达不了目标数，则 **只能粘贴已经在粘贴板上的字符**：
    
     *  只粘贴一次，总操作数+1，即**总操作数**为:  a n s + = 1 ans += 1 ans\+=1
     *  粘贴后记事本上的字符数要加上粘贴的字符数，即**完成一次粘贴记事本上的字符数**为： n u m + = p a s t e num += paste num\+=paste

#### 代码：(Java) ####

public class MInSteps {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int n = 3;
    		System.out.println(minSteps(n));
    	}
    	public static int minSteps(int n) {
        
    		if(n == 1) {
        
    			return 0;
    		}
    		
    		int num = 2;//至少两个字符,从两个字符开始
    		int ans = 2;//总操作数,两个字符时，已经复制粘贴各一次，且此时粘贴板上有一个字符了
    		int paste = 1; //复制板上的字符数
    		
    		while(num < n) {
        
    			if(n % num == 0) {
        
    				ans += 2; //复制 + 粘贴
    				paste = num;
    			}else {
        
    				ans += 1; //粘贴
    			}
    			
    			num += paste;//当前数+粘贴板上字符数
    		}
    		
    		return ans;
        }
    }

##### 运行结果： #####

![在这里插入图片描述][44be558282374d36934830e1b56d74b0.png]  
力扣提交：  
![在这里插入图片描述][770a07c616e1464d9ff51624c8f5d10a.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，最坏的情况n是质数，一次只能粘贴一次，要粘贴n次。
 *  **空间复杂度**： O ( 1 ) O(1) O(1)，只需要常数级别的空间。

##### 注：仅供学习参考， 如有不足，欢迎指正！ #####

题目来源：[力扣。][Link 1]

[44be558282374d36934830e1b56d74b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/38f6168826004ed8b329ccea079bbd51.png
[770a07c616e1464d9ff51624c8f5d10a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/05a5cf155ad5444684b0bb890969dd32.png
[Link 1]: https://leetcode.cn/problems/2-keys-keyboard/description/