[LeetCode] 650. 2 Keys Keyboard 两键的键盘

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 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:html

  1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
  2. 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'.java

Example 1:python

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'.

Note:数组

  1. The n will be in the range [1, 1000].

初始化一个记事本,里面只含有一个字符'A',每次能够执行一个操做,共有两个操做:拷贝所有,粘贴上一次的拷贝。给一个数组n,求要达到n个字符,最少须要操做几步。post

技巧是循环找出n的分解因子i,这个因子就是能够看成模块的个数,再算出模块的长度n/i,调用递归,加上模块的个数i来更新结果resthis

解法1:递归。url

解法2:DPcode

Java:orm

class Solution {
    public int minSteps(int n) {
        int[] dp = new int[n+1];

        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = i-1; j > 1; j--) {
                if (i % j == 0) {
                    dp[i] = dp[j] + (i/j);
                    break;
                }
                
            }
        }
        return dp[n];
    }
}  

Python:htm

class Solution(object):
    def minSteps(self, n):
        """
        :type n: int
        :rtype: int
        """
        result = 0
        p = 2
        # the answer is the sum of prime factors
        while p**2 <= n:
            while n % p == 0:
                result += p
                n //= p
            p += 1
        if n > 1:
            result += n
        return result  

C++:

class Solution {
public:
    int minSteps(int n) {
        if (n == 1) return 0;
        int res = n;
        for (int i = n - 1; i > 1; --i) {
            if (n % i == 0) {
                res = min(res, minSteps(n / i) + i);
            }
        }
        return res;
    }
};

C++:

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1, 0);
        for (int i = 2; i <= n; ++i) {
            dp[i] = i;
            for (int j = i - 1; j > 1; --j) {
                if (i % j == 0) {
                    dp[i] = min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
};

C++:

class Solution {
public:
    int minSteps(int n) {
        int res = 0;
        for (int i = 2; i <= n; ++i) {
            while (n % i == 0) {
                res += i;
                n /= i;
            }
        }
        return res;
    }
};

  

  

  

 

相似题目:

[LeetCode] 651. 4 Keys Keyboard 四键的键盘

 

All LeetCode Questions List 题目汇总