使用按键A，Ctrl + A键，按Ctrl + C和Ctrl + V的最大字符数 [英] Maximum number of characters using keystrokes A, Ctrl+A, Ctrl+C and Ctrl+V

问题描述

这是从谷歌的面试问题。我不能由我自己来解决它。有人可以提供一些线索？

This is an interview question from google. I am not able to solve it by myself. Can somebody shed some light?

写一个程序，打印按键，使得它产生的字符'A的最大数量的顺序。你被允许只使用4个按键：<大骨节病> A ，<大骨节病>控制 + <大骨节病> A ，<大骨节病>控制 + <大骨节病> C < /骨节病>和<大骨节病>控制 + <大骨节病> V 。 n只有按键是允许的。所有<大骨节病>控制 +字符被视为一个按键，因此<大骨节病>控制 + <大骨节病> A 是一个击键。

Write a program to print the sequence of keystrokes such that it generates the maximum number of character 'A's. You are allowed to use only 4 keys: A, Ctrl+A, Ctrl+C and Ctrl+V. Only N keystrokes are allowed. All Ctrl+ characters are considered as one keystroke, so Ctrl+A is one keystroke.

例如，序列<大骨节病> A ，<大骨节病>控制 + <大骨节病> A ，<大骨节病>控制 + <大骨节病> C ，<大骨节病>控制 + <大骨节病> V 生成两个A的4个按键。

For example, the sequence A, Ctrl+A, Ctrl+C, Ctrl+V generates two A's in 4 keystrokes.

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

我做了一些数学。对于任何N，用A的第X号，一个<大骨节病>控制 + <大骨节病> A ，一个<大骨节病>控制 + <大骨节病> C 和Y <大骨节病>控制 + <大骨节病> V ，我们可以生成最大（（N-1）/ 2） ² A的数量。对于一些N> M，最好是使用尽可能多的<大骨节病>控制 + <大骨节病> A 的<大骨节病>控制 + <大骨节病> C 和<大骨节病>控制 + <大骨节病> V 序列，因为它双打的数量。

I did some mathematics. For any N, using x numbers of A's , one Ctrl+A, one Ctrl+C and y Ctrl+V, we can generate max ((N-1)/2)² number of A's. For some N > M, it is better to use as many Ctrl+A's, Ctrl+C and Ctrl+V sequences as it doubles the number of A's.

顺序<大骨节病>控制 + <大骨节病> A ，<大骨节病>控制 + <大骨节病> V ，<大骨节病>控制 + <大骨节病> C 不会覆盖已有的选择。这将追加拷贝的选区来选定的。

The sequence Ctrl+A, Ctrl+V, Ctrl+C will not overwrite the existing selection. It will append the copied selection to selected one.

推荐答案

有一个动态规划的解决方案。我们开始知道0键可以使我们0的。然后，我们遍历了我至 N ，做了两件事：pressing一个曾经和pressing全选+复制然后粘贴Ĵ倍（实际上 JI-1 以下;注意这里的窍门：内容仍然在剪贴板上，这样我们就可以多次粘贴而不复制每次）。我们只需要考虑最多连续4贴，因为选择，复制，粘贴×5就相当于选择，复制，粘贴，选择，复制，粘贴，而后者是更好，因为它给我们留下了更多的剪贴板。一旦我们达到了 N ，我们想要的结果。

There's a dynamic programming solution. We start off knowing 0 keys can make us 0 A's. Then we iterate through for i up to n, doing two things: pressing A once and pressing select all + copy followed by paste j times (actually j-i-1 below; note the trick here: the contents are still in the clipboard, so we can paste it multiple times without copying each time). We only have to consider up to 4 consecutive pastes, since select, copy, paste x 5 is equivalent to select, copy, paste, select, copy, paste and the latter is better since it leaves us with more in the clipboard. Once we've reached n, we have the desired result.

复杂性可能表现为O（N），但由于数量的增长以指数速度其实是O（N ² ）由于乘以大量的复杂性。下面是一个Python实现。它需要大约0.5秒来计算N = 50,000。

The complexity might appear to be O(N), but since the numbers grow at an exponential rate it is actually O(N²) due to the complexity of multiplying the large numbers. Below is a Python implementation. It takes about 0.5 seconds to calculate for N=50,000.

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]

在code，Ĵ重presents后，我们的新的关键presses序列pssed键$ P $的总数。我们已经有了我键presses在这个阶段，和2个新的关键presses去全选和复制。因此，我们正在打糊 JI-2 次。由于粘贴增加了 DP的现有的序列[I] A 的，我们需要添加 1 使其 JI-1 。这解释了 JI-1 在第二-最后一行。

In the code, j represents the total number of keys pressed after our new sequence of keypresses. We already have i keypresses at this stage, and 2 new keypresses go to select-all and copy. Therefore we're hitting paste j-i-2 times. Since pasting adds to the existing sequence of dp[i] A's, we need to add 1 making it j-i-1. This explains the j-i-1 in the 2nd-last line.

下面是一些结果（ N =>数A的）：

Here are some results (n => number of A's):

• 7 => 9
• 8 => 12
• 9 => 16
• 10 => 20
• 100 => 1391569403904
• 1000 => 3268160001953743683783272702066311903448533894049486008426303248121757146615064636953144900245 174442911064952028008546304
• 50000 => 一个非常大的数字！

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

我同意@SB，你应该总是说明你的假设：我的是，你并不需要粘贴两次翻番的字符数。这得到了7答案，所以，除非我的解决方案是错误的假设必须是正确的。

I agree with @SB that you should always state your assumptions: Mine is that you don't need to paste twice to double the number of characters. This gets the answer for 7, so unless my solution is wrong the assumption must be right.

在万一有人想知道我为什么不检查形式的序列<大骨节病>控制 + <大骨节病> A ，<大骨节病>控制 + <大骨节病> C ，<大骨节病> A ，<大骨节病>控制 + <大骨节病> V ：最终的结果总是相同的<大骨节病> A ，<大骨节病>控制 + <大骨节病> A ，<大骨节病>控制 + <大骨节病> C ，<大骨节病>控制 + <大骨节病> V 我的执行的考虑。

In case someone wonders why I'm not checking sequences of the form Ctrl+A, Ctrl+C, A, Ctrl+V: The end result will always be the same as A, Ctrl+A, Ctrl+C, Ctrl+V which I do consider.

这篇关于使用按键A，Ctrl + A键，按Ctrl + C和Ctrl + V的最大字符数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！