https://leetcode.com/problems/2-keys-keyboard
650. 2 Keys Keyboard
一开始有一个 'A' 在记事本中，有两种操作方式
复制全部：将目前所有文字复制
贴上 ：将复制的文字贴上
给一个数字 n ，求获得 n 个 'A' 最少要进行的步骤次数
Example 1:
Input: n = 3
Output: 3
Explanation: 一开始有一个 'A'
Step 1, 复制
Step 2, 贴上 得到 'AA'
Step 3, 贴上 得到 'AAA'
Example 2:
Input: n = 1
Output: 0
Constraints:
1 <= n <= 1000
思路：
知道在做什么但没有想法 所以先从小数字实际算一次找规律
结果发现似乎是质因子加总的答案 于是就直接go
如 12 = 2 * 2 * 3 , 2 + 2 + 3 = 7 答案就是 7
如 8 = 2 * 2 * 2 , 2 + 2 + 2 = 6 答案 6 (cpcpcp) or (cpcppp)
Python Code:
class Solution:
def minSteps(self, n: int) -> int:
ans = 0 # []
while n % 2 == 0:
ans += 2 # append
n //= 2
for i in range(3, int(n**0.5) + 1, 2):
while n % i == 0:
ans += i # append
n //= i
if n > 2:
ans += n # append
return ans # sum()
原本用 list 存质因子 最后再用 sum
不过直接进行加总好像更好
所以这题的原理是啥