650. 2 Keys Keyboard复制粘贴的次数

［抄题］：

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.

Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

以为是dp数组，结果只需要稍微除一下就行了

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

totalSteps += singleSteps; 需要一直相加来积累一次性能走的最长步数，否则要走很多次

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

需要while循环一直相加的时候要注意点

［复杂度］：Time complexity: O(n) Space complexity: O(1)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

[潜台词] ：

class Solution {
    public int minSteps(int n) {
        //initialization: totalSteps = 0
        int totalSteps = 0;
        
        //for loop for n
        for (int singleSteps = 2; singleSteps <= n; singleSteps++) {
            while (n % singleSteps == 0) {
                totalSteps += singleSteps;
                n /= singleSteps;
            }
        }
        
        return totalSteps;
        
        /*
        singleSteps 2  2
        totalSteps  2  4
        n           2  1
        */
    }
}

View Code