首页 > 代码库 > POJ 1002 487-3279 Trie题解
POJ 1002 487-3279 Trie题解
本题的解法是多种多样的,这里使用Trie来解决一下。
也可以使用hash表,map等解法,因为输入是特定的7位数字,故此应该都可以解决的。
这里使用Trie的速度并不快,主要是因为最后我直接遍历输出,遍历整个Trie的速度还是比较慢的。
思路:
1 使用insert函数建立Trie,主要增加一个叶子节点的信息,记录当前有多少个重复的字符串
2 遍历就是根据叶子节点的信息决定是否需要输出。
#include <stdio.h> #include <iostream> #include <string> using namespace std; const int ARR_SIZE = 10; struct Node { int n; Node **alpha; Node() : n(0) { alpha = new Node*[ARR_SIZE]; for (int i = 0; i < ARR_SIZE; i++) alpha[i] = NULL; } ~Node() { for (int i = 0; i < ARR_SIZE; i++) { if (alpha[i]) delete alpha[i]; alpha[i] = NULL; } delete alpha; alpha = NULL; n = 0; } }; Node *Trie; void insertTrie(string &s) { Node *pCrawl = Trie; for (unsigned i = 0; i < s.size(); i++) { int id = s[i] - '0'; if (pCrawl->alpha[id] == NULL) { pCrawl->alpha[id] = new Node; } pCrawl = pCrawl->alpha[id]; } pCrawl->n++; //增加一个字符串数量 } inline char charToNum(char a) { switch (a) { case 'A': case 'B': case 'C': return '2'; case 'D': case 'E': case 'F': return '3'; case 'G': case 'H': case 'I': return '4'; case 'J': case 'K': case 'L': return '5'; case 'M': case 'N': case 'O': return '6'; case 'P': case 'R': case 'S': return '7'; case 'T': case 'U': case 'V': return '8'; case 'W': case 'X': case 'Y': return '9'; } return char('9'+1); //There is no mapping for Q or Z.uppercase letters (excluding Q and Z) } char lookUpTable[26]; void initLookUpTable() { for (int i = 0; i < 26; i++) { lookUpTable[i] = charToNum(char(i+'A')); } } void strToNum(string &s) { int j = -1; for (unsigned i = 0; i < s.size(); i++) { if (s[i] != '-') { s[++j] = s[i];//错误:s[j++] = s[i];j已经变化,下面还是用j if ('A' <= s[j] && s[j] <= 'Z') { s[j] = lookUpTable[s[j]-'A']; } } } s.resize(j+1); } bool flag; void printRepeat(Node *r, string &path) { if (r->n >= 1) { if (r->n == 1) return ; flag = true; unsigned i = 0; for ( ; i < 3; i++) putchar(path[i]); putchar('-'); for ( ; i < 7; i++) putchar(path[i]); putchar(' '); printf("%d\n", r->n); return ; } for (int i = 0; i < ARR_SIZE; i++)//in ascending lexicographical order { path += char(i+'0'); if (r->alpha[i]) printRepeat(r->alpha[i], path); path.erase(path.size()-1); } } int main() { initLookUpTable(); int N; scanf("%d", &N); getchar(); string s; char chs[100]; Trie = new Node; while (N--) { gets(chs); s = chs; strToNum(s); insertTrie(s); } flag = false; string path; printRepeat(Trie, path); if (!flag) puts("No duplicates."); delete Trie; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。