必须要批评下自己了,首先就是这个题目的迟疑不定,去年做字典树的时候就碰到这个题目了,当时没什么好的想法,就暂时搁置了,其实想法应该有很多,只是居然没想到。
同样都是对单词进行建树,并插入可能值,但是拨号键盘上的字母是对应多个的,给定拨号序列,有多种可能情况 输出其中最可能的一种,肯定要想到搜索啊,而且拨号数目不超过100,每个按键最多只对应4个字母,复杂度并不高,所以用dfs是可行的,对于每次递归深度,dfs找到最大的可能值的情况并输出。
接下来就是要批评自己了,下午一点钟开始做这个题目,居然被一个小bug搞了一个多小时,都没过样例,就是我的dfs写挫了,而且我迟迟没找到原因。。。真的要反省自己的代码编写能力了。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int tot; char s[110]; char press[10][5]; char num[110]; int ansd; char anss[110],finds[110]; bool flag; struct node { node* ch[27]; int cur,deep; } tree[200000]; node* newNode() { node* p; p=&tree[tot++]; for (int i=0;i<27;i++) { p->ch[i]=NULL; } p->cur=0; p->deep=0; return p; } void insertn(node* root,char* s1,int fee) { node* p=root; int i=0,k; //puts(s1); while (s1[i]) { k=s1[i]-'a'; if (p->ch[k]==NULL) { //cout<<s1[i]<<" "<<p->deep<<endl; p->ch[k]=newNode(); } p->ch[k]->deep=i++; p->ch[k]->cur+=fee; p=p->ch[k]; } } void init() { strcpy(press[2],"abc"); strcpy(press[3],"def"); strcpy(press[4],"ghi"); strcpy(press[5],"jkl"); strcpy(press[6],"mno"); strcpy(press[7],"pqrs"); strcpy(press[8],"tuv"); strcpy(press[9],"wxyz"); } void dfs(node* rt,char* s1,int maxd,int d) { node* p=rt; if (d==maxd) { if (p->cur>ansd){ flag=1; ansd=p->cur; for (int i=0;i<d;i++) anss[i]=finds[i]; anss[d]='