※ 引述《JerryChungYC (JerryChung)》之铭言：
: 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
: 不过直接进行加总好像更好
: 所以这题的原理是啥
思路:
一开始copy的值是1 假设(目标n - 现在长度) % 现在长度 == 0
代表我们能将copy值换成现在长度
因为现在长度>现在copy值 所以能更快将字串长度变成n
而且(目标n - 现在长度) % 现在长度 == 0
所以现在长度能刚好走完剩余距离 不会超过n
所以符合假设就将现在copy值变成现在长度
也就是说 重新copy 然后贴上
假如不符合假设 就现在copy值继续贴上
Python Code:
class Solution:
def minSteps(self, n: int) -> int:
result = 0
cur_copy = 1
cur_len = 1
n -= 1
while n > 0:
if n % cur_len == 0:
cur_copy = cur_len
n -= cur_copy
cur_len += cur_len
result += 2
else:
cur_len += cur_copy
n -= cur_copy
result += 1
return result
感觉不像正确做法 但时间空间都满漂亮的