Untitled
unknown
plain_text
a year ago
2.5 kB
1
Indexable
Never
//trie #include <iostream> #include <string> using namespace std; class Node { public: Node *child[26]; // bool isLeaf; int count; //tuy de bai // string s; Node() { for (int i = 0; i < 26; i++) { child[i] = nullptr; } // isLeaf = false; count = 0; } }; const int MAXNODE = 20000; Node pool[MAXNODE]; int cnt; Node *getNode() { return &pool[cnt++]; } class Trie { public: Node *root; Trie() { root = getNode(); } void add(string s) { Node *cur = root; int index; for (char c : s) { index = c - 'a'; if (cur->child[index] == nullptr) { cur->child[index] = getNode(); } cur = cur->child[index]; cur->count++; } // cur->isLeaf = true; } int findPrefix(string s) { Node * cur = root; int index; for (char c : s) { index = c - 'a'; if (cur->child[index] == nullptr) return false; cur = cur->child[index]; } return cur->count; } }; int main() { cnt = 0; Trie t; t.add("abc"); t.add("abcd"); t.add("abd"); t.add("ace"); cout << "find prefix ab: " << t.findPrefix("ab") << endl; return 0; } //bst #include <iostream> #include <string> #include <queue> #include <vector> #include <set> using namespace std; class Node { public: int id; int score; Node(int i, int s) { id = i; score = s; } }; class CmpNode { public: bool operator() (const Node *n1, const Node *n2) { if (n2->score != n1->score) return n1->score < n2->score; return n1->id < n2->id; } }; int main() { set<Node *, CmpNode> p; Node n1(1, 22); Node n2(2, 33); Node n3(3, 77); Node n4(4, 77); p.insert(&n1); p.insert(&n2); p.insert(&n3); p.insert(&n4); //p.erase(&n4); n4.score = 11; //p.insert(&n4); for (Node *tp : p) { printf("%d %d\n", tp->id, tp->score); } printf("\n\n"); /* p.erase(); p.find(); p.upper_bound(); p.lower_bound(); p.begin(); p.end(); p.size(); */ Node n(2, 33); auto it = p.upper_bound(&n); it--; printf("%d_%d\n", (*it)->id, (*it)->score); return 0; } //heap #include <iostream> #include <string> #include <queue> #include <vector> using namespace std; class Node { public: int score; Node(int s) { score = s; } }; class CmpNode { public: bool operator() (const Node *n1, const Node *n2) { if (n2->score > n1->score) return true; else return false; } }; int main() { priority_queue<Node *, vector<Node *>, CmpNode> p; Node n1(22); Node n2(33); Node n3(77); p.push(&n1); p.push(&n2); p.push(&n3); Node *tp = p.top(); p.pop(); tp = p.top(); printf("%d\n", p.size()); return 0; }