gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:11:35 28 4
gpt4 key购买 nike

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

编写一个程序来打印击键序列,使其生成最大数量的字符“A”。您只能使用 4 个键:ACtrl+ACtrl+CCtrl+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)2个A。对于一些 N > M,最好使用尽可能多的 Ctrl+ACtrl+CCtrl+V 序列,因为它将 A 的数量加倍。

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

最佳答案

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

复杂度可能看起来是 O(N),但由于数字以指数速率增长,由于乘以大数的复杂性,它实际上是 O(N2)。下面是一个 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确实考虑过。

关于algorithm - 使用击键 A、Ctrl+A、Ctrl+C 和 Ctrl+V 的最大字符数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4606984/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com