→ JerryChungYC: 又忘記問了 所以有leetcode群嗎 窩不知道跑2是誰:( 08/19 12:17
推 dont: 大師 08/19 13:48
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
不過直接進行加總好像更好
所以這題的原理是啥
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.52.67 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724040928.A.DD2.html