leetcode 650 隻有兩個鍵的鍵盤

傳送門

####題目介紹

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

Copy All（複制全部）：複制這個記事本中的所有字元（不允許僅複制部分字元）。

Paste（粘貼）：粘貼 上一次 複制的字元。

給你一個數字 n ，你需要使用最少的操作次數，在記事本上輸出 恰好 n 個 ‘A’ 。傳回能夠列印出 n 個 ‘A’ 的最少操作次數。

####題目樣例

示例 1：

輸入：3
輸出：3
解釋：
最初, 隻有一個字元 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作來獲得 'AA'。
第 3 步, 使用 Paste 操作來獲得 'AAA'。
示例 2：

輸入：n = 1
輸出：0
 

提示：
1 <= n <= 1000
           

####題目解析

通過讀題我們知道一個長度為n的字元串必然是由上一次操作之前的字元串和剪切闆拼接的字元串組成的。

這裡我們進行未知量的假設

假設

S k S_k Sk​為第k次操作得到的字元串長度

P a s t e k Paste_k Pastek​為第k次操作複制的字元長度

是以，對于一個長度為n的字元串假設最小操作次數為k

得，

n n n = P a s t e k + S i − 1 Paste_k+S_{i-1} Pastek​+Si−1​

由題意知，

∃ ! j ∈ [ 0 , i − 1 ] \exists!j\in[0,i-1] ∃!j∈[0,i−1],有 S j = P a s t e i − 1 S_j=Paste_{i-1} Sj​=Pastei−1​

則有

P a s t e k = { S i − 1 , j = = i − 1 P a s t e j + 1 , e l s e Paste_k =\begin{cases} S_{i-1} & ,j == i-1\\\\ Paste_{j+1} & ,else \end{cases} Pastek​=⎩⎪⎨⎪⎧​Si−1​Pastej+1​​,j==i−1,else​

N N N

= P a s t e k + S i − 1 =Paste_k+S_{i-1} =Pastek​+Si−1​

= ∑ i = j + 1 k P a s t e j + 1 + S j = \sum_{i = j+1}^{k} Paste_{j+1}+S_j =∑i=j+1k​Pastej+1​+Sj​

= ( k − j ) ∗ S j =(k-j)*S_j =(k−j)∗Sj​

= ( n / S j ) ∗ S j =(n/S_j)*S_j =(n/Sj​)∗Sj​

這裡我們發現 S j S_j Sj​實際是n的因子

最終我們就得出了次數的關系式

T i m e n = ( n / S j ) + S j Time_n = (n/S_j)+S_j Timen​=(n/Sj​)+Sj​

顯然最大因子的次數是比其他因子少的

因為最大因子與數字的倍數是最小的

比如 t i m e 100 time_{100} time100​的兩個因子10和20

根據公式

t i m e 100 = 100 / 20 + t i m e 20 = 5 + 2 + t i m e 10 time_{100} = 100/20+ time_{20} = 5+2+time_{10} time100​=100/20+time20​=5+2+time10​

t i m e 100 = 100 / 10 + t i m e 10 = 10 + t i m e 10 time_{100} = 100/10+time_{10} = 10+time_{10} time100​=100/10+time10​=10+time10​

可以看出差距極大

算法實作

1.DFS版

class Solution {
    private:
public:
    int minSteps(int n) {
        if(n == 1)
            return 0;
        int &&mid = n>>1;
        int i = mid;
        while(i>1&&n%i)
            i--;
        return n/i+minSteps(i);
    }
    Solution(){
        
    }
};
           

2.DFS版打表

class Solution {
    private:
    int num[257];//這裡隻對于重複率高的進行打表，實際257~512那層隻進行了一次運算重複率降低是以這裡定義的是512
public:
    int minSteps(int n) {
        if(n<257&&num[n]+1)
            return num[n];
        int &&mid = n>>1;
        int i = mid;
        while(i>1&&n%i)
            i--;
        int last;
        if(i<257)
            num[i] = num[i]==-1?minSteps(i):num[i];
        last = i<257?num[i]:minSteps(i);
        if(n<257){
            num[n] = num[n]==-1?n/i+num[i]:num[n];
            return num[n];
        }
        return n/i+last;
    }
    Solution(){
        memset(num,-1,257*sizeof(int));
        num[0] = num[1] = 0;
        num[2] = 2;
        
    }
};
           

3.BFS版打表

bfs打表這裡空間換時間也使用了O(n)的打表預處理時間，實際上降低了平均損耗，但時間上實際是比dfs多了20ms的損耗，也證明了命中率相對較低

class Solution {
    private:
    int num[1010];
public:
    int minSteps(int n) {
        
        return num[n];
    }
    Solution(){
        memset(num,0,1010*sizeof(int));
        num[0] = num[1] = 0;
        num[2] = 2;
        for(int i = 3;i<1010;i++){
            int &&mid = i>>1;
            int j = mid;
            while(j>1&&i%j)
                j--;
            num[i] = num[j]+i/j;
        }
    }
};