首页 > 代码库 > HDU1671——前缀树的一点感触
HDU1671——前缀树的一点感触
题目http://acm.hdu.edu.cn/showproblem.php?pid=1671
题目本身不难,一棵前缀树OK,但是前两次提交都没有成功。
第一次Memory Limit Exceeded:
前缀树是很费空间的数据结构,每个节点存放了字母(数字)个数个指针,正所谓用空间来换取时间。
我发现我忘记写析构函数了,所以测例多起来还不释放很容易超空间。
树形结构的析构也很有趣:
1 ~Node() 2 { 3 for (int i = 0; i < 10; ++i) 4 { 5 if (children[i]) 6 { 7 delete children[i]; 8 children[i] = nullptr; 9 } 10 } 11 }
好了,第二次没成功,Time Limit Exceeded:
看起来这是一棵规规矩矩的前缀树,仔细找可以优化的地方,试探性地把
1 vector<Node *> children; 2 Node() 3 { 4 for (int i = 0; i < 10; ++i) children.push_back(nullptr); 5 }
改成了
1 vector<Node *> children = vector<Node *>(10, nullptr); 2 Node() 3 { 4 //for (int i = 0; i < 10; ++i) children.push_back(nullptr); 5 }
Accepted!显然构造的时候赋值比构造之后再赋值要快。。果然还是要尽可能的优化啊!
附代码:
1 #include <string> 2 #include <vector> 3 #include <iostream> 4 5 using namespace std; 6 7 class Node 8 { 9 public: 10 bool is_phone = false; 11 vector<Node *> children = vector<Node *>(10, nullptr); 12 Node() 13 {} 14 ~Node() 15 { 16 for (int i = 0; i < 10; ++i) 17 { 18 if (children[i]) 19 { 20 delete children[i]; 21 children[i] = nullptr; 22 } 23 } 24 } 25 void insert(const string &_Phone) 26 { 27 Node *p = this; 28 for (int i = 0; i < _Phone.size(); ++i) 29 { 30 int curr = _Phone[i] - ‘0‘; 31 if (p->children[curr] == nullptr) 32 { 33 p->children[curr] = new Node(); 34 } 35 p = p->children[curr]; 36 } 37 p->is_phone = true; 38 } 39 bool has_phone(const string &_Phone) 40 { 41 Node *p = this; 42 for (int i = 0; i < _Phone.size(); ++i) 43 { 44 int curr = _Phone[i] - ‘0‘; 45 if (!p->children[curr]) return false; 46 if (p->children[curr]->is_phone) return true; 47 p = p->children[curr]; 48 } 49 return true; 50 } 51 }; 52 53 typedef Node *Trie; 54 55 int main() 56 { 57 int t; 58 cin >> t; 59 while (t--) 60 { 61 Trie trie = new Node(); 62 int n; 63 cin >> n; 64 string phone; 65 bool flag = true; 66 while (n--) 67 { 68 cin >> phone; 69 if (trie->has_phone(phone)) { flag = false; } 70 trie->insert(phone); 71 } 72 if (flag) cout << "YES" << endl; 73 else cout << "NO" << endl; 74 delete trie; 75 } 76 //system("pause"); 77 return 0; 78 }
HDU1671——前缀树的一点感触
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。