首页 > 代码库 > POJ 2418 Hardwood Species(字典树)
POJ 2418 Hardwood Species(字典树)
题目链接:POJ 2418 Hardwood Species
【题意】给出一大串树的名字,可能有重复,然后按字典序输出名字和百分比。
【思路】我已开始偷懒用了map来做,这道题给的时间是10s,用map的8s也还是水过了,真是神奇啊,后来还是写了一下字典树,700ms+就过了,效率提升显著啊。这里要注意的是建字典树的ChildSize是256,题目输入不只有字母,还有一些其它字符。
下面贴上代码,先是map的:
1 /* 2 ** POJ 2418 Hardwood Species 3 ** Created by Rayn @@ 2014/04/30 4 ** 用map水看看 5 */ 6 #include <cstdio> 7 #include <iostream> 8 #include <string> 9 #include <map> 10 #include <algorithm> 11 using namespace std; 12 13 int main() 14 { 15 string str; 16 int cnt = 0; 17 map<string, int> tree; 18 while(getline(cin, str)) 19 { 20 tree[str]++; 21 cnt++; 22 } 23 map<string, int>::iterator i; 24 for(i = tree.begin(); i != tree.end(); ++i) 25 { 26 cout << i->first; 27 printf(" %.4f\n",(i->second*100.0) / cnt); 28 } 29 return 0; 30 }
然后是用了字典树的:
1 /* 2 ** POJ 2418 Hardwood Species 3 ** Created by Rayn @@ 2014/05/01 4 ** Trie树 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <cstdlib> 9 10 const int ChildSize = 256; 11 12 int tot; 13 14 struct TrieNode { 15 int val; /* 用于记录单词出现的次数*/ 16 TrieNode *child[ChildSize]; /* 分支节点的孩子指针 */ 17 }; 18 TrieNode *InitTrie() 19 { 20 return (TrieNode*)calloc(1, sizeof(TrieNode)); 21 } 22 void Insert(TrieNode *root, char *word) 23 { 24 TrieNode *now = root; 25 26 for(char *p=word; *p; p++) 27 { 28 int v = *p; 29 if(now->child[v] == 0) 30 { 31 now->child[v] = (TrieNode*)calloc(1, sizeof(TrieNode)); 32 } 33 now = now->child[v]; 34 } 35 //到达记录统计单词次数的节点 36 now->val++; 37 } 38 void Search(TrieNode *root) 39 { 40 static char tmp[31]; 41 static int pos; 42 43 if(root->val) 44 { 45 tmp[pos] = ‘\0‘; 46 if(tmp[0]) 47 { 48 printf("%s %.4f\n", tmp, (root->val*100.0)/tot); 49 } 50 } 51 for(int i=0; i<256; ++i) 52 { 53 if(root->child[i]) 54 { 55 tmp[pos] = i; 56 pos++; 57 Search(root->child[i]); 58 pos--; //回溯 59 } 60 } 61 } 62 int main() 63 { 64 char word[31]; 65 TrieNode *root; 66 67 tot = 0; 68 root = InitTrie(); 69 while(gets(word)) 70 { 71 Insert(root, word); 72 tot++; 73 } 74 Search(root); 75 return 0; 76 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。