第142章 规则

热烈掌声响起来。

观眾席上大部分人都在盯著大屏幕，等著看规则。

大屏幕亮了。

团队现场编程。限时三小时。共一道大题，分三个阶段递进。

题目：设计一套中文输入法引擎。

林东看到这行字的时候，手指在键盘上停了一下。

输入法。

屏幕、电池、主板、外壳、触控算法、天线、驱动一全都齐了，唯独输入法还用的是开源的方案，体验一般，適配也麻烦。

他本来打算年后做一套，现在好了，决赛题目就是输入法。

他嘴角动了一下。

做完直接拿走。

阶段一（60分钟）：核心索引。

设计拼音到汉字的索引结构。给定词库（约10万词条），要求支持拼音输入，返回匹配的候选词列表。响应时间不超过20ms，內存占用不超过1mb。

阶段二（60分钟）：智能联想。

在阶段一的基础上，增加词组联想功能。输入一个词，系统自动预测下一个可能的词。內存占用增加不超过0.5mb。

阶段三（60分钟）：动態优化。

在阶段二的基础上，增加词频动態调整功能。用户的使用习惯实时影响候选词排序。內存占用增加不超过0.5mb，总內存不超过2mb。

提交內容：每阶段完成后提交代码，系统自动评测。三阶段全通过者按总用时排名。

李教授顿了顿，扫了一圈全场：“现在，我宣布—一创新杯程序设计大赛决赛，正式开始。”

大屏幕上倒计时跳动：03：00：00。

体育馆里安静下来，只有键盘敲击的声音。

林东没有急著动手。

他把三个阶段的要求又看了一遍，然后靠在椅背上，闭上眼睛。

阶段一，核心索引。

拼音到汉字的映射，常规做法是用trie树，时间复杂度0（n），內存可控。但trie树的每个节点都要存26个指针，10万词条下来，內存肯定超1mb。得换一种思路。

他想到了李虎重写后的那个数据结构。

第二轮比赛，李虎那道题的原解法是0（n2），重写后降到了0（nlogn）。

核心改进是把嵌套循环换成了哈希加二分查找，数据存储从炼表换成了数组。当时林东站在李虎后面看了一眼，觉得这个思路不错，顺手记下来了。没想到今天用得上。

他睁开眼睛，打开编辑器。

先用哈希表存拼音到词条索引的映射，再用数组存词条本身。

查询的时候，哈希找到索引，二分查找定位，一次搞定。时间复杂度0（log

n），內存占用—他算了一下，大概0.6mb。

够了。

他开始写代码。

手指落在键盘上，速度不快不慢。哈希函数、衝突处理、二分查找边界—

每一个细节都在他脑子里过了好几遍。他不是在“写”代码，是在“翻译”脑子里的东西。

写了大概三十分钟，他停下来，检查了一遍。哈希函数没问题，二分查找边界处理正確，內存分配没有泄漏。

他看了一眼旁边的李虎。李虎也在写，手指飞快，屏幕上代码一行一行地跳出来。他写的是阶段一，用的也是哈希加二分查找一和林东的思路一模一样。

林东嘴角动了一下。

他没告诉李虎怎么做，李虎也没问他。两个人想到一块去了。是这道题的最优解就在那儿，谁水平够，谁就能看到。

他收回目光，继续写。

又写了十分钟，代码完成了。

他按下“编译”——通过。

再按下“运行”——测试用例全部通过。

响应时间——他看了一眼，12ms。內存占用——0.58mb。

他深吸一口气，按下“提交”。

大屏幕上，四大天王队的图標亮了—一提交。

观眾席上一阵骚动。

“这么快？四十分钟就提交了？”

“张扬队那边还没动静呢。”

“是不是太赶了？”

李虎也转过头来，压低声音：“老四，你交了？”

“嗯。”

“这么快？”

林东没回答，盯著大屏幕。

几秒钟后，图標变红。

未通过。

观眾席上响起一片议论。

“被退回了。”

“我说吧，太赶了。”

“四大天王不会翻车吧？”

周琳坐在观眾席上，抓著陈露的胳膊，指甲都快掐进去了：“怎么回事？”

陈露盯著大屏幕，声音很稳：“还没结束。”

林东看著屏幕上那个“未通过”，脸上没什么表情。

他打开评测反馈，看了一眼—边界条件。

拼音“liang”和“lian”的分词边界没处理。

他暗骂了自己一声。

確实漏了。

他开始改了。

在哈希函数里加了一个判断，把“liang”和“lian”分开处理。

五分钟，改完。

重新编译，重新运行，测试用例全部通过。

再次按下“提交”。

大屏幕上，图標变绿。

通过。

用时：四十五分钟。

林东靠在椅背上，长出一口气。

李虎在旁边嘿嘿笑了一声：“嚇我一跳。”

“继续。”林东说。

阶段一完成了，但其他人的阶段一还没完成。

张扬队那边，阶段一还没提交。

陈龙和许藏一直没动手，在等林东和李虎写完阶段一，好接著做阶段二。

“阶段二，谁来？”林东问。

许藏开口了：“我来。”

林东看了他一眼。

“需要什么？”林东问。

“阶段一的代码。”许藏说，“还有词库。”

林东把阶段一的代码发给他。

许藏打开，从头到尾看了一遍，没说话。

然后打开编辑器，开始写。

林东没打扰他，靠在椅背上看著。

许藏的思路和他不一样。阶段二要求词组联想—一输入一个词，系统自动预测下一个可能的词。

常规做法是统计词与词之间的共现频率，词库10万词条，两两组合就是100亿对，根本存不下。

许藏用的不是常规做法。

他把每个词映射成一个固定维度的向量，然后计算向量之间的相似度。相似度高的词，就是可能的下一个词。

这个思路，林东想过，但没往深了想。

因为向量维度太高，计算量太大。但许藏用了降维一用哈希把高维向量压缩成低维，计算量从0（n2）降到了0（n）。

许藏写得很快，代码量很少，但逻辑很绕。

林东看了一遍，看懂了。陈龙也凑过来看了一遍，没说话，但推了推眼镜。

本章未完，点击下一页继续阅读。（1 / 2）