Leetcode-650 —— 2 Keys Keyboard

题目描述

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

测试用例

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

1
2
3
4
5
6
7
// 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次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 找最大因数时找到之后一定要跳出循环

本文标题:Leetcode-650 —— 2 Keys Keyboard

文章作者:Syncher

发布时间:2019年10月18日 - 19:10

最后更新:2019年10月18日 - 19:10

原始链接:https://0x400.com/2019-10-18-lc-650-2-keys-keyboard.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。