首页 > 代码库 > hdu--1671--字典树<出现mle怎么解决>

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

2024-07-16 18:58:44   222人阅读

一直觉得 指针版的 字典树 各种好 直到这题 出现了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         else89             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:

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

　　每天 只要快乐 就足够了

 


联系
我们