hdu1671-每个字典树都应该开释内存
hdu1671-每个字典树都应该释放内存
Total Submission(s): 4627 Accepted Submission(s): 1564
Phone List
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4627 Accepted Submission(s): 1564
题意: 看一堆电话号码中是不是某个电话号码是其中一个电话号码的前缀 如果有 则不能打通 输出NO 没有就全部能连通 输出YES
#include<stdio.h> struct node { node*next[10]; int visit; void ini() { visit=0; for(int i=0;i<10;i++) next[i]=NULL; } //节点初始化 }; int bulid(char *s,node*root) { for(;*s!='\0';s++) { if(root->next[*s-'0']==NULL) { node*p=new node; p->ini(); root->next[*s-'0']=p; root=root->next[*s-'0']; } else { root=root->next[*s-'0']; if(root->visit) return 1; } //检查沿途是否有标记 } root->visit=1; //标记末字符 for(int i=0;i<10;i++) if(root->next[i]!=NULL) return 1; //检查末字符是否有后继字符 很重要 笨蛋 居然没想到 return 0; } void end(struct node *p) { int i; for(i=0;i<10;i++) if(p->next[i]!=NULL) end(p->next[i]); delete(p); } int main() { int sum; scanf("%d",&sum); while(sum--) { int num; scanf("%d",&num); char number[15]; int g=0; node*root=new node; root->ini(); while(num--) { scanf("%s",number); if(bulid(number,root)) {g=1;break;} } while(g&&num)//这个地方处理蛮巧妙的可以节省时间哦 { scanf("%s",number); num--; } if(g) printf("NO\n"); else printf("YES\n"); end(root);//必须要释放否则MLE } return 0; }