[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:

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

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

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

难度

Medium

方法

通过length记录已打印的字符长度，copy_length记录剪切板中字符长度。如果n - length % (length + copy_length) == 0，则表示可以将剪切板中字符粘贴，然后复制所有字符后再粘贴，能够打出n个字符；否则直接粘贴copy_length长度的字符，循环处理即可。

代码

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

        copy_length = 1
        steps = 1
        length = 1
        while n - length > copy_length:
            if (n - length - copy_length) % (length + copy_length) == 0:
                length += copy_length
                copy_length = length
                steps += 2
            else:
                steps += 1
                length += copy_length
        return steps + 1


assert Solution().minSteps(1) == 0
assert Solution().minSteps(3) == 3
assert Solution().minSteps(5) == 5
assert Solution().minSteps(100) == 14