续 · 键盘上的权重战争
窗外的雪还没停，赫尔辛基的冬天长得像没优化的冒泡排序。
昨天你用一套“贪心平摊”解决了 nokiabest 的极限按键次数，这会儿正摸着 Nokia 3310 玩贪吃蛇——用 2、4、6、8 控制方向的经典游戏。
正吃到第七个豆子，CEO 推门进来了。他举着一台原型机，屏幕幽幽地亮着。
“昨天你跟我说，“CEO 清了清嗓子，"nokiabest 那种每个字母只出现一次的情况，随便塞就能最优。但你后面提到字母会重复——确实，真实世界里，用户打的字母不是均匀分布的，e 的出现频率是 z 的三十倍——如果考虑字母频率，重新映射键位，最少要按多少次键？”
他把手机往你桌上一搁，屏幕上是一条正在编辑的短信草稿，收件人写着 nokia，内容只有一行字：connectingpeople
“老板，”你抬头看他，“拿自家口号当测试用例，是不是有点自恋？”
CEO 的表情纹丝不动：“ 这是市场部给的 KPI——他们明年要把这句印在每台手机上。如果连自己的 slogan 都打不利索，发布会上怎么跟黑莓对线？”
他把原型机往你面前推了半寸：“这才是真实世界的需求。”
第一幕：频率加权下的贪心
昨天的 nokiabest，所有字母只出现一次，权重相同，排列顺序无所谓，只需要贪心地一层一层塞满即可。但今天的 connectingpeople，字母出场次数不同。e 出了 3 次，l 只出 1 次。如果傻乎乎地把 e 塞到某个键的第三层——用户每打一个 e 就要按 3 次键，手机迟早会被扔进芬兰湾。
你在白板上画了八个方框，代表 2 到 9 号键。
“每个键可以挂一串字母。排第一的按 1 次，排第二的按 2 次，排第三的按 3 次——按键代价按层数递增。那么，最优映射本质上就跟快捷键一个道理：最常用的操作一定绑在最顺手的位置，没人会把‘保存’藏在三级菜单里。
CEO 点头：“这个不用解释，肌肉记忆就是成本。”
“这就是今天这道题的灵魂。”我敲了敲白板，“频率越高的字母，要放到越便宜的位置。”
“在频率加权的情况下，最优填充就是按频率降序，依次往 8 个键的每一层’铺货’。第一层 8 个坑位给频率最高的 8 个字母，第二层给接下来的 8 个，依此类推。”
- 统计词频，谁出场次数多谁就是 VIP。
- 把频率从高到低排序。
- 按顺序填满 8 个键的第一层（每个代价 1），再填第二层（每个代价 2），第三层……
- 每个字母的总代价 = 它所在层数 × 它的频率。总按键次数 = 所有字母代价之和。
CEO 若有所思地点点头：“那如果我给你一个更复杂的词呢？比如……芬兰语里那个‘飞机喷气发动机助理机械师学员’——lentokonesuihkuturbiinimoottoriapumekaanikkoaliupseerioppilas？”
“一样的，算法内核一句话——按频率降序排列，第 i 个字母（从 0 开始）会被放在第 i // 8 层（层数从 0 起），按键代价为 (i // 8) + 1，总次数累加 频率 × 代价。”
第二幕 · 代码就是武器
你拉过键盘，打开 Notepad。2003 年的诺基亚办公室里，这台电脑跑的还是 Windows 2000，编程环境朴素得像白水煮土豆。但这不重要——算法在手，什么编辑器都是利器。
这个年代，Python 2.2 刚刚发布，写起来颇有复古手感。
def minimumPushes(word: str) -> int:
# 1. 统计频率，别问我为什么不用Counter——Python 2.2里还没这玩意儿
freq = [0] * 26
for ch in word:
freq[ord(ch) - ord('a')] += 1
# 2. 降序排序——高频在前，低频在后
freq.sort(reverse=True)
# 3. 贪心分配：第 i 个字母落在第 i//8 层，代价 = 层数 + 1
total_pushes = 0
for i, f in enumerate(freq):
if f == 0:
break
layer = i // 8 + 1 # 第几层，代价即层号
total_pushes += f * layer
return total_pushes
时间复杂度 O(n + 26 log 26)，实际上就是 O(n)。空间复杂度 O(1)。还是那股诺基亚味儿——低功耗，高可靠。
你转头看向 CEO：“假设英语里 26 个字母全部出现，频率排名前 8 的占第一层，按 1 次；接下来 8 个占第二层，按 2 次；最后 10 个占第三层，按 3 次。没有谁可以逃脱这个代价层级——除非你给 26 个字母每人一个独立按键。”
说到这儿，你顿了下，望向桌上那台 BlackBerry 8700——昨天黑莓经理非要留在这儿的，说是“让诺基亚的工程师开开眼，看看什么叫真正的打字效率”。
第三幕 · 物理键的诅咒
“黑莓的全键盘，在这种频率加权测试下，表现如何？”CEO 冷不丁问了一句。
你拿起那台黑莓，用手指划过那密密麻麻的 26 个按键。“他们的方案是：26 个字母，一人一键。也就是说，不管 e 出现了多少次，也不管 z 多稀有，成本全是 1。”
“听起来……很好啊？”CEO 的语气有点不确定。
“单论按键次数，确实好。代价嘛——硬件复杂度爆炸，单手操作变灾难，拇指移动距离赛过马拉松。 ”
你拿起诺基亚原型机，八个键，简洁得像一把瑞士军刀。“物理世界的残酷就在这儿——你用多少空间换多少效率。假设英语词汇频率分布是固定的，我们这套 8 键多层方案的总按键次数，只比全键盘多了一个‘层数代价’。但物理成本呢？我们的键盘只占三分之一的面板，省下来的空间可以放更大的屏幕，或者更大的电池。”
“更重要的是……”你压低了声音，“黑莓的 QWERTY 固定了每个字母的位置，它没办法根据输入习惯动态调整。而我们的映射方案是可重新编程的——理论上，我们可以在手机里内置一个轻量级频率统计引擎，静默学习用户的打字习惯，动态调整映射。高频字母往第一层塞，低频往后面扔。这种个性化优化，黑莓的物理键盘永远做不到。”
CEO 的眼镜片上反过一道白光。“你是说……自适应键盘？”
“你也可以说是‘输入法’。”你笑了笑，“不过现在说这个还早。先把今天的问题搞定吧。”
尾声
那天下午，你把完整的算法文档交给了 CEO。标题写的是：
《按键映射优化方案 2.0：引入字母频率权重的贪心分配》
交完文档，你走出大楼。雪停了，天空露出一小片北欧特有的低饱和度蓝。
你想起昨天咬的那口苹果，还剩半个在口袋里。
黑莓的产品经理后来再也没来找过你。据说他回到加拿大后，在实验室里对着 26 键全键盘吼了一句：“你永远没法用物理按键解决频率权重问题！” 然后被保安请了出去。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。