leetcode_650_隻有兩個鍵的鍵盤

最初在一個記事本上隻有一個字元 ‘A’。你每次可以對這個記事本進行兩種操作：

Copy All (複制全部) : 你可以複制這個記事本中的所有字元(部分的複制是不允許的)。
Paste (粘貼) : 你可以粘貼你上一次複制的字元。
給定一個數字 n 。你需要使用最少的操作次數，在記事本中列印出恰好 n 個 'A'。輸出能夠列印出 n 個 'A' 的最少操作次數。
           

示例 1:

輸入: 3

輸出: 3

解釋:

最初, 我們隻有一個字元 ‘A’。

第 1 步, 我們使用 Copy All 操作。

第 2 步, 我們使用 Paste 操作來獲得 ‘AA’。

第 3 步, 我們使用 Paste 操作來獲得 ‘AAA’。

注意： n 的取值範圍是 [1, 1000] 。

方法一：如果 n 為素數，那麼 op = n,

否則，求 乘積為 n 的所有素數 ，如 n = 15 , 3*5 =15, op = 3 + 5 ,問題轉化為求素數。

class Solution(object):
    def minSteps(self, n): 
        if n ==1:
            return 0

        return self.get_all_divprimers(n)
        

    def get_all_divprimers(self, n):
        res, i = [],2
        while i <= int(pow(n,0.5)):
            if n % i == 0:
                res.append(i)
                n , i = n/i, 2
            else:
                i+=1
        res.append(n)
        print(sum(res))
        return sum(res)

           

**分析:想要減少操作數，我們就盡可能的一次複制較大長度的，但是注意，複制的這個長度值一旦增加，就無法變小，注意最後複制粘貼的構成的總長度恰好是n。是以，我們首先判斷n 是不是質數，如果是，隻能一個一個字元粘貼了，op 數 就是 n 。 如果不是，說明可以通過一個相對大的長度複制粘貼。

如 n = 9, 那麼，9 可由 3粘貼三次得到。

class Solution(object):

    def bigchu(self,s):
        for i in range(2,int(s/2)):
            
            if not s%i:
                return i
        return 0
    def minSteps(self,n):
        if n == 1:
            return 0
        sum = 0
        chu = self.bigchu(n)
        while n>4 and chu :
            sum+=chu
            n /=chu
            chu = self.bigchu(n)
        return sum+n