//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;
}