Medium

题目描述

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

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

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

示例 1：

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

示例 2：

输入：n = 1
输出：0

提示：

  • 1 <= n <= 1000

解题思路

解题思路

这道题的核心在于找到最优的复制和粘贴策略。我们来分析一下操作模式：

  1. 基本观察：要得到 n 个 ‘A’，我们需要将初始的 1 个 ‘A’ 扩展到 n 个。每次复制操作会记住当前的字符数，后续的粘贴操作会增加相同数量的字符。

  2. 操作分析：假设我们有 k 个 ‘A’，执行一次复制 + m 次粘贴，总共需要 1+m 次操作，最终得到 k*(1+m) 个 ‘A’。

  3. 数学本质：这实际上是一个质因数分解问题。要得到 n 个 ‘A’，我们需要将 n 分解为若干因子的乘积，每个因子对应一轮"复制+粘贴"操作。

  4. 最优策略：将 n 分解为质因数，每个质因数 p 需要 p 次操作（1次复制 + p-1次粘贴）。因此答案就是所有质因数的和。

解法对比：

  • 质因数分解法（推荐）：时间复杂度 O(√n)，空间复杂度 O(1)
  • 动态规划法：时间复杂度 O(n²)，空间复杂度 O(n)

质因数分解法更高效，因为它直接利用了问题的数学本质。

代码实现

class Solution {
public:
    int minSteps(int n) {
        if (n == 1) return 0;
        
        int result = 0;
        
        // 找到所有质因数并累加
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                result += i;
                n /= i;
            }
        }
        
        // 如果 n > 1，说明还有一个大于 sqrt(n) 的质因数
        if (n > 1) {
            result += n;
        }
        
        return result;
    }
};

class Solution:
    def minSteps(self, n: int) -> int:
        if n == 1:
            return 0
        
        result = 0
        
        # 找到所有质因数并累加
        i = 2
        while i * i <= n:
            while n % i == 0:
                result += i
                n //= i
            i += 1
        
        # 如果 n > 1，说明还有一个大于 sqrt(n) 的质因数
        if n > 1:
            result += n
        
        return result

public class Solution {
    public int MinSteps(int n) {
        if (n == 1) return 0;
        
        int result = 0;
        
        // 找到所有质因数并累加
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                result += i;
                n /= i;
            }
        }
        
        // 如果 n > 1，说明还有一个大于 sqrt(n) 的质因数
        if (n > 1) {
            result += n;
        }
        
        return result;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var minSteps = function(n) {
    if (n === 1) return 0;
    
    let steps = 0;
    let factor = 2;
    
    while (factor <= n) {
        while (n % factor === 0) {
            steps += factor;
            n /= factor;
        }
        factor++;
    }
    
    return steps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
质因数分解O(√n)O(1)
动态规划O(n²)O(n)

推荐解法：质因数分解法，时间和空间效率都更优秀。

相关题目