hdu--1671--字典树<出现mle怎么解决>

一直觉得指针版的字典树各种好直到这题出现了MLE之后才发现还是有点烦的=-=

但其实解决的方法也蛮简单的只要写了个deleteTrie函数就好了

 1 void deleteTrie( trie* root )
 2 {
 3     if( root == NULL )
 4         return;
 5     for( int i = 0 ; i<size ; i++ )
 6     {
 7         if( root->next[i] !=NULL )
 8         {
 9             deleteTrie( root->next[i] );
10         }
11     }        
12     delete root;
13     return;
14 }

这里把我折磨了好久当我写完这个的时候没有再去 root = new trie一遍导致一直运行错误找了好久才发现卧槽，。。

这题就是给你N个字符串问是否其中某个字符串是其他的前缀或者它自身是别人的前缀

所以就需要2个判断分别判断自己是不是前缀和别人是否成为自己的前缀

　　　　　　--touch me --

这里用到的方法和我上次用过的很像设置一个flag变量表明这个字符串出现过了

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 bool vis;
 6 const int size = 10;
 7 struct trie
 8 {
 9     struct trie* next[size];
10     int flag;
11 };
12 trie* root;
13 
14 void init( trie* root )
15 {
16     for( int i = 0 ; i<size ; i++ )
17     {
18         root->next[i] = NULL;
19     }
20     root->flag = -1;
21 }
22 
23 void create( char* str , int flag )
24 {
25     trie*p = root;
26     trie* q;
27     int len = strlen(str);
28     for( int i = 0 ; i<len ; i++ )
29     {
30         int id = str[i] - '0';
31         if( p->next[id] == NULL )
32         {
33             q = new trie;
34             init( q );
35             p->next[id] = q;
36         }
37         else if( p->next[id]->flag != -1 )
38         {
39             vis = true;
40         }
41         p = p->next[id];
42     }
43     p->flag = flag;
44     for( int i = 0 ; i<size ; i++ )
45     {
46         if( p->next[i]!=NULL )
47         {
48             vis = true;
49             break;
50         }
51     }
52 }
53 
54 void deleteTrie( trie* root )
55 {
56     if( root == NULL )
57         return;
58     for( int i = 0 ; i<size ; i++ )
59     {
60         if( root->next[i] !=NULL )
61         {
62             deleteTrie( root->next[i] );
63         }
64     }        
65     delete root;
66     return;
67 }
68 
69 int main()
70 {
71     cin.sync_with_stdio(false);
72     char str[20];
73     int t , n;
74     cin >> t;
75     while( t-- )
76     {
77         root = new trie;
78         init( root );
79         vis = false;
80         cin >> n;
81         while( n-- )
82         {
83             cin >> str;
84             create( str , n );
85         }
86         if( vis )
87             cout << "NO" << endl;
88         else
89             cout << "YES" << endl;
90         deleteTrie(root);
91     }
92     return 0;
93 }

View Code

其实还可以有种方法避免自己再deleteTrie后忘记 root = new trie就是将 init函数的形参变下就好了

1 void init( trie*& root )
2 {
3     root = new trie;
4     for( int i = 0 ; i<size ; i++ )
5     {
6         root->next[i] = NULL;
7     }
8     root->flag = -1;
9 }

这个形参的传入在链表的学习的时候经常用到..

today:

　　所谓成功就是按你自己喜欢的方式过完一生

　　每天只要快乐就足够了

just follow your heart