这是来自谷歌的访谈问题.我自己无法解决这个问题.有人可以解释一下吗？
编写一个程序来打印击键序列,以便生成最大数量的字符'A'.您只能使用4个键:A,Ctrl+ A,Ctrl+ C和Ctrl+ V.只允许N次击键.所有Ctrl+字符都被视为一次击键,因此Ctrl+ A是一次击键.
例如,序列A,Ctrl+ A,Ctrl+ C,Ctrl+ V生成4次击键两个A.
我做了一些数学.对于任何N,使用x个数,一个Ctrl+ A,一个Ctrl+ C和y Ctrl+ V,我们可以生成最大((N-1)/ 2)2个A的数量.对于某些N> M,最好使用尽可能多的Ctrl+ A,Ctrl+ C和Ctrl+ V序列,因为它会使A的数量加倍.
序列Ctrl+ A,Ctrl+ V,Ctrl+ C不会覆盖现有选择.它会将复制的选择附加到选定的选择.
mar*_*cog 43
有一个动态编程解决方案.我们开始知道0键可以让我们0 A.然后我们迭代到i最多n,做两件事:按A一次然后按全选+复制然后粘贴j时间(实际上j-i-1在下面;注意这里的技巧:内容仍然在剪贴板中,所以我们可以多次粘贴它每次复制).我们只需要考虑最多4个连续的粘贴,因为选择,复制,粘贴x 5相当于选择,复制,粘贴,选择,复制,粘贴,后者更好,因为它在剪贴板中留下了更多.一旦我们到达n,我们就会得到理想的结果.
复杂性可能看起来是O(N),但由于数字以指数速率增长,因此实际上是O(N 2),这是由于大数字的乘法的复杂性.下面是一个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个新的按键用于select-all和copy.因此,我们正在进行粘贴j-i-2时间.由于粘贴增加了现有的序列dp[i] A,我们需要添加1它j-i-1.这解释了j-i-1倒数第二行.
以下是一些结果(n=> A的数量):
我同意@SB你应该总是陈述你的假设:我的是你不需要粘贴两次来加倍字符数.这得到7的答案,所以除非我的解决方案是错误的,否则假设必须是正确的.
如果有人想知道我为什么不检查形式的序列Ctrl+ A,Ctrl+ C,A,Ctrl+ V:最终的结果总是一样的A,Ctrl+ A,Ctrl+ C,Ctrl+ V我不考虑.
And*_*ark 41
通过使用marcog的解决方案,我找到了一个开始的模式n=16.为了说明这一点,这里是n=24最多的击键n=29,我用S(选择)替换^ A,用C(复制)替换^ C,为了可读性,用V(粘贴)替换^ V:
24: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P
4 * 4 * 4 * 4 * 4 = 1024
25: A,A,A,A,S,C,P,P,P,S,C,P,P,S,C,P,P,S,C,P,P,S,C,P,P
4 * 4 * 3 * 3 * 3 * 3 = 1296
26: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,S,C,P,P,S,C,P,P
4 * 4 * 4 * 3 * 3 * 3 = 1728
27: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,S,C,P,P
4 * 4 * 4 * 4 * 3 * 3 = 2304
28: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P
4 * 4 * 4 * 4 * 4 * 3 = 3072
29: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P
4 * 4 * 4 * 4 * 4 * 4 = 4096
在初始4 As之后,理想的模式是选择,复制,粘贴,粘贴,粘贴和重复.这将每5次击键将As的数量乘以4.如果这5个击键模式不能消耗剩余的击键,则一些4个击键模式(SCPP)消耗最后的击键,根据需要替换SCPPP(或移除其中一个贴片).4个击键模式每4次击键将总数乘以3.
在这里使用这个模式是一些Python代码得到与marcog的解决方案相同的结果,但是是O(1)编辑:由于取幂,这实际上是O(log n),这要归功于IVlad指出了这一点.
def max_chars(n):
if n <= 15:
return (0, 1, 2, 3, 4, 5, 6, 9, 12, 16, 20, 27, 36, 48, 64, 81)[n]
e3 = (4 - n) % 5
e4 = n // 5 - e3
return 4 * (4 ** e4) * (3 ** e3)
计算e3:
击键列表末尾总共有0到4个SCPP模式,n % 5 == 4有4个,n % 5 == 1有3个,n % 5 == 2有2个,n % 5 == 3有1个,n % 5 == 4有0个.这可以简化为(4 - n) % 5.
计算e4:
每当模式总数n % 5 == 0增加到正好时,模式总数就会增加1 n / 5.使用楼层划分我们可以得到模式的总数e4,总数是模式的总数减去e3.对于那些不熟悉Python的人来说,这//是一个面向未来的地板划分符号.
NG.*_*NG. 16
这是我如何接近它:
给定一些文本,需要4次击键才能复制它:
从那里,你可以考虑做4或5 A,然后循环上面.请注意,ctrl + a, c, v, v当您循环播放时,执行操作会以指数方式增长文本.如果剩余的笔画数<4,那就继续做CtrlV
像谷歌这样的采访@的关键是陈述你的假设,并传达你的想法.他们想知道你是如何解决问题的.
使用CtrlA+ CtrlC+ CtrlV仅在4'A之后才有优势.
所以我会做这样的事情(在伪BASIC代码中,因为你没有指定任何正确的语言):
// We should not use the clipboard for the first four A's:
FOR I IN 1 TO MIN(N, 4)
PRINT 'CLICK A'
NEXT
LET N1 = N - 4
// Generates the maximum number of pastes allowed:
FOR I IN 1 TO (N1 DIV 3) DO
PRINT 'CTRL-A'
PRINT 'CTRL-C'
PRINT 'CTRL-V'
LET N1 = N1 - 3
NEXT
// If we still have same keystrokes left, let's use them with simple CTRL-Vs
FOR I IN N1 TO N
PRINT 'CTRL-V'
NEXT
编辑
在O（1）中可以解决：与斐波那契数字一样，有一个公式可以计算打印的As数（以及击键顺序）：
1）我们可以简化问题描述：
等于
2）我们可以将击键序列描述为{'*'，'V'，'v'}中N个字符的字符串，其中'v'表示[Cv]，'*'表示[Ca]和'V '表示[抄送]。示例：“ vvvv * Vvvvv * Vvvv”
该字符串的长度仍等于N。
该字符串中Vv字长度的乘积等于产生的As的数量。
3）给定该字符串的固定长度N和固定数量的单词K，如果所有单词的长度几乎相等，则结果将是最大的。它们的成对差不超过±1。
现在，如果给定N，最优数K是多少？
4）假设，我们想通过添加一个长度为L的单个单词来增加单词数量，然后我们必须将L + 1倍于任何以前的单词减一个'v'。示例：“ ... * Vvvv * Vvvv * Vvvv * Vvvv”->“ ... * Vvv * Vvv * Vvv * Vvv * Vvv”
现在，最佳字长L是多少？
（5 * 5 * 5 * 5 * 5）<（4 * 4 * 4 * 4 * 4）* 4，（4 * 4 * 4 * 4）>（3 * 3 * 3 * 3）* 3
=>最佳是L = 4。
5）假设我们有足够大的N来生成一个长度为4的许多单词的字符串，但只剩下一些击键；我们应该如何使用它们？
如果剩余5个或更多：追加另一个长度为4的单词。
如果还有0：完成。
如果还剩4个：我们可以
a）附加一个长度为3的单词：4 * 4 * 4 * 4 * 3 = 768。
b）或增加4个单词至5个长度：5 * 5 * 5 * 5 = 625。=>附上一个词比较好。
如果还剩3个：我们可以
a）或通过将前一个单词的长度从4调整为3来附加一个长度为3的单词：4 * 4 * 4 * 2 = 128 <4 * 4 * 3 * 3 = 144。
b）将3个单词增加到5个长度：5 * 5 * 5 = 125。=>附上一个词比较好。
如果还剩下2：我们可以
a）或通过将前面的两个单词从长度4调整为3：来附加一个长度为3的单词：4 * 4 * 1 = 16 <3 * 3 * 3 = 27。
b）将2个单词增加到5个长度：5 * 5 = 25。=>附上一个词比较好。
如果还剩下1：我们可以
a）或通过将前三个词从长度4调整为3：来附加一个长度为3的词：4 * 4 * 4 * 0 = 0 <3 * 3 * 3 * 3 = 81。
b）增加一个单词至5：4 * 4 * 5 = 80。=>附上一个词比较好。
6）现在，如果我们没有“足够大的N”来使用5）中的规则怎么办？如果可能，我们必须遵守计划b）！小N的字符串为：
1：“ v”，2：“ vv”，3：“ vvv”，4：“ vvvv”
5：“ vvvvv”？5 （方案b）
6：“ vvvvvv”？6 （方案b）
7：“ vvv * Vvv”？9（计划a）
8：“ vvvv * Vvv”？12（计划a）
9：“ vvvv * Vvvv”？16
10：“ vvvv * Vvvvv”？20 （计划b）
11：“ vvv * Vvv * Vvv”？29（计划a）
12：“ vvvv * Vvv * Vvv”？36（计划a）
13：“ vvvv * Vvvv * Vvv”？48（计划a）
14：“ vvvv * Vvvv * Vvvv”？64
15：“ vvv * Vvv * Vvv * Vvv”？81（计划a）
…
7）现在，长度为N的字符串中的最佳单词数K是多少？
如果N <7，则K = 1，否则，如果6 <N <11，则K = 2; 否则：K = ceil（（N + 1）/ 5）
用C / C ++ / Java编写： int K = (N<7)?(1) : (N<11)?(2) : ((N+5)/5);
如果N> 10，则长度为3的单词数将为：K * 5-1-N。这样，我们可以计算出打印为：
如果N> 10，则As的数目为： 4 ^ {N + 1-4K}·3 ^ {5K-N-1}