algorithm - 使用击键 A、Ctrl+A、Ctrl+C 和 Ctrl+V 的最大字符数

Question

这是来自谷歌的面试题。我无法自己解决。有人可以解释一下吗？

编写一个程序来打印击键序列，使其生成最大数量的字符“A”。您只能使用 4 个键:A、Ctrl+A、Ctrl+C 和 Ctrl+V。只允许 N 次击键。所有 Ctrl+ 字符都被视为一次击键，因此 Ctrl+A 是一次击键。

例如序列A, Ctrl+A, Ctrl+C, Ctrl+V 在 4 次击键中生成两个 A。

• Ctrl+A 是全选
• Ctrl+C是复制
• Ctrl+V 是粘贴

我做了一些数学。对于任何 N，使用 x 个 A's，一个 Ctrl+A，一个 Ctrl+C 和 y < kbd>Ctrl+V，我们可以生成最大((N-1)/2)²个A。对于一些 N > M，最好使用尽可能多的 Ctrl+A，Ctrl+C和 Ctrl+V 序列，因为它将 A 的数量加倍。

序列 Ctrl+A, Ctrl+V, Ctrl+ C 不会覆盖现有的选择。它将复制的选择附加到选定的一个。

Answer 1

有一个动态规划解决方案。我们开始知道 0 键可以使我们成为 0 A。然后我们遍历i最多 n ，做两件事:按一次 A 并按全选 + 复制然后粘贴 j次(实际上是下面的 j-i-1；注意这里的技巧:内容仍然在剪贴板中，所以我们可以多次粘贴它而不必每次都复制)。我们只需要考虑最多 4 次连续粘贴，因为选择、复制、粘贴 x 5 相当于选择、复制、粘贴、选择、复制、粘贴，后者更好，因为它在剪贴板中留下了更多内容。一旦我们到达 n ，我们得到了想要的结果。

复杂度可能看起来是 O(N)，但由于数字以指数速率增长，由于乘以大数的复杂性，它实际上是 O(N²)。下面是一个 Python 实现。计算 N=50,000 大约需要 0.5 秒。

def max_chars(n):
  dp = [0] * (n+1)
  for i in xrange(n):
    dp[i+1] = max(dp[i+1], dp[i]+1) # press a
    for j in xrange(i+3, min(i+7, n+1)):
      dp[j] = max(dp[j], dp[i]*(j-i-1)) # press select all, copy, paste x (j-i-1)
  return dp[n]

在代码中，j表示在我们新的按键序列之后按下的按键总数。我们已经有了 i此阶段的按键，以及 2 个新按键进入全选和复制。因此我们正在点击粘贴 j-i-2次。由于粘贴添加到 dp[i] 的现有序列中A的，我们需要添加 1制作 j-i-1 .这解释了 j-i-1在倒数第二行。

这是一些结果(n => A 的数量):

• 7 => 9
• 8 => 12
• 9 => 16
• 10 => 20
• 100 => 1391569403904
• 1,000 => 3268160001953743683783272702066311903448533894049486008426303248121757146615064636953144900245174442911064952028008546304
• 50,000 => a very large number!

我同意@SB 的观点，您应该始终陈述您的假设:我的假设是您不需要粘贴两次来使字符数加倍。这得到了 7 的答案，所以除非我的解决方案是错误的，否则假设一定是正确的。

如果有人想知道为什么我不检查 Ctrl+A, Ctrl+C , A, Ctrl+V: 最终结果总是和A, Ctrl+A, Ctrl+C, Ctrl+V 我确实考虑过。