做题感悟: 简单的字典树题
解题思路:判断是否存在一个号码是另一个号码的前缀(这题号码不重复),但是POJ 上须静态字典树,就是先申请再将它们连接起来(思路一样),静态用时间很少。
代码(动态内存+释放):
#include<stdio.h> #include<iostream> #include<map> #include<string> #include<string.h> #include<stdlib.h> #include<queue> #include<algorithm> using namespace std ; #define LEN sizeof(struct node) int n ; bool flag ; struct node { bool count ; struct node *next[10] ; } ; struct node *root ; //根节点 struct node *build() // 建立新节点 { struct node *p ; p=(struct node*)malloc(LEN) ; for(int i=0 ;i<10 ;i++) { p->next[i]=NULL ; } p->count=false ; return p ; } void save(char *s) // 存单词同时判断 { int len=strlen(s) ; if(!len) return ; struct node *p ; p=root ; for(int i=0 ;i<len ;i++) { int temp=s[i]-'0' ; if(p->next[temp]&&(p->next[temp]->count||len-1==i)) // 判断是否存在前缀 { flag=true ; break ; } else if(p->next[temp]==NULL) p->next[temp]=build() ; p=p->next[temp] ; } p->count=true ; } void del(struct node *p)// 释放内存 { for(int i=0 ;i<10 ;i++) if(p->next[i]!=NULL) del(p->next[i]) ; free(p) ; } int main() { int T ; char s[15] ; scanf("%d",&T) ; while(T--) { root=build() ; flag=false ; scanf("%d",&n) ; for(int i=0 ;i<n ;i++) { scanf("%s",s) ; if(!flag) save(s) ; } printf("%s\n",flag ? "NO" : "YES") ; del(root) ; // 释放内存 } return 0 ; }
代码(静态字典树):
#include<stdio.h> #include<iostream> #include<map> #include<string> #include<string.h> #include<stdlib.h> #include<queue> #include<algorithm> using namespace std ; #define MX 1000000 struct node { bool count ; struct node *next[10] ; }T[MX] ; struct node *root ; int top=0 ; bool flag ; struct node *build() { struct node *p ; p=&T[top++] ; for(int i=0 ;i<10 ;i++) { p->next[i]=NULL ; } p->count=false ; return p ; } void save(char *s) { int len=strlen(s) ; if(!len) return ; struct node *p ; p=root ; for(int i=0 ;i<len ;i++) { int temp=s[i]-'0' ; if(p->next[temp]&&(p->next[temp]->count||len-1==i)) { flag=true ; return ; } if(p->next[temp]==NULL) p->next[temp]=build() ; p=p->next[temp] ; } p->count=true ; } int main() { int T,n ; char s[15] ; scanf("%d",&T) ; while(T--) { root=build() ; flag=false ; scanf("%d",&n) ; for(int i=0 ;i<n ;i++) { scanf("%s",s) ; if(!flag) save(s) ; } printf("%s\n",flag ? "NO" : "YES") ; top=0 ; } return 0 ; }