首页 > 代码库 > POJ 2418 Hardwood Species（字典树）

POJ 2418 Hardwood Species（字典树）

2024-07-04 17:59:20   224人阅读

题目链接：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 }
View Code

然后是用了字典树的：

 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 }
View Code

 


联系
我们