本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P3864 [USACO1.2] 命名那个数字 Name That Number【题目描述】在威斯康辛州牛守志大农场经营者之中都习惯于请会计部门用连续数字给母牛打上烙印。但是,母牛本身并没感到这个系统的便利,它们更喜欢用它们喜欢的名字来呼叫它们的同伴而不是用像这个的语句“C’mon, #4364, 相处愉快。”请写一个程序来帮助可怜的牧牛工将一只母牛的烙印编号翻译成一个可能的名字。因为母牛们现在都有手机了可以按照下表来转换数字为字母数字对应字母2 22A,B,C3 33D,E,F4 44G,H,I5 55J,K,L6 66M,N,O7 77P,R,S8 88T,U,V9 99W,X,Y请注意没有字符Q和字符Z。牛群们可接受的名字都被放在这样一个叫作 “dict.txt” 的文件中它包含一连串的少于5000 50005000个准确地说是4617 46174617个可被接受的牛的名字。(所有的名字都是大写的且已按字典序排列) 请读入母牛的编号并返回那些能从编号翻译出来并且在字典中的名字。举例来说编号4734 47344734能产生的81 8181个名字中只有一个 “GREG” 是有效的在字典中。写一个程序来对给出的编号打印出所有的有效名字如果没有则输出NONE。【输入】第一行一行包含一个编号长度1 11到12 1212。接下来若干行每行一个字符串表示可以被接受的名字。【输出】以字典顺序输出一个有效名字的不重复列表一行一个名字。如果没有有效名字输出NONE。【输入样例】4734 NMSL GREG LSDC ....(太多了不写了)【输出样例】GREG【核心思想】问题分析给定一个数字编号长度1 ∼ 12 1 \sim 121∼12每个数字对应3 33个字母如2 → A , B , C 2 \to A,B,C2→A,B,C。要求找出所有由该编号翻译出的字母组合中存在于给定字典4617 46174617个名字里的有效名字按字典序输出。算法选择DFS 枚举所有组合对每个数字位的3 33个字母进行深度优先搜索生成所有可能的字符串哈希表快速查询用mapstring, int存储字典实现O ( 1 ) O(1)O(1)查询生成的字符串是否在字典中剪枝优化生成完整字符串后才查字典无法中途剪枝因字典无序但3 12 531441 3^{12} 531441312531441可接受关键步骤读入编号字符串s ss长度n nn存入数组a [ 1.. n ] a[1..n]a[1..n]建立字典读入4617 46174617个名字用mp[name] 1标记存在定义字母映射表c[10][3]2 ∼ 9 2 \sim 92∼9各对应3 33个大写字母DFS 函数dfs(step, t)step当前处理到第几位从1 11开始t当前已构建的字符串前缀若step n生成完毕若mp[t]存在则输出并标记flag true否则取出当前位数字num a[step]枚举i ∈ [ 0 , 2 ] i \in [0, 2]i∈[0,2]递归dfs(step1, t c[num][i])输出判断若flag仍为false输出NONE时间/空间复杂度时间复杂度O ( 3 n ) O(3^n)O(3n)枚举所有字母组合n ≤ 12 n \le 12n≤12时最大531441 531441531441空间复杂度O ( 4617 ) O(4617)O(4617)字典哈希表存储DFS 枚举 哈希查询的核心思想数字到字母的映射每个数字固定对应3 33个字母无歧义直接查表全排列生成DFS 按位展开形成一棵三叉树叶子节点即为所有可能的3 n 3^n3n个字符串哈希判存在用map将字典查询优化到O ( 1 ) O(1)O(1)避免线性查找字典序自然保证DFS 按字母表顺序c[num][0], c[num][1], c[num][2]枚举生成的字符串天然按字典序适用于密码翻译、组合枚举、字典匹配类问题【算法标签】#普及 #DFS-一维【代码详解】#includebits/stdc.husingnamespacestd;constintN15;// 定义数组最大容量为15编号最长12位inta[N],n;// a[i]存储编号第i位的数字n为编号长度mapstring,intmp;// mp存储字典中的所有名字用于O(1)查询// c[num][i]表示数字num对应的第i个字母num从2到9i从0到2charc[10][3]{{},{},{A,B,C},{D,E,F},{G,H,I},{J,K,L},{M,N,O},{P,R,S},{T,U,V},{W,X,Y}};boolflag;// flag标记是否找到至少一个有效名字// 深度优先搜索枚举编号每个数字对应的所有字母组合// step当前处理到第step位从1开始// t当前已构建的字符串前缀voiddfs(intstep,string t){if(stepn)// 如果已经处理完所有数字位{// cout t t endl; // 注释掉的调试输出if(mp[t])// 如果当前字符串t在字典中存在{couttendl;// 输出该有效名字flagtrue;// 标记找到了有效名字}return;// 递归返回}intnuma[step];// 取出当前位对应的数字for(inti0;i3;i)// 枚举该数字对应的3个字母{dfs(step1,tc[num][i]);// 递归到下一层将当前字母加入字符串}}intmain(){string s;cins;// 读入母牛的编号字符串ns.size();// 计算编号长度for(inti1;in;i)// 将编号字符串转换为数字数组a[i]s[i-1]-0;// s[0]对应a[1]以此类推for(inti1;i4617;i)// 读入4617个字典中的名字{string s;cins;mp[s]1;// 将名字加入字典映射}dfs(1,);// 从第1位开始DFS初始字符串为空if(!flag)// 如果没有找到任何有效名字coutNONEendl;// 输出NONEreturn0;}【运行结果】4734 NMSL GREG LSDC .... GREG