★ FEATURED ARTICLE 我接触洛谷P1765“手机”这道题是在给新手班带练的时候。当时很多同学刷到这道题第一反应都是“这不就是个模拟吗”结果一提交就掉进各种坑里有人读不进来带空格的字符串有人把大写字母当成普通字符处理还有人忘了空格本身也算一次按键。这道题表面上是入门难度实际上把字符串处理、查表法、边界条件这些基本功全串起来了。对于刚接触算法竞赛的同学来说这是一道性价比极高的练习题既能巩固基础语法又能提前感受“题目读不懂比代码写不出更致命”的竞赛常态。只要你做过几道洛谷的入门题就会发现P1765这类“规则模拟题”在竞赛里非常常见。它不会考你高深的算法但会给你一套实际生活中的规则让你用编程语言老老实实地复现一遍。这类题做得好不好往往不取决于你会多少算法而取决于你能不能把题目描述里的每一个细节都转化成代码逻辑。这也是我觉得值得专门写一篇博文来拆解这道题的原因——它看起来简单却包含了很多“只可意会不可言传”的经验点。1. 题目到底在问什么1.1 题目背景九宫格键盘的输入规则洛谷P1765的题目背景设定在老式手机的多按键输入法上。用过功能机的朋友都知道那时候的手机键盘不是现在触屏上的全键盘而是一个9键或12键布局。每个数字键上对应若干个英文字母比如2键上对应ABC3键上对应DEF以此类推。要在这种键盘上输入一个字母规则是这样的你想输入“a”按一下2键想输入“b”按两下2键想输入“c”按三下2键。也就是说你的目标是字母在一个按键上的第几个位置你就需要连续按几次这个键。而不同字母之间比如“a”后面跟着“d”由于“a”在2键上“d”在3键上直接切换按键就可以了。但如果连续的两个字母在同一个按键上比如“a”后面跟着“b”你按完“a”后不能直接按两下2键输出“b”因为这样中间的停顿会被识别成输入了新的字符。所以遇到这种情况你需要先按一下别的键来“分隔”在经典的规则里就是用按一次空格键来分隔。这就是P1765的核心模拟规则。题目会给你一句由小写字母、空格和句号组成的英文句子让你计算按出这句话总共需要按键多少次。1.2 核心考点这道题到底考什么很多第一次做这道题的同学读完之后会觉得“这不就是查表吗有什么好考的”但仔细分析这道题其实在考察三个层面的能力。第一层是规则理解能力。题目描述里包含了“同键分隔”这个特殊规则。很多人在计算的时候只算了字母本身需要的按键次数完全忘了同键切换时需要额外按一次空格键。这就是典型的“题目没读透”——竞赛里这类失误是致命的。第二层是映射关系的组织能力。数字2到9一共8个键对应26个字母再加上空格和句号一共有28个“输入目标”。你需要以某种方式把每个输入目标对应的按键次数和所属键位存下来。这考察的是你对表结构的理解是开一个二维数组、用多个一维数组还是直接在代码里写个查找函数都能体现你的代码组织能力。第三层是边界条件的处理能力。输入的句子既有大写字母又有小写字母还有空格和句号。大写字母怎么处理是不是要先算一次上档键题目里到底有没有这个规则这些细节决定了你的代码能不能过全部测试点。1.3 数据范围与输入输出要求P1765的输入格式和输出格式都很简短输入只有一行字符以回车结束是包含字母、空格和句号的英文句子。输出只有一个数字表示总共需要的按键次数。这里有一个很多人容易忽视的点题目说的是“输入只有一行”题面一般写一行或多行但实际是一行但这一行里是可能有空格的。这就意味着你不能用普通的cin s或者scanf(%s)来读入因为这两种方式遇到空格就会停下来。你必须使用能够读取整行含空格字符串的方式。另外还要注意句号。英文句号‘.’在九宫格键盘中出现在1键上通常按一下就能输入句号。这个细节题目里会说明但如果你之前做过别的手写输入法题可能默认句号是按键次数不同的规则那就容易踩坑。2. 解题思路从手工模拟到程序化处理2.1 先手工模拟一遍理解规则在学习怎么写代码之前我强烈建议你先拿纸笔手工模拟一遍。比如输入句子“i love you.”我们手动算算需要按键多少次。先把整句话拆成每个字符i、空格、l、o、v、e、空格、y、o、u、.。在九宫格键盘上i在4键上是第3个字母所以输入i需要按3次。接下来是空格空格不属于任何字母键通常单独处理按一次空格键所以空格是1次。然后是ll在5键上是第3个字母需要按3次。l的前一个字符是空格空格和l不在同一个键上所以不需要额外的分隔键。接下来是oo在6键上是第3个字母按3次。前一个字符l在5键上键位不同无需分隔。再往后v在8键上是第3个字母按3次e在3键上是第2个字母按2次。到这里我们遇到了一个关键点单词“you”内部y在9键上按3次y是第2个字母需要仔细数wxyz分别在9键的1、2、3、4位y是第3位o在6键上按3次u在8键上按2次tuvu在8键上第2位。最后是句号句号在1键上按1次。如果严格按照题意一个个数这个例子的总按键数是i3空格1l3o3v3e2空格1y3o3u2句号125次。你自己动手算一遍就能体会到这个过程里最麻烦的就是“数某个字母在按键上排第几位”这恰好就是我们要传给程序去做的查表工作。手工模拟完你再看题目里的规则会清晰很多。2.2 两种经典解法映射表法和计算法理解了规则之后我们可以有两种思路来实现。第一种是映射表法也是最直观、最不容易出错的方法。把所有可能需要输入的目标小写字母、空格、句号和它们对应的“按键次数”建立一一对应关系。这个对应关系不需要额外计算直接手动写好放在代码里供查询。第二种是计算法即不直接建立字母到按键次数的映射而是先根据字母ASCII码推算出它在哪个键上、是第几位然后实时计算。这种方法代码更“聪明”但更容易出错因为你必须把26个字母在8个键上的分布规律理清楚还要处理大写字母和标点的特殊规则。对于新手我的建议很明确选映射表法。这不是因为计算法不好而是因为竞赛里最重要的永远是正确性优先。映射表法几乎不可能错逻辑清晰容易查错而计算法虽然看起来精简但极容易因为边界情况而翻车。等你以后熟练了可以再试试计算法体会一下不同的编程思路。2.3 为什么推荐映射表法而不是直接算我见过太多新手在这个题上写出一堆复杂的ASCII运算代码结果在字母分组的边界上疯狂报错。比如要判断某个字母在哪一组就得手动划分a-c、d-f、g-i、j-l、m-o、p-s、t-v、w-z这些分组不是均匀的最后两组分别有4个和4个字符t-v是3个w-z是4个严格说p-s是4个。如果靠计算法你得记清楚每个分组的起点和长度维护成本相当高。而映射表法呢你只需要在一开始就把26个字母按顺序存好算出每个字母的按键次数然后查表就行。这个方法的好处在于它把“规则计算”变成了“查字典”计算核心只有一行代码最终程序的正确性几乎完全取决于你建的表准不准。打个比方这就像你去一个陌生的城市手里有一份详细的地图你只需要照着地图走而不需要临时判断东南西北。地图也许不够“高级”但它永远不会带你走错路。3. 核心细节解析与实操要点3.1 字符到按键次数的映射表怎么建我们来一步步建立这张表。经典的九宫格键位大概是这样分布的2键abc所以a需要按1次b按2次c按3次3键defd按1次e按2次f按3次4键ghig按1次h按2次i按3次5键jklj按1次k按2次l按3次6键mnom按1次n按2次o按3次7键pqrsp按1次q按2次r按3次s按4次8键tuvt按1次u按2次v按3次9键wxyzw按1次x按2次y按3次z按4次而空格和句号都是单独的键按一次即可。你要做的事情是把这个映射关系用一个容器存起来。有两种常用办法一是直接建立一个长度为26的整数数组下标从0到25分别代表a到z数组里存储对应字母需要的按键次数。比如keyCount[0] 1代表a按1次keyCount[1] 2代表b按2次。这种方式的查询逻辑是keyCount[ch - a]非常简洁。二是建立一个字符到次数的pair数组逐个判断。这种方式代码稍长但可读性更高适合不熟悉数组下标的同学。我推荐用第一种因为它把查表逻辑变成了一个简单的下标映射。下面是这种建表方式的一个完整思路int keyTimes[26] {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4};这个数组里的顺序其实就是26个字母a到z依次的按键次数。你对照上面的键位分布检查一下p在第16个位置下标15是1s在第18个位置下标17是4z在第25个位置下标24是4就说明表建对了。3.2 大写字母的处理思路与常见误区P1765的题面里关于大写字母的规则是需要仔细读的。题目通常会说输入句子中可能出现大小写字母而输入大写字母需要在对应的按键次数之上再加按一次“上档键”通常用*键或#键因此每个大写字母的按键次数1次上档键该字母对应的小写按键次数。很多第一次做题的同学会在这里犯迷糊要么完全忽略大写字母直接对小写字母查表然后把结果加上去结果少算了上档键要么把大写字母当成单独的一个键位去查表结果完全算错。正确的处理方式是先把大写字母转换成小写字母查表得到对应小写字母的按键次数然后再加上1次上档键。比如输入‘A’先转成‘a’查表得到a是1次按键再加1次上档键所以实际按了2次。如果你用C可以用tolower(ch)如果你用Java可以用Character.toLowerCase(ch)如果用Python直接ch.lower()。还要注意一个问题题目输入里是否包含空格和大写的组合比如“Hello World”。这种情况下大写H的处理、空格的处理、大写W的处理要分别处理不能混在一起。你需要在遍历字符串的循环里对每个字符分三种情况小写字母、大写字母、空格或句号。每种情况分别累加次数。3.3 同键分隔的特殊规则如何落实这道题最关键也最容易漏掉的规则就是“同一按键上的连续字母需要额外按键分隔”。具体来说如果当前字符和上一个字符在同一个数字键上并且两个都是字母那么需要在输入当前字符之前多按一次空格键有些题面会写按任意键分隔但按键次数上通常按1次空格键计数。这里有一个在实现上很容易出错的概念分隔键只算一次而且是算在“当前字符”头上的。也就是说如果当前字母和上一个字母同键那么当前字母的实际按键次数 1分隔键 该字母在键上的位置次数。这个规则只针对字母大部分题目里空格、句号不参与同键判断。又或者题面另有要求比如空格和某些键同键之类的特殊情况那就得严格按照题面来。P1765最常见的描述里空格不在任何字母键上所以你可以只在当前字符是字母时才检查与上一个字符的键位关系。就这个规则我见过有人把它实现成“全局加一次分隔键”结果统计出来数字总是偏大就是因为没理解“只在连续同键字符之间才算”。正确做法是维护一个变量记录“上一个字符属于哪个键”每次处理一个新字符时先判断是否和上一个字母同键再决定要不要额外加1。上面这些细节你在写代码前就要想清楚。不然等代码写完了再改往往要绕不少弯路。4. 实操过程与代码实现4.1 C 完整解法数组建表 逐字符扫描我把C的完整实现写在这里每一处关键逻辑都有注释。这是我认为最简单、最适合新手理解的写法也是我实际带学生时最推荐的版本。#include iostream #include string #include cctype using namespace std; int main() { // 按键次数表下标0-25对应a-z // 依次为 2键abc,3键def,4键ghi,5键jkl, // 6键mno,7键pqrs,8键tuv,9键wxyz int keyTimes[26] {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4}; // 每个字符所属的键位0表示不属于任何字母键(空格/句号) // 这里用2-9表示对应的数字键方便判断是否同键 int keyOfChar[26] {2,2,2, 3,3,3, 4,4,4, 5,5,5, 6,6,6, 7,7,7,7, 8,8,8, 9,9,9,9}; string s; // 用getline读取整行包含空格 getline(cin, s); int total 0; int prevKey -1; // 记录上一个字母所在的键初始为-1表示无前驱 for (int i 0; i s.size(); i) { char ch s[i]; if (ch A ch Z) { // 大写转小写 ch ch - A a; // 大写字母需要多按一次上档键 total 1; } if (ch a ch z) { int idx ch - a; int curKey keyOfChar[idx]; // 如果上一个字符也是字母且在同一键上需要按分隔键 if (prevKey curKey) { total 1; // 分隔键 } total keyTimes[idx]; prevKey curKey; } else if (ch ) { total 1; // 空格按一次 prevKey -1; // 空格不参与同键判断 } else if (ch .) { total 1; // 句号按一次 prevKey -1; } } cout total endl; return 0; }这里有几个值得强调的设计决策。我专门增加了一个keyOfChar数组用来记录每个字母属于哪个数字键。可能有同学会说“我已经有keyTimes了判断同键的时候直接把相邻字母比较一下不就好了”不行因为比较同键不等于比较按键次数。比如a是1次、d也是1次但它们不在同一个键上这就是为什么必须要有一个独立的键位表而不是复用按键次数表。如果你想省内存也可以直接把同一个键的字母用区间判断比如判断两个字母是否都在a-c或者都在d-f之间但那样代码分支会多不少。用一张键位表是一个很清晰的工程化选择。另一个值得注意的点是prevKey的维护。当遇到空格或句号时我会把prevKey重置为-1这是因为空格和句号本身不参与同键判断。如果不重置就可能出现“o空格p”这种场景——o和p其实不同键不加分隔没问题但如果“a空格b”a和b都在2键上实际输入时因为中间隔着空格它们不需要分隔键。如果不重置prevKey程序就会误判a和b同键而多加一次按键。4.2 Java 解法代码对比与要点说明在Java里读整行用BufferedReader或者Scanner.nextLine()都很方便。我给出一版Java实现逻辑与C版本完全一致但写法上更贴近Java习惯。import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String s br.readLine(); int[] keyTimes {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4}; int[] keyOfChar {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9}; int total 0; int prevKey -1; for (int i 0; i s.length(); i) { char ch s.charAt(i); if (ch A ch Z) { ch Character.toLowerCase(ch); total 1; } if (ch a ch z) { int idx ch - a; int curKey keyOfChar[idx]; if (prevKey curKey) { total 1; } total keyTimes[idx]; prevKey curKey; } else if (ch ) { total 1; prevKey -1; } else if (ch .) { total 1; prevKey -1; } } System.out.println(total); } }用BufferedReader而不是Scanner是因为在竞赛环境中BufferedReader的速度更快处理一行包含空格的输入也更干净利落。这里要小心的是br.readLine()如果输入为空会读到null但洛谷的题目保证输入至少有一行所以这里不用做额外判空。Java版本里将大写转小写用的是Character.toLowerCase(ch)其实直接ch 32也可以但可读性差而且容易在字符编码上产生误解。我建议还是用标准库函数。4.3 Python 解法简洁但不失严谨Python处理这种字符串题目非常舒服代码量最少。但要注意的是Python对字符和数字的转换跟C不一样需要用ord()函数。下面是完整的Python实现。s input() key_times [1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4] key_of_char [2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9] total 0 prev_key -1 for ch in s: if A ch Z: ch ch.lower() total 1 if a ch z: idx ord(ch) - ord(a) cur_key key_of_char[idx] if prev_key cur_key: total 1 total key_times[idx] prev_key cur_key elif ch : total 1 prev_key -1 elif ch .: total 1 prev_key -1 print(total)Python里要注意input()读取一行时是不包含末尾换行符的这样正好。还有一个容易踩的坑如果你在本地测试时输入里包含多个连续空格input()会原样保留这正好符合题目要求。千万不要用split()去预处理输入那会把空格全部切割掉导致结果完全不对。4.4 三个版本放在一起对比为了让你看得更清楚我把三种语言实现的核心差异整理成一张表对比项CJavaPython读入一行含空格getline(cin, s)br.readLine()input()大写转小写ch ch - A a 或 tolowerCharacter.toLowerCase(ch)ch.lower()字符转下标ch - ach - aord(ch) - ord(a)建表方式两个int数组两个int数组两个list运行速度最快较快相对较慢就这道题的数据量而言三种语言的性能差异完全可以忽略因为总共只需要遍历一遍字符串时间复杂度是O(n)n是字符串长度。但如果你今后要打竞赛建议C或Java至少掌握一种因为它们在处理更复杂的数据规模时更从容。5. 常见问题与排查技巧实录5.1 读入问题getline和cin混用的经典大坑我在答疑的时候发现很多同学P1765提交不过问题出在“读入字符串”上。最经典的错误写法是先用cin n之类的东西读了一个数字然后再用getline(cin, s)读字符串。这会导致getline读到一个残留的换行符从而什么都读不到或者读到一个空字符串。在P1765里虽然没有前置数字输入但不少同学在本地测试时喜欢先写一个“请输入测试次数”之类的操作结果就把自己带沟里了。如果你确实需要先读数字再读含空格的字符串必须在两者之间加一个cin.ignore()来吃掉换行符。例如int t; cin t; cin.ignore(); while (t--) { string s; getline(cin, s); // 处理s }这是一个重要的通用经验我在很多入门题里都见过类似的坑尤其是那些需要读取多行含空格字符串的题目。尽早养成“cin之后如果需要getline就加ignore”的意识能帮你免掉无数调试时间。5.2 空格与句号的特殊处理为什么我老是多算或少算有同学遇到这种现象自己的程序对于没有空格的字符串测试都对了但只要输入里出现空格答案就不对。排查下来往往出在空格被忽略或空格被当成普通字符处理上。产生这个问题的原因通常是用了cin s读入导致字符串从空格处断开后面的所有字符全都没被处理。比如输入“hello world”cin s只会读进“hello”后面“world”直接被丢弃了。这种错误在本地调试时特别有迷惑性因为你可能只输入了没有空格的测试用例自然发现不了问题。正确做法就是前文用的getline(cin, s)或者input()。如果你已经用了正确的方式读入但结果还是不对那就检查一下循环里对空格是否分了一支出来单独累加1。要注意的是别把空格也放进查表函数里去查否则可能查出一个任意的数值。另外还有一个关于句号的坑有些题面的规则里句号和空格都在1键按一次但有些变体题里句号可能要按好几次。P1765按一次即可。如果你是根据记忆写的代码最好回题面里确认一下句号的按键次数。5.3 同键分隔最容易漏掉的那1次按键同键分隔这个规则是P1765的区分度所在。我见过的错误五花八门但可以归结为两类。一类是完全不知道这个规则所以代码里根本没有判断同键的逻辑。这种提交通常会在隐含有连续同键字母的测试点上挂掉比如“good”中的“o”和“o”就是同键需要分隔键但如果你没实现按出来的次数就会比标准答案少1。另一类是过度实现了这个规则比如对每一对相邻字母都判断了一次甚至对空格和字母也判断了一次。这会导致按键次数偏多。比如“a b”这种情况a和b虽然都在2键上但中间隔了一个空格输入时不需要分隔键。如果你不对“空格”做特殊处理很容易把a和b判断为需要加一次分隔键从而多算。处理这个问题的统一思路就是我在正确代码里写的维护一个prevKey变量在遇到空格或句号时重置为-1。这样既不会漏掉真正的同键分隔又不会对跨空格的两个字母误判。5.4 边界情况全空格、大写跳跃、空行等如果你想让代码更稳健可以额外测试这些边界情况输入全是空格比如“ ”此时每个空格按一次程序应该能正确输出空格数量。输入“A”大写字母需要上档键加1加第一次按键共2次。输入“Z”z的按键次数是4再加上1次上档键共5次。输入“aA”a在2键第1位按1次A按上档键1次加a的1次再加2键上连续输入需要分隔1次共11114次。输入只有一句号“.”输出1。这些边界情况在洛谷的测试点里不一定都出现但自己做一遍可以大大增强对题意的理解。5.5 本地调试小技巧构造随机输入对比如果你想更高效地自测可以写一个“暴力校检验证器”先用一个逻辑很简单但不够优雅的方法算出结果比如直接手写分支判断每个字符的按键次数再用你的程序运行同一个输入两个结果对比不一致就可以定位问题。这个方法适用于几乎所有入门题和部分中档题是我个人非常推荐的自我检测手段。手动构造测试用例时也可以刻意设计一些包含连续同键字母的句子比如“see you soon”或者大小写混合的句子“I Am OK.”这些句子最能暴露分隔规则处理是否到位。6. 从P1765出发同类型题的泛化能力6.1 这类“模拟生活规则”题在竞赛中的定位P1765属于典型的“模拟字符串”题型。在洛谷的题目体系中这类题通常被标记为普及-/入门难度但它的思想会延伸到更高难度的问题中。比如P1843、P14258这类题目名里包含字符串处理的题很多都是P1765的变体给出一套复杂的规则要求你严格模拟最终计算某种结果。在算法竞赛里“模拟”类题目占据了不小的比例。它们看似简单实则非常考验做题的细致程度。很多选手在平时训练时对模拟题不以为然觉得“只要照着题意敲代码就行”但一到正式比赛往往是在模拟题上因为漏看条件而丢分。P1765作为一道经典的模拟题最大的价值就是帮你训练“读题细、规则全、边界清”的做题习惯。从技巧角度看这道题体现的思想是“空间换时间”——与其在每次判断时都重新计算按键次数不如提前把映射关系存好。这其实是竞赛中最常用的优化手段之一。很多看似复杂的题目一张预处理的表就能把问题从“每次现算”变成“查表即可”大幅降低出错率。6.2 变体题从九宫格到其他映射场景如果你想把这道题吃透可以做几个很有意思的变体练手。第一个变体是“键盘改成双拼/全拼输入法”规则会变成一个字母可能对应多个组合键计算方式会从“按键次数”变成“组合键数”但核心思想仍然是查表模拟。第二个变体是“计算某段电话号码对应的按键次数”题目会给你一个电话号码包括数字、*、#等符号规则会更复杂但同样可以用一个映射表把所有符号的按键次数存起来。第三个变体是“数字转字母的组合输出”也就是给定一串数字让你求所有可能的字母组合。这个题目就变成了回溯算法题虽然和P1765的模拟目标不一致但它让你意识到“按键与字母映射”这个模型可以产生出完全不同的算法问题。我在带新人时常让他们把P1765的代码拿去做这些变体既能巩固基础知识又能提前预览后续要学的高级算法。这种“一题多练”的方法比单纯刷题效率高得多。6.3 我个人的做题体会这道题我做了不止一次每次都会有不同的感触。第一次做的时候我用的是最朴素的逐个字符if-else判断代码写了一长串好不容易过了。后来再用映射表法才意识到“表驱动”这种思想的威力——很多代码里的复杂逻辑本质上是把一张表硬生生写成了if-else。如果你想让自己的代码风格更进一步可以试试“表驱动函数封装”的写法。把“判断一个字符要按几次键”单独封装成一个函数返回按键次数主循环只负责读字符和累加。这种拆分的代码更清晰以后遇到类似逻辑可以直接复用函数。说到底P1765只是众多入门题中的一颗小珍珠但它是很多同学第一次体会到“规则模拟”乐趣的地方。如果有同学能把这道题完全吃透理解查表、边界、读入处理这几个要点后面刷再难的模拟题都会从容很多。
阅读完成 · 觉得有帮助？
)
