首页 > 代码库 > hdu--1671--字典树<出现mle怎么解决>
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 else89 cout << "YES" << endl;90 deleteTrie(root);91 }92 return 0;93 }
其实 还可以有种方法避免自己再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:
所谓成功 就是按你自己喜欢的方式 过完一生
每天 只要快乐 就足够了
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。