Leetcode-650 —— 2 Keys Keyboard

题目描述

剪切板中初始状态下只有一个字母 ‘A’，只允许复制全部和粘贴全部操作，使用最小的操作步骤得到 n 个字符 ‘A’。

测试用例

根据题意，n 的取值区间为 [1, 1000]

// Case 0: n 等于 1

// Case 1: n 是偶数

// Case 2: n 是奇数

// Case 3: 你是质数

分析

1. 如果 n 是偶数，f(n) = f(n/2) + 2 复制一次，粘贴一次

2. 如果 n 是奇数，

   • 若 n 是质数，则 f(n) = n
   • 零 m * x == n，假设 x >= m 则 f(n) = m + f(x)，复制一次，粘贴 m - 1次。

代码

class Solution:
    def minSteps(self, n: int) -> int:
        if n == 1: #1
            return 0
        
        def calc(n):
            if n <= 3:
                return n
            if n % 2 == 0:
                return calc(n//2) + 2
            else:
                r = int(math.sqrt(n))
                m = 0
                for i in range(2, r+1):
                    if n % i == 0:
                        m = n // i
                        break   #2
                if m > 0:
                    return n // m + calc(m)
                else:
                    return n
                
        return calc(n)

注意两点：

• #1考虑 n == 1 的基本情况

• #2 找最大因数时找到之后一定要跳出循环