大家好，我是小楼。上周，我参加了某区一个程序员技能大赛的预赛，其实就是一个算法大赛。虽然最后的结果是通过了初赛，但是过程真的是一言难尽。这次的算法竞赛和ACM很像。虽然我大学的专业是数学，大学的时候也学过ACM的课程，但是我的算法确实不行，而且很好。好在这次比赛是组（抱大腿）组队模式，3人一组，3小时，一共7道算法题，1道入门，2道easy，2道medium，2道difficult。入门题我10分钟就写完了，但是...因为我知道自己有点高手，所以我在游戏开始的时候就挑了最简单的题做，把难的题交给了队友。结果3个小时过去了，这道看似最简单的题还是没有解出来。下面结合这个问题说说我的心路历程。这道题的描述如下：看似字很多，其实想表达的很简单，就是输入一些成绩，每个成绩输入的时候，如果超过了bestgradein班级，输出prefect，如果超过自己最好成绩就输出great，没有超过自己最好成绩就输出bad。是不是很简单？用一个max变量保存全班最好成绩，用一个map保存每个人最好成绩，不就解决了吗？不过我是第一次使用这个oj系统，连用户都是刚注册的，所以看了一会输入输出demo。本次比赛只能使用ACM输入输出模式。比如你使用Go语言，输入输出应该是这样的：学习了输入输出后，一口气写出如下解决方案：packagemainimport("fmt")funcmain(){varnintvarnamestringvarxfloat32varmaxfloat32scores:=make(map[string]float32,n)fmt.Scan(&n)fori:=0;我max||i==0{fmt.Println("perfect")max=xscores[name]=x}else{ifs,ok:=scores[name];好的{如果x>s{fmt.Println("great")scores[name]=x}else{fmt.Println("bad")}}else{fmt.Println("great")scores[name]=x}}}}当我得意洋洋，觉得这道题10分钟就能搞定的时候，提交代码居然超时了。比赛期间没有截图。提交后显示有少数测试用例耗时超过2秒。oj的判断原则是准备一堆测试用例。如果全部通过，则判定为通过。如果很容易通过，设计者就会想出各种极端的案例。优化地图性能，转身认真复习题。果然时间空间有限：时间限制：C/C++1秒，其他语言2秒空间限制：C/C++262144K，其他语言524288K64bitIOFormat:%lld除此题外还有map读取和写，其他都是O(1)复杂度。性能不够是因为地图性能不够？地图的性能不够，到底是哪里不够呢？众所周知，map的原理一般是这样的：当map中存储了一些key时，会先为key计算hash值，在map中找到对应的hashslot。tree，这里我们简化为链表），因为不同key的hash值可能会重复（冲突），如果有冲突，key只能排成链表，链表必须每次搜索都要遍历。那么有没有可能是设计者给了一堆哈希值重复的名字，而且数量多到每次插入和查找都要遍历链表，导致性能下降和超时呢？于是仔细复习题，发现输入的名字和成绩是有限制的：名字保证长度不超过6，只由小写英文字母组成，每个名字代表唯一的学生x是小数点后1位，0≤x≤300name最多长度为6，且为小写字母。这给了我一点启发。querymap能不能变成O(1)的复杂度？显然，小写字母的范围是a~z。如果把它看成一个数，就是1-26，也就是27个碱基，所以每个名字都可以表示成一个27个碱基的数，这样大家的成绩就可以放到一个大数组中，进行一次O(1）根据名字的27位碱基查找。为什么是27进制而不是26进制，因为名字里没有说有多少位，比如只有5位，空位怎么表示？只能用0表示，a-z为1-26，组合为27个碱基。参考小数计算规则，27进制应该这样计算（以roshi为例）：计算出的值是数组的下标，那么数组的最大值是多少？26*27^5+26*27^4+26*27^3+26*27^2+26*27^1+26*27^0很容易计算：387420488需要这么大的数组，大概3个更多1亿以上，输入结果是1位小数，可以转成int，大约4个字节，1513361KB，好像比要求的524288K多了。不考虑空间，写个版本跑一下看能不能过。？代码写起来很简单：packagemainimport("fmt")funcmain(){varnintvarnamestringvarxint32fmt.Scan(&n)varscores[387420488]int32varexist[387420488]int32varmax我的int32:=0;我max||i==0{fmt.Printf("perfect\n")max=xscores[idx]=xexist[idx]=1}else{ifexist[idx]==0||x>scores[idx]{fmt.Printf("great\n")scores[idx]=xexist[idx]]=1}else{fmt.Printf("bad\n")}}}}varindex27=[6]int32{1,27,27*27,27*27*27,27*27*27*27}funcmapIndex(xstring)int32{varindexint32fori:=len(x)-1;我>=0;i--{index=index+int32(x[i]-96)*index27[len(x)-1-i]}rreturnindex}结果是一个错误。我当时不明白，但后来我明白了。暂且不说。原因我们后面再说，因为报错不明确。它可以通过测试。悟性在哪里？还是超出了内存？优化内存使用上面代码使用了2个数组，一个存放最大值，一个存放该值是否存在，一个数组1513361KB，两个3026722KB，是最大内存限制var分数的5.7倍[387420488]int32var存在[387420488]int32exist数组可以使用boolean类型，最高分0<=0<=300，int16就够了。大小范围是int81byte-128~127int162byte-32768~32767int324byte-2147483648~2147483647如果是这种组合，会占用1135020KB，是上限的两倍多，还是有点多，先试试：还是一样的，是不是我的算法有问题？这没有意义。至此，我真的无计可施了，3个小时也耗尽了，游戏也结束了。赛后思考赛后，我带着这个问题向刚加入字节跳动的朋友提问。我觉得我刚上字节的时候应该做了很多题。新的思路是使用前缀树：每个名字构造一个前缀树，查找时最多只需要查找6次，内存占用不要太多，是时间和空间的平衡.老板还补充道：游戏比较特殊，可能是某个案件的主人，而你要做的就是如何摆脱这个特殊案件。大佬的话似乎很有道理，于是我写了一个之前开源的版本：packagemainimport("fmt")typetreeNodestruct{maxfloat32next[26]*treeNode}funcmain(){varnintvarnamestringvarxfloat32fmt.Scan(&n)varmaxfloat32tree:=new(treeNode)fori:=0;我max||i==0{fmt.Println("perfect")max=xinsert(tree,name,x)}else{iftmp:=searchAndStoreMax(tree,name,x);tmp!=-1{ifx>tmp{fmt.Println("great")insert(tree,name,x)}else{fmt.Println("bad")}}else{fmt.Println("great")insert(tree,name,x)}}}}funcinsert(node*treeNode,namestring,xfloat32){fori:=0;我<长度（名称）；i++{idx:=int32(name[i]-'a')ifnode.next[idx]==nil{node.next[idx]=new(treeNode)}node=node.next[idx]}节点。max=x}funcsearchAndStoreMax(node*treeNode,namestring,xfloat32)float32{fori:=0;我<长度（名称）；i++{idx:=int32(名称[i]-'a')ifnode.next[idx]==nil{return-1}node=node.next[idx]}ifx>node.max{tmp:=node.maxnode.max=xreturntmp}returnnode.max}结果又超时了。我拿走了，终于找到了问题所在。后来试了很多方法，都没有用。比如我就在想是不是围棋的map性能不够好。我用Java试了一下，结果还是不行。终于在搜索牛客网的时候找到了突破口（对对对，这个比赛就是在牛客网上举办的）。简单来说，牛客网的ACM模式输入可能需要读取一行，然后处理成想要的数据。抱着怀疑的态度试了一下，果然，狗屎！您可以使用初始地图来关闭！虽然我不知道这两个输入之间的区别。关键我还是用网站提示的输入法，实在是太坑爹了。正确的输入方法如下：Stdin)ifinput.Scan(){n,_=strconv.Atoi(input.Text())}scores:=make(map[string]float64,n)varmaxfloat64fori:=0;我
