Java生成UUID
来源:点击打开链接
好久不发解题报告了……这个是裸的Trie树模板题。需要增加内存释放删除的函数,否则会报MLE。
#include <iostream> #include <cstring> #include <cstdio> #include <stdlib.h> using namespace std; char tar[10005][20]; struct Trie { Trie *next[10]; int v; //根据需要变化,10,26,52,62 }; Trie *root; void init() { root=(Trie *)malloc(sizeof(Trie)); for(int i=0;i<10;i++) { root->next[i]=NULL; } } void Trieinsert(char *str) { int len = strlen(str); Trie *p = root, *q; for(int i=0; i<len; ++i) { int id = str[i]-‘0‘; if(p->next[id] == NULL) { q = (Trie *)malloc(sizeof(Trie)); q->v = 1; for(int j=0; j<10; ++j) q->next[j] = NULL; p->next[id] = q; p = p->next[id]; } else { p->next[id]->v++; p = p->next[id]; } } p->v = -1; } int Triefind(char *str) { int len = strlen(str); Trie *p = root; for(int i=0; i<len; ++i) { int id = str[i]-‘0‘; //根据需要选择是减去‘0‘还是‘a‘,或者是‘A‘ p = p->next[id]; if(p == NULL) return 0; if(p->v == -1) return -1; } return -1; } int Triedel(Trie* T) { int i; if(T==NULL) return 0; for(i=0;i<10;i++) { if(T->next[i]!=NULL) Triedel(T->next[i]); } free(T); return 0; } int main() { int testcase,tarnum; cin>>testcase; while(testcase--) { char tmp[20]; init(); cin>>tarnum; int find=0; for(int i=0;i<tarnum;i++) { scanf("%s",tmp); if(Triefind(tmp)==-1) { find=1; } if(find==1) continue; Trieinsert(tmp); } if(find==1) cout<<"NO"<<endl; else cout<<"YES"<<endl; Triedel(root); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。