python 笔试题被刷 求大牛指导!

实现在哪里？

@0bit 我贴了gist啊
如果看不到的话 访问这里：
https://gist.github.com/imjustfly/5370526

第一题以前看过
http://www.matrix67.com/blog/archives/4092

第一题就是考虑一开始那几种情况吧，剩下的ctrl a + ctrl c + ctrl v三个键效率肯定比aaa高，最后考虑下剩下1个或者2个键的情况

代码正确与否不知道
这样的注释嘛（#否则） 不要也罢
另外写英文的注释

第一题这样暴力做肯定是不对的，假设之前已经输入了a个A了，那么再经过2+k次粘贴可以得到k*a个A
假设： M = F(n)
有：
F(n) = max([F(n-2-k)*k for k in range(1, N)]+[n, ])

当n<=0时： F(n) = 0

01背包

我觉得楼主的第一题好像是看错题目了吧。
Ctrl + a 这样 算2次吧
然后
n<=11 次 就是直接按a

n>11 算 ((n-5)%6+5)^((n-(n-5)%6+5)/6)
不知道有没有错了。。

@mingzhi 错了 ((n-5)%6+5)*(2^((n-(n-5)%6+5)/6))吧

第一题，python一行流：
F = lambda n: max([F(n-2-k)*k for k in range(1, n)]+[n, ]) if n > 0 else 0

后面的就懒得看了

好像比背包要简单，因为如果有“复制粘贴”，“复制粘贴”操作肯定是最后一步。
而如果N大于6，肯定会有“复制粘贴”，然后就可以递归了。

@mingzhi 我又觉得我错了
全选 复制 粘帖 再粘帖 再粘帖 再粘帖 再粘帖
再全选 复制 粘帖 再粘帖 再粘帖 再粘帖 再粘帖

这样子更多吧。。

暂时没有详细研究，但是先提出来一个很严重的问题，就是单纯的(全选，拷贝，粘贴)的组合行为，实际上数量是完全没有增加的，因为粘贴的动作会覆盖掉原来的选择，并且光标会移动到最后，至少再粘贴一次才有效果。

第一个是个动态规划问题吧。第二个是正则+awk+sort。

现场笔的还是网络上提交？

n <=6 -> m=n
n>6 -> m(n) = Max (m(n-1)+p, m(n-2)+2p , m(n-3)*2)

ctrl是可以一直按住的
全选的情况下是可以被覆盖的

第一个题目描述得太简单了，是不是只有出题人自己才能看懂呢？ctrl + A到底是算一个键呢？还是算是组合键？如果是组合键，那加上另两个组合键，全部的键的数目就是：A, C, V, ctrl。希望先讲清楚出题人到底啥意图

@mingzhi
@hfeeki
题目就是他给的邮件，题目这样写很容易想到组合键和A一样算一次，如果算两次他应该说有A CTRL C V 这几个键

@awsx 网上提交的

@lddhbu 没这么简单
比如十次按键：
AAAA CTRL+A CTRL+C CTRL+V CTRL+V CTRL+V CTRL+V (20个A)
AAAA CTRL+A CTRL+C CTRL+V CTRL+A CTRL+C CTRL+V（16个A）

哈哈 看来最难的是怎么理解第一题

动态规划我是没有学过了，但是很多时候一眼看上去的东西会有点误差。我简单的手算了一下，过程如下：
f(n + (a,c,v,v)) = f(n) * 2
f(n + (a,c,v,v,v)) = f(n) * 3
f(n + (a,c,v,v,v,v)) = f(n) * 4
f(n + (a,c,v,v,v,v,v)) = f(n) * 5
......

f(n+4) = f(n) * 2
f(n+5) = f(n) * 3
f(n+6) = f(n) * 4
f(n+7) = f(n) * 5
f(n+k) = f(n) * (k - 2)

f(n+8) = f(n) * 6, f(n+4+4) = f(n) * 2 * 2
f(n+9) = f(n) * 7, f(n+5+4) = f(n) * 3 * 2
f(n+10) = f(n) * 8, f(n+6+4) = f(n) * 4 * 2, f(n+5+5) = f(n) * 3 * 3
f(n+11) = f(n) * 9, f(n+7+4) = f(n) * 5 * 2, f(n+6+5) = f(n) * 4 * 3
f(n+12) = f(n) * 10, f(n+8+4) = f(n) * 6 * 2, f(n+6*6) = f(n) * 4 * 4, f(n+4+4+4) = f(n) * 2 * 2 * 2
f(n+16) = f(n) * 14, f(n+12+4) = f(n) * 10 * 2, f(n+8+8) = f(n) * 6 * 6, f(n+4+4+4+4) = f(n) * 2 * 2 * 2 * 2

我们知道指数函数是增长速度最快的函数，所以到此其实大概能得出结论，如果我们把k进行不同的组合拆分的话，大概会是这样的一个结果：

2 ^ (k / 4) = 2 ^ (0.25 * k)
3 ^ (k / 5) = 2 ^ (0.317 * k)
4 ^ (k / 6) = 2 ^ (0.333 * k)
5 ^ (k / 7) = 2 ^ (0.332 * k)
6 ^ (k / 8) = 2 ^ (0.323 * k)

k / 6的时候取得最大值，有兴趣可以算一下验证一下，基本上就是底下的公式变形推导：
a ^ (k / (a + 2)) = 2 ^ (lg(a) / lg(2)) ^ (k / (a + 2))
2 ^ (k / lg(2) * (lg(a) / (a + 2))

所以，当n足够大时，尽量多的按照这个a+c+v+v+v+v的组合来操作，结果是最大的。剩下的部分就是n从多少开始满足这个规则，以及6的组合余下的余数放哪，这个就不推算了。

有错误莫怪哦。

第一题 很简单的动态规划
分为3个原子操作:
“A”
“Press Ctrl+A;Press Ctrl+C;Press Ctrl+V;Press Ctrl+V;”
"Press Ctrl+V;"

当前敲击按键x的次数的最大值为（list[x-1]+1, list[x-4] * 2, list[x-1]+copy_clipboard_num）里的最大值

当 list[x-4] * 2 与 list[x-1]+copy_clipboard_num 相等时
优先使用 list[x-4] * 2 ，这样在步数相同的情况下可以扩大clipboard

其实分析一下就可以看出PressA这种情况在第8次敲键盘之后不会出现, 也可以初始化前八次按键的状态， 然后只采用2种原子操作

代码
http://gist.github.com/5371878

输出步骤的时候从后往前找出来就行

研究了半天状态，结果还是用5分钟写个搜索……orz……
效率不高，n=46时约用时1s
简单的三种操作，1、按A；2、按C-v；3、按C-a,C-c,C-v,C-v
简单的剪枝：如果Clipboard大于1则不按A；反之则按A。
http://gist.github.com/MayLava/5372068

@justfly 1秒钟之内循环1到49毫无压力。注意我前面说的，全选复制粘贴是不会变多的，至少粘贴两次才会多出来一次，所以结果会跟你的不一样。当n=11的时候，m=20。而不是n=10。

SELECT_ALL = 'CTRL+A'
COPY = 'CTRL+C'
PASTE = 'CTRL+V'
PRESS_GROUP = [SELECT_ALL, COPY, PASTE, PASTE, PASTE, PASTE]
A4 = ['A', 'A', 'A', 'A']

def f(n):
press_left = n
press_keys = []
total = 0
group_count = 0

if n <= 7:
return (n, ['A'] * n)
elif n == 8:
return (9, [['A', 'A', 'A'], [SELECT_ALL, COPY, PASTE, PASTE, PASTE]])
elif n == 9:
return (12, [['A', 'A', 'A', 'A'], [SELECT_ALL, COPY, PASTE, PASTE, PASTE]])
else:
press_a4(press_keys)
press_left = press_left - 4
group_count = press_group(press_left, press_keys)
press_left = press_left - 6 * group_count
allot_left(press_left, press_keys)
total = calculate_total(press_keys)
return (total, press_keys)

def press_a4(press_keys):
press_keys.append(A4)

def press_group(press_left, press_keys):
group_count = press_left / 6
for i in range(group_count):
press_keys.append(PRESS_GROUP)
return group_count

def allot_left(press_left, press_keys):
if len(press_keys) == 2:
a_count = press_left / 2
v_count = press_left - a_count
for i in range(a_count):
press_keys[0].append('A')
for i in range(v_count):
press_keys[1].append(PASTE)
else:
left = press_left
index = len(press_keys) - 1
while left > 0:
left = left - 1
press_keys[index].append(PASTE)
index = index - 1
if index == 0:
index = len(press_keys) - 1

def calculate_total(press_keys):
total = len(press_keys[0])
for l in press_keys[1:]:
total = total * (len(l) - 2)
return total

def main():
for i in range(1, 50):
print 'n=%d, m=%d' % (i, f(i)[0])

if __name__ == "__main__":
main()

@justfly 一点小bug，请把press_keys.append(A4)改成press_keys.append(copy.copy(A4))，把press_keys.append(PRESS_GROUP)改成press_keys.append(copy.copy(PRESS_GROUP))

第一题是动态规划吧……归纳下可以得出递推式：
m=f(x)=
1(x=1)
f(x-1)+1
f(x-3)*2
f(x-1)+Clickboard

基本就是同@qdcanyun 的解答那样的啦……

第二题得算算有用信息可能的大小。不知道一天的访问量是多大……

歪下楼

[I 130403 17:26:40] 1 200 GET /question/123 (8.8.9.9) 200.39ms
[I 130403 17:26:90] 1 200 GET /topic/456 (8.8.9.9) 300.85ms
[I 130403 17:26:90] 1 200 POST /answer/789 (8.8.9.9) 300.85ms

公司是知乎，鉴定完毕。

第二题写了个解题报告，欢迎拍砖。

感谢好基友 MayLava 帮忙修改

https://gist.github.com/TheLoverZ/5449825

第二题题意不是很明确……
不过用 awk 直接实现很容易的呀。用三个键计数：
1. awk '/GET \/topic/{id[$4]++;topic[$7]++;it[$4" "$7]++}'

2. END 里面判断：
{for(x in id){if(id[x]>2)print x}} 访问 /topic 大于2次的用户列表
{for(y in it){if(it[y]>2)print y}} 同一个用户访问了2次以上不同 /topic 地址的列表 id /topic/***

真的没看懂题目的要求
[用户列表] ：访问了 2个不同的 /topic 并且这几个topic 均重复访问了 2次？

不过三个哈希组合判断足够了，awk 后面直接跟所有文件的列表一次搞定～～

python 的话……好长。

怎么又开始挖坟了
搭车贴gist
https://gist.github.com/sailxjx/5388648

这个结果对不对？
/*
括号里表示一开始输入几个0
0:0(0)
1:1(1)
2:2(2)
3:3(3)
4:4(4)
5:5(5)
6:6(6)
7:9(3)
8:12(3)
9:16(4)
10:20(4)
11:25(5)
12:36(3)
13:48(3)
14:64(4)
15:80(4)
16:100(5)
17:144(3)
18:192(3)
19:256(4)
20:320(4)
21:400(5)
22:576(3)
23:768(3)
24:1024(4)
25:1280(4)
26:1600(5)
2304(3)
3072(3)
4096(4)
*/