前缀树

对于树的每个节点使用一个数组记录每个字母的子树，并用布尔变量判断是否为叶节点。通过深度遍历寻找对应的子树

  1. class Trie {
  2. private:
  3.     vector<Trie*> children;
  4.     bool isEnd;
  5.     Trie* searchPrefix(string prefix){
  6.         Trie* node = this;
  7.         for (char ch:prefix){
  8.             ch -= 'a';
  9.             if(node->children[ch] == NULL)
  10.                 return NULL;
  11.             node = node->children[ch];
  12.         }
  13.         return node;
  14.     }
  15. public:
  16.     /** Initialize your data structure here. */
  17.     Trie(): children(26), isEnd(false) {
  19.     }
  21.     /** Inserts a word into the trie. */
  22.     void insert(string word) {
  23.         Trie* node = this;
  24.         for (char c: word){
  25.             char ch = c - 'a';
  26.             if (node->children[ch] == NULL)
  27.                 node->children[ch] = new Trie();
  28.             node = node->children[ch];
  30.         }
  31.         node->isEnd = true;
  32.     }
  34.     /** Returns if the word is in the trie. */
  35.     bool search(string word) {
  36.         Trie* node = this->searchPrefix(word);
  37.         return node != nullptr && node->isEnd;
  38.     }
  40.     /** Returns if there is any word in the trie that starts with the given prefix. */
  41.     bool startsWith(string prefix) {
  42.         return this->searchPrefix(prefix) != nullptr;
  43.     }
  44. };

LRU缓存机制

同时使用双向链表与哈希map，通过hash快速查找每个节点，使节点后放入头部，插入节点时考查是否超越容量，否则删除尾部

  1. struct DLinkedNode {
  2.     int key, value;
  3.     DLinkedNode* prev;
  4.     DLinkedNode* next;
  5.     DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
  6.     DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
  7. };
  9. class LRUCache {
  10. private:
  11.     unordered_map<int, DLinkedNode*> cache;
  12.     DLinkedNode* head;
  13.     DLinkedNode* tail;
  14.     int size;
  15.     int capacity;
  17. public:
  18.     LRUCache(int _capacity): capacity(_capacity), size(0) {
  19.         // 使用伪头部和伪尾部节点
  20.         head = new DLinkedNode();
  21.         tail = new DLinkedNode();
  22.         head->next = tail;
  23.         tail->prev = head;
  24.     }
  26.     int get(int key) {
  27.         if (!cache.count(key)) {
  28.             return -1;
  29.         }
  30.         // 如果 key 存在，先通过哈希表定位，再移到头部
  31.         DLinkedNode* node = cache[key];
  32.         moveToHead(node);
  33.         return node->value;
  34.     }
  36.     void put(int key, int value) {
  37.         if (!cache.count(key)) {
  38.             // 如果 key 不存在，创建一个新的节点
  39.             DLinkedNode* node = new DLinkedNode(key, value);
  40.             // 添加进哈希表
  41.             cache[key] = node;
  42.             // 添加至双向链表的头部
  43.             addToHead(node);
  44.             ++size;
  45.             if (size > capacity) {
  46.                 // 如果超出容量，删除双向链表的尾部节点
  47.                 DLinkedNode* removed = removeTail();
  48.                 // 删除哈希表中对应的项
  49.                 cache.erase(removed->key);
  50.                 // 防止内存泄漏
  51.                 delete removed;
  52.                 --size;
  53.             }
  54.         }
  55.         else {
  56.             // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
  57.             DLinkedNode* node = cache[key];
  58.             node->value = value;
  59.             moveToHead(node);
  60.         }
  61.     }
  63.     void addToHead(DLinkedNode* node) {
  64.         node->prev = head;
  65.         node->next = head->next;
  66.         head->next->prev = node;
  67.         head->next = node;
  68.     }
  70.     void removeNode(DLinkedNode* node) {
  71.         node->prev->next = node->next;
  72.         node->next->prev = node->prev;
  73.     }
  75.     void moveToHead(DLinkedNode* node) {
  76.         removeNode(node);
  77.         addToHead(node);
  78.     }
  80.     DLinkedNode* removeTail() {
  81.         DLinkedNode* node = tail->prev;
  82.         removeNode(node);
  83.         return node;
  84.     }
  85. };
  88. /**
  89.  * Your LRUCache object will be instantiated and called as such:
  90.  * LRUCache* obj = new LRUCache(capacity);
  91.  * int param_1 = obj->get(key);
  92.  * obj->put(key,value);
  93.  */

平衡二叉树

  1. struct Node {
  2.     int val;
  3.     Node * parent;
  4.     Node * left;
  5.     Node * right;
  6.     int size;
  7.     int height;
  9.     Node(int val) {
  10.         this->val = val;
  11.         this->parent = nullptr;
  12.         this->left = nullptr;
  13.         this->right = nullptr;
  14.         this->height = 0; // 结点高度：以node为根节点的子树的高度（高度定义：叶结点的高度是0）
  15.         this->size = 1; // 结点元素数：以node为根节点的子树的节点总数
  16.     }
  18.     Node(int val, Node * parent) {
  19.         this->val = val;
  20.         this->parent = parent;
  21.         this->left = nullptr;
  22.         this->right = nullptr;
  23.         this->height = 0; // 结点高度：以node为根节点的子树的高度（高度定义：叶结点的高度是0）
  24.         this->size = 1; // 结点元素数：以node为根节点的子树的节点总数
  25.     }
  27.     Node(int val, Node * parent, Node * left, Node * right) {
  28.         this->val = val;
  29.         this->parent = parent;
  30.         this->left = left;
  31.         this->right = right;
  32.         this->height = 0; // 结点高度：以node为根节点的子树的高度（高度定义：叶结点的高度是0）
  33.         this->size = 1; // 结点元素数：以node为根节点的子树的节点总数
  34.     }
  35. };
  38. // 平衡二叉搜索树（AVL树）：允许重复值
  39. class AVL {
  40. public:
  41.     AVL(vector<int> & vals) {
  42.         if (!vals.empty()) {
  43.             root = build(vals, 0, vals.size() - 1, nullptr);
  44.         }
  45.     }
  47.     // 根据vals[l:r]构造平衡二叉搜索树 -> 返回根结点
  48.     Node * build(vector<int> & vals, int l, int r, Node * parent) {
  49.         int m = (l + r) >> 1;
  50.         Node * node = new Node(vals[m], parent);
  51.         if (l <= m - 1) {
  52.             node->left = build(vals, l, m - 1, node);
  53.         }
  54.         if (m + 1 <= r) {
  55.             node->right = build(vals, m + 1, r, node);
  56.         }
  57.         recompute(node);
  58.         return node;
  59.     }
  61.     // 返回二叉搜索树中第k小的元素
  62.     int kthSmallest(int k) {
  63.         Node * node = root;
  64.         while (node != nullptr) {
  65.             int left = getSize(node->left);
  66.             if (left < k - 1) {
  67.                 node = node->right;
  68.                 k -= left + 1;
  69.             } else if (left == k - 1) {
  70.                 break;
  71.             } else {
  72.                 node = node->left;
  73.             }
  74.         }
  75.         return node->val;
  76.     }
  78.     void insert(int v) {
  79.         if (root == nullptr) {
  80.             root = new Node(v);
  81.         } else {
  82.             // 计算新结点的添加位置
  83.             Node * node = subtreeSearch(root, v);
  84.             bool isAddLeft = v <= node->val; // 是否将新结点添加到node的左子结点
  85.             if (node->val == v) { // 如果值为v的结点已存在
  86.                 if (node->left != nullptr) { // 值为v的结点存在左子结点，则添加到其左子树的最右侧
  87.                     node = subtreeLast(node->left);
  88.                     isAddLeft = false;
  89.                 } else { // 值为v的结点不存在左子结点，则添加到其左子结点
  90.                     isAddLeft = true;
  91.                 }
  92.             }
  94.             // 添加新结点
  95.             Node * leaf = new Node(v, node);
  96.             if (isAddLeft) {
  97.                 node->left = leaf;
  98.             } else {
  99.                 node->right = leaf;
  100.             }
  102.             rebalance(leaf);
  103.         }
  104.     }
  106.     // 删除值为v的结点 -> 返回是否成功删除结点
  107.     bool Delete(int v) {
  108.         if (root == nullptr) {
  109.             return false;
  110.         }
  112.         Node * node = subtreeSearch(root, v);
  113.         if (node->val != v) { // 没有找到需要删除的结点
  114.             return false;
  115.         }
  117.         // 处理当前结点既有左子树也有右子树的情况
  118.         // 若左子树比右子树高度低，则将当前结点替换为右子树最左侧的结点，并移除右子树最左侧的结点
  119.         // 若右子树比左子树高度低，则将当前结点替换为左子树最右侧的结点，并移除左子树最右侧的结点
  120.         if (node->left != nullptr && node->right != nullptr) {
  121.             Node * replacement = nullptr;
  122.             if (node->left->height <= node->right->height) {
  123.                 replacement = subtreeFirst(node->right);
  124.             } else {
  125.                 replacement = subtreeLast(node->left);
  126.             }
  127.             node->val = replacement->val;
  128.             node = replacement;
  129.         }
  131.         Node * parent = node->parent;
  132.         Delete(node);
  133.         rebalance(parent);
  134.         return true;
  135.     }
  137. private:
  138.     Node * root;
  140.     // 删除结点p并用它的子结点代替它，结点p至多只能有1个子结点
  141.     void Delete(Node * node) {
  142.         if (node->left != nullptr && node->right != nullptr) {
  143.             return;
  144.             // throw new Exception("Node has two children");
  145.         }
  146.         Node * child = node->left != nullptr ? node->left : node->right;
  147.         if (child != nullptr) {
  148.             child->parent = node->parent;
  149.         }
  150.         if (node == root) {
  151.             root = child;
  152.         } else {
  153.             Node * parent = node->parent;
  154.             if (node == parent->left) {
  155.                 parent->left = child;
  156.             } else {
  157.                 parent->right = child;
  158.             }
  159.         }
  160.         node->parent = node;
  161.     }
  163.     // 在以node为根结点的子树中搜索值为v的结点，如果没有值为v的结点，则返回值为v的结点应该在的位置的父结点
  164.     Node * subtreeSearch(Node * node, int v) {
  165.         if (node->val < v && node->right != nullptr) {
  166.             return subtreeSearch(node->right, v);
  167.         } else if (node->val > v && node->left != nullptr) {
  168.             return subtreeSearch(node->left, v);
  169.         } else {
  170.             return node;
  171.         }
  172.     }
  174.     // 重新计算node结点的高度和元素数
  175.     void recompute(Node * node) {
  176.         node->height = 1 + max(getHeight(node->left), getHeight(node->right));
  177.         node->size = 1 + getSize(node->left) + getSize(node->right);
  178.     }
  180.     // 从node结点开始（含node结点）逐个向上重新平衡二叉树，并更新结点高度和元素数
  181.     void rebalance(Node * node) {
  182.         while (node != nullptr) {
  183.             int oldHeight = node->height, oldSize = node->size;
  184.             if (!isBalanced(node)) {
  185.                 node = restructure(tallGrandchild(node));
  186.                 recompute(node->left);
  187.                 recompute(node->right);
  188.             }
  189.             recompute(node);
  190.             if (node->height == oldHeight && node->size == oldSize) {
  191.                 node = nullptr; // 如果结点高度和元素数都没有变化则不需要再继续向上调整
  192.             } else {
  193.                 node = node->parent;
  194.             }
  195.         }
  196.     }
  198.     // 判断node结点是否平衡
  199.     bool isBalanced(Node * node) {
  200.         return abs(getHeight(node->left) - getHeight(node->right)) <= 1;
  201.     }
  203.     // 获取node结点更高的子树
  204.     Node * tallChild(Node * node) {
  205.         if (getHeight(node->left) > getHeight(node->right)) {
  206.             return node->left;
  207.         } else {
  208.             return node->right;
  209.         }
  210.     }
  212.     // 获取node结点更高的子树中的更高的子树
  213.     Node * tallGrandchild(Node * node) {
  214.         Node * child = tallChild(node);
  215.         return tallChild(child);
  216.     }
  218.     // 重新连接父结点和子结点（子结点允许为空）
  219.     static void relink(Node * parent, Node * child, bool isLeft) {
  220.         if (isLeft) {
  221.             parent->left = child;
  222.         } else {
  223.             parent->right = child;
  224.         }
  225.         if (child != nullptr) {
  226.             child->parent = parent;
  227.         }
  228.     }
  230.     // 旋转操作
  231.     void rotate(Node * node) {
  232.         Node * parent = node->parent;
  233.         Node * grandparent = parent->parent;
  234.         if (grandparent == nullptr) {
  235.             root = node;
  236.             node->parent = nullptr;
  237.         } else {
  238.             relink(grandparent, node, parent == grandparent->left);
  239.         }
  241.         if (node == parent->left) {
  242.             relink(parent, node->right, true);
  243.             relink(node, parent, false);
  244.         } else {
  245.             relink(parent, node->left, false);
  246.             relink(node, parent, true);
  247.         }
  248.     }
  250.     // trinode操作
  251.     Node * restructure(Node * node) {
  252.         Node * parent = node->parent;
  253.         Node * grandparent = parent->parent;
  255.         if ((node == parent->right) == (parent == grandparent->right)) { // 处理需要一次旋转的情况
  256.             rotate(parent);
  257.             return parent;
  258.         } else { // 处理需要两次旋转的情况：第1次旋转后即成为需要一次旋转的情况
  259.             rotate(node);
  260.             rotate(node);
  261.             return node;
  262.         }
  263.     }
  265.     // 返回以node为根结点的子树的第1个元素
  266.     static Node * subtreeFirst(Node * node) {
  267.         while (node->left != nullptr) {
  268.             node = node->left;
  269.         }
  270.         return node;
  271.     }
  273.     // 返回以node为根结点的子树的最后1个元素
  274.     static Node * subtreeLast(Node * node) {
  275.         while (node->right != nullptr) {
  276.             node = node->right;
  277.         }
  278.         return node;
  279.     }
  281.     // 获取以node为根结点的子树的高度
  282.     static int getHeight(Node * node) {
  283.         return node != nullptr ? node->height : 0;
  284.     }
  286.     // 获取以node为根结点的子树的结点数
  287.     static int getSize(Node * node) {
  288.         return node != nullptr ? node->size : 0;
  289.     }
  290. };