题目描述有一个键盘其中 2 个按键失灵了按下这两个键时屏幕会连续输出别的字符两次按下j键一次屏幕显示uu两个连续的 u按下b键一次屏幕显示tt两个连续的 tu键和t键本身是好的按一次只显示一个字符。从屏幕输出还原按键的规则屏幕上连续两个t一定是按了一次b而不是按了两次t屏幕上连续两个u一定是按了一次j而不是按了两次u按t之后不会紧接着按b所以ttt解码成两次b而不是tbtu和j同理uuu解码成两次j其他按键都正常维修师傅的要求给定屏幕上输出的字符串统计每个按键被按下的次数只统计次数大于 0 的按键按次数降序输出次数相同的按按键对应字符升序排失灵按键按原字符排也就是b按b、j按j输出时还要做一次字符转义按键0~9输出0~9按键a~z输出10~35a10b11…z35输入一个字符串s只含小写字母和数字长度不超过 500且s中不含b和j。输出[转义值, 按键次数]组成的二维数组按次数降序、次数相同按转义值升序排列。示例 1输入aauutthello输出[[10,2],[21,2],[11,1],[14,1],[17,1],[19,1],[24,1]]补充说明原题文件在示例输出处截断上面的示例输出按规则还原。ttt会解码成两次buuu解码成两次j。讲个故事小张的串键键盘小张的键盘泼了杯水b键和j键串键了。按b出来tt按j出来uu其他键都好好的。他闭着眼敲了一通屏幕上留下一串字符。维修师傅拿到这串字符得反推他到底按了多少次键每个键各按了几下。小张指着屏幕上的ttt问这到底是按了几次b师傅一拍桌子3 个t是 2 次b因为按完t不会再紧接按b单个t没法夹在b中间。核心原理连续字符压缩 转义排序这道题分三步解码、转义、排序。第一步解码。关键是处理t和u这两种字符其他字符按一次算一次直接计数。t的规则屏幕上连续两个t就是 1 次b连续三个tttt是 2 次b。规律很直接连续 L 个t等于 L-1 次b相当于重叠着数相邻的tt对有几对就是几次b。题目里按t之后不会紧接按b这条就是为了排除tbt这种夹着单独t的拆法。只有孤零零一个t前后都不是t才算 1 次t。u和j一模一样连续 L 个u是 L-1 次j单个u是 1 次u。说白了ttt里有 2 对tt位置 0-1 和 1-2所以是 2 次b。第二步转义。每个按键字符映射成一个数字0~9映射到0~9a~z映射到10~35公式记一下数字字符直接减0字母字符减a再加 10。比如b是 11j是 19t是 29o是 24。第三步排序。先按次数从大到小排次数一样的按转义值从小到大排。失灵按键按它自己的原字符排b就是b、j就是j而转义值本来就是按字符算的所以直接拿转义值升序兜底就行。拿示例aauutthello走一遍aa→a按 2 次uu→ 连续 2 个u1 次jtt→ 连续 2 个t1 次bhello→h、e、l、l、o各按 1 次其中l是 2 次按键次数a2、l2、b1、e1、h1、j1、o1。转义值a10、l21、b11、e14、h17、j19、o24。排完序[[10,2],[21,2],[11,1],[14,1],[17,1],[19,1],[24,1]]。怎么实现读入字符串s用一个指针从左往右扫遇到t或u就向右数出连续段的长度 LL 等于 1这个字符本身按 1 次L 大于等于 2对应失灵键按 L-1 次t对应bu对应j其他字符直接按 1 次累加把每个按键转义成数字按次数降序、转义值升序排序拼成二维数组输出代码实现C 语言#includestdio.h#includestring.h#includestdlib.htypedefstruct{intval;intcnt;}Pair;intescapeVal(charc){if(c0c9)returnc-0;returnc-a10;}intcmpPair(constvoid*a,constvoid*b){constPair*xa,*yb;if(x-cnt!y-cnt)returny-cnt-x-cnt;// 次数降序returnx-val-y-val;// 转义值升序}intmain(){staticchars[505];if(scanf(%504s,s)!1)return0;intn(int)strlen(s);intcnt[128];memset(cnt,0,sizeof(cnt));inti0;while(in){charcs[i];if(ct||cu){intji;while(jns[j]c)j;intLj-i;if(L1)cnt[(int)c]1;// 单个 t/uelsecnt[(int)(ct?b:j)](L-1);// L-1 次 b/jij;}else{cnt[(int)c]1;i;}}Pair pairs[128];intm0;for(intk0;k128;k){if(cnt[k]0){pairs[m].valescapeVal((char)k);pairs[m].cntcnt[k];m;}}qsort(pairs,m,sizeof(Pair),cmpPair);printf([);for(intk0;km;k){if(k)printf(,);printf([%d,%d],pairs[k].val,pairs[k].cnt);}printf(]\n);return0;}C#includebits/stdc.husingnamespacestd;intescapeVal(charc){if(c0c9)returnc-0;returnc-a10;}intmain(){string s;cins;intns.size();mapchar,intcnt;inti0;while(in){charcs[i];if(ct||cu){intji;while(jns[j]c)j;intLj-i;if(L1)cnt[c];elsecnt[(ct)?b:j](L-1);ij;}else{cnt[c];i;}}vectorpairint,intpairs;// (转义值, 次数)for(autop:cnt)if(p.second0)pairs.push_back({escapeVal(p.first),p.second});sort(pairs.begin(),pairs.end(),[](constpairint,inta,constpairint,intb){if(a.second!b.second)returna.secondb.second;returna.firstb.first;});cout[;for(size_t k0;kpairs.size();k){if(k)cout,;cout[pairs[k].first,pairs[k].second];}cout]endl;return0;}Javaimportjava.util.*;publicclassMain{staticintescapeVal(charc){if(c0c9)returnc-0;returnc-a10;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);if(!sc.hasNext())return;Stringssc.next();intns.length();MapCharacter,IntegercntnewHashMap();inti0;while(in){charcs.charAt(i);if(ct||cu){intji;while(jns.charAt(j)c)j;intLj-i;if(L1)cnt.merge(c,1,Integer::sum);elsecnt.merge((ct)?b:j,L-1,Integer::sum);ij;}else{cnt.merge(c,1,Integer::sum);i;}}Listint[]pairsnewArrayList();for(Map.EntryCharacter,Integere:cnt.entrySet())if(e.getValue()0)pairs.add(newint[]{escapeVal(e.getKey()),e.getValue()});pairs.sort((a,b)-{if(a[1]!b[1])returnb[1]-a[1];returna[0]-b[0];});StringBuildersbnewStringBuilder([);for(intk0;kpairs.size();k){if(k0)sb.append(,);sb.append([).append(pairs.get(k)[0]).append(,).append(pairs.get(k)[1]).append(]);}sb.append(]);System.out.println(sb);}}JavaScriptfunctionescapeVal(c){if(c0c9)returnc.charCodeAt(0)-48;returnc.charCodeAt(0)-9710;}functionsolve(s){constns.length;constcnt{};constadd(k,v){cnt[k](cnt[k]||0)v;};leti0;while(in){constcs[i];if(ct||cu){letji;while(jns[j]c)j;constLj-i;if(L1)add(c,1);elseadd(ct?b:j,L-1);ij;}else{add(c,1);i;}}constpairsObject.keys(cnt).filter(kcnt[k]0).map(k[escapeVal(k),cnt[k]]);pairs.sort((a,b)(a[1]!b[1])?b[1]-a[1]:a[0]-b[0]);return[pairs.map(p[${p[0]},${p[1]}]).join(,)];}constreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin});rl.on(line,(line){console.log(solve(line.trim()));rl.close();});Pythondefescape_val(c):if0c9:returnord(c)-ord(0)returnord(c)-ord(a)10defsolve(s):cnt{}i,n0,len(s)whilein:cs[i]ifcin(t,u):jiwhilejnands[j]c:j1Lj-iifL1:cnt[c]cnt.get(c,0)1else:keybifctelsejcnt[key]cnt.get(key,0)(L-1)ijelse:cnt[c]cnt.get(c,0)1i1pairs[(escape_val(k),v)fork,vincnt.items()ifv0]pairs.sort(keylambdax:(-x[1],x[0]))return[,.join(f[{val},{times}]forval,timesinpairs)]sinput().strip()print(solve(s))复杂度分析扫描字符串O(n)n 最大 500统计按键最多 36 种按键常数级排序O(36 * log 36)常数级总时间复杂度O(n)空间复杂度O(1)按键种类固定数据规模小怎么写都过重点是解码那段连续字符的处理。总结一下失灵的键盘 连续字符压缩 转义 排序。几个坑记一下b和j不会出现在输入里它们是解码出来的连续 L 个t是 L-1 次b不是 L/2 次ttt就是 2 次b单个t前后都不是t才算 1 次tu同理排序兜底用转义值升序失灵键按原字符排正好对应转义值下次看到屏幕输出还原按键这种题先想清楚哪些字符是失灵键撑出来的剩下的就是按一次算一次。你遇到过最绕的字符串解码题是哪道欢迎在评论区聊聊。