2019獨角獸企業重金招聘Python工程師標準>>>

???? 這是一個類似于查字典的問題。已知一本“字典”中包含了一些英文單詞（5000個左右，單詞長度為1~12位），又已知一種對應關系，數字2~9共對應除去Q和Z的24個英文字母，每個數字可對應3個英文字母，如2可對應A,B,C，也就是說A,B,C均可用2表示。那給你一個n位的數字，這個數字可以表示的單詞就有3^n種。現題目給定一個1~12位長的數字，要求輸出在字典中存在的這個數字所對應成的所有單詞。

???? 由于字典中包含的單詞數量不多，我們可以先將單詞讀入內存，然后一一比較。但這種做法肯定不是最好的，如果單詞的個數很多的話，那肯定花的時間會增大，這種方法必須把每個字典里的每個單詞都比較一次。

????? 想到用哈希查找的方法，可以以數字為關鍵字key,f=key%5000作為哈希函數，定義數組arr[5000]，將關鍵字為key的單詞全都存到以arr[f]為頭結點的鏈表中，這樣的話每次查詢都可以直接定址到key%5000,大大減少查詢時間。寫了好久，最后終于通過了。

?

/* ID: whutzha1 PROG: namenum LANG: C++ */ #include<fstream> using namespace std; ifstream cin("namenum.in"); ifstream fin("dict.txt"); ofstream cout("namenum.out");struct Node {char name[13];long long num;Node *next; };int main() {Node *arr[5000];int i;for (i=0;i<5000;i++){arr[i]=NULL;}//讀dict.txt文件char read_name[13];long long read_num;int area;int n;char ch;while(fin.get(ch)){for (i=0;i<13;i++){while(ch==' '||ch=='\n'){ fin.get(ch); }read_name[i]=ch;fin.get(ch);if (ch==' '||ch=='\n')break; }read_name[i+1]='\0';read_num=0;for(i=0;i<12;i++){switch(read_name[i]){case 'A':case 'B':case 'C': n=2;break;case 'D':case 'E':case 'F': n=3;break;case 'G':case 'H':case 'I': n=4;break;case 'J':case 'K':case 'L': n=5;break;case 'M':case 'N':case 'O': n=6;break;case 'P':case 'R':case 'S': n=7;break;case 'T':case 'U':case 'V': n=8;break;case 'W':case 'X':case 'Y': n=9;break;default: break;}read_num=(read_num*10+n);if (i==11||read_name[i+1]=='\0') {area=read_num%5000;Node *p=(Node *)malloc(sizeof(Node));if (arr[area]==NULL) {arr[area]=p;}else {Node *q=arr[area];Node *r;while (q){r=q;q=q->next;}r->next=p;}p->num=read_num;p->next=NULL;for (i=0;i<13;i++){p->name[i]=read_name[i];if (p->name[i]=='\0'){break;}}break;}} }//while long long num;bool flag;cin>>num;Node *p;p=arr[num%5000];flag=false;while(p){if (p->num==num){flag=true;// for(i=0;i<12;i++)// {// cout<<p->name[i];// if (p->name[i+1]=='\0')// {cout<<endl;break;} // }cout<<p->name<<endl;}p=p->next;}if (!flag) {cout<<"NONE"<<endl;}return 0; }

轉載于:https://my.oschina.net/u/585691/blog/71996

總結

以上是生活随笔為你收集整理的1.2 Name That Number的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。