单链DNA

换了个地址：http://www.cnblogs.com/vizhen/

 

HDOJ 1671 Phone List

题目传送门

简要分析字典树问题。但是要释放内存，否则会MLE.... = =!


代码
 1 #include <iostream>
 2 
 3 bool flag=false;//重复标记
 4 const int MAXSIZE=10;
 5 struct Trie
 6 {
 7     int tail;//标记结束
 8     int count;//标记频率
 9     Trie *next[MAXSIZE];
10     Trie()
11     {
12         tail=0;
13         count=1;
14         for (int i=0;i<MAXSIZE;i++)
15         {
16             next[i]=NULL;
17         }
18     }
19 };
20 
21 //建树扩展：当有结尾的点出现频率大于1次表示有重复
22 void InsertWorldEx(Trie* &root,char *world)
23 {
24     Trie *location=root;
25     int i=0,branch=0,len;
26 
27     len=strlen(world);
28     while (world[i])
29     {
30         branch=world[i]-'0';
31         if(location->next[branch]==NULL)
32              location->next[branch]=new Trie;
33         else
34         {
35             location->next[branch]->count++;
36         }
37         
38         if(i==len-1)  location->next[branch]->tail=1;
39         
40         //标记已经有前缀重复
41         if(location->next[branch]->tail==1&&location->next[branch]->count>1)
42             flag=true;
43         
44         i++;
45         location=location->next[branch];
46     }      
47 }
48 int del(Trie* &root)
49 {
50     int i;
51     if(root==NULL)
52         return 0;
53     for (i=0;i<MAXSIZE;i++)
54     {
55         if(root->next[i]!=NULL)
56             del(root->next[i]);
57     }
58     free(root);
59     return 0;
60 }
61 
62 int main()
63 {
64     int t;
65     scanf("%d",&t);
66     while(t--)
67     {
68         int num;
69         char phone[20];
70         Trie *root=new Trie;
71         flag=false;
72 
73         scanf("%d",&num);
74         for (int i=0;i<num;i++)
75         {
76             scanf("%s",phone);
77             if(flag==false) InsertWorldEx(root,phone);
78         }
79 
80         if(flag) printf("NO\n");
81         else printf("YES\n");
82         del(root);
83     }
84     return 0;
85 }
86 

相似题目HDOJ 1305 http://acm.hdu.edu.cn/showproblem.php?pid=1305


posted on 2010-10-05 22:51 Geek.tan 阅读(310) 评论(0)  编辑 收藏 引用 所属分类: ACM解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


导航

统计

公告

coding是我的寂寞，我是谁的寂寞

随笔分类(40)

随笔档案(48)

搜索

积分与排名

最新评论

评论排行榜