※ 引述《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
感覺不像正確做法 但時間空間都滿漂亮的