C++ 数据结构知识点详解

#include <vector>
#include <list>
#include <iostream>

int main() {
    // 数组：随机访问 O(1)，适合频繁按下标读取
    std::vector<int> arr{1, 2, 3, 4, 5};
    std::cout << arr[2] << '\n';          // 3，O(1)

    // 链表：中间插入 O(1)，适合频繁插入删除
    std::list<int> lst{1, 2, 4, 5};
    auto it = lst.begin();
    std::advance(it, 2);                   // 指向 4
    lst.insert(it, 3);                     // 变成 1 2 3 4 5
    return 0;
}

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class SinglyLinkedList {
public:
    SinglyLinkedList() : head(nullptr) {}

    // 尾部插入
    void push_back(int val) {
        ListNode* node = new ListNode(val);
        if (!head) { head = node; return; }
        ListNode* p = head;
        while (p->next) p = p->next;
        p->next = node;
    }

    // 按值查找，返回第一个匹配节点，找不到返回 nullptr
    ListNode* find(int val) {
        for (ListNode* p = head; p; p = p->next)
            if (p->val == val) return p;
        return nullptr;
    }

    // 删除第一个值为 val 的节点，返回是否删除成功
    bool remove(int val) {
        ListNode** cur = &head;            // 二级指针，优雅处理头节点删除
        while (*cur && (*cur)->val != val)
            cur = &(*cur)->next;
        if (!*cur) return false;
        ListNode* tmp = *cur;
        *cur = (*cur)->next;               // 把前驱的 next 指向被删节点的 next
        delete tmp;
        return true;
    }

    // 打印
    void print() {
        for (ListNode* p = head; p; p = p->next)
            std::cout << p->val << " ";
        std::cout << '\n';
    }

    ~SinglyLinkedList() {                  // 析构释放全部节点
        while (head) {
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }
    }

private:
    ListNode* head;
};

int main() {
    SinglyLinkedList l;
    l.push_back(1); l.push_back(2); l.push_back(3);
    l.remove(2);
    l.print();                             // 1 3
    return 0;
}

#include <stack>

class MyQueue {
    std::stack<int> in, out;

    void transfer() {                      // 只有 out 空时才搬
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
    }

public:
    void push(int x) { in.push(x); }       // 入队 O(1)
    int pop() {                            // 出队均摊 O(1)
        transfer();
        int v = out.top(); out.pop();
        return v;
    }
    int peek() {                           // 取队首均摊 O(1)
        transfer();
        return out.top();
    }
    bool empty() { return in.empty() && out.empty(); }
};

// 简化版链地址哈希表：vector<list<pair<K,V>>>
#include <vector>
#include <list>
#include <utility>
#include <cstddef>

template <typename K, typename V>
class MyHashMap {
    std::vector<std::list<std::pair<K, V>>> buckets;
    std::size_t count = 0;

    std::size_t hash(const K& key) const {
        return std::hash<K>{}(key) % buckets.size();
    }

public:
    MyHashMap(std::size_t n = 16) : buckets(n) {}

    void put(const K& key, const V& val) {
        auto& list = buckets[hash(key)];
        for (auto& kv : list) {
            if (kv.first == key) { kv.second = val; return; } // 覆盖
        }
        list.emplace_back(key, val);       // 拉链追加
        ++count;
    }

    bool get(const K& key, V& out) const {
        const auto& list = buckets[hash(key)];
        for (const auto& kv : list)
            if (kv.first == key) { out = kv.second; return true; }
        return false;
    }
};

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> m;

    // 底层可观测接口
    std::cout << "bucket_count = " << m.bucket_count() << '\n';      // 初始桶数
    std::cout << "max_load_factor = " << m.max_load_factor() << '\n'; // 默认 1.0

    m["apple"] = 1;
    m["banana"] = 2;
    std::cout << "load_factor = " << m.load_factor() << '\n';        // 元素数/桶数

    // 查询 key 所在桶
    std::cout << "apple 在桶 " << m.bucket("apple") << '\n';
    return 0;
}

#include <string>
#include <cstddef>

// 多项式滚动哈希（类 Java String.hashCode 思路，用 31 乘子）
std::size_t poly_hash(const std::string& s) {
    std::size_t h = 0;
    for (char c : s)
        h = h * 31 + static_cast<unsigned char>(c);
    return h;
}

// 更稳健的字符串哈希：FNV-1a，分布更均匀
std::size_t fnv1a(const std::string& s) {
    std::size_t h = 1469598103934665603ULL;  // FNV offset basis
    for (char c : s) {
        h ^= static_cast<unsigned char>(c);
        h *= 1099511628211ULL;               // FNV prime
    }
    return h;
}

#include <vector>
#include <algorithm>

class MinHeap {
    std::vector<int> a;

    void sift_up(int i) {
        while (i > 0 && a[i] < a[(i - 1) / 2]) {
            std::swap(a[i], a[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }

    void sift_down(int i) {
        int n = a.size();
        while (true) {
            int l = 2 * i + 1, r = 2 * i + 2, small = i;
            if (l < n && a[l] < a[small]) small = l;
            if (r < n && a[r] < a[small]) small = r;
            if (small == i) break;
            std::swap(a[i], a[small]);
            i = small;
        }
    }

public:
    void push(int x) { a.push_back(x); sift_up(a.size() - 1); }
    int top() const { return a[0]; }
    void pop() { a[0] = a.back(); a.pop_back(); sift_down(0); }
    bool empty() const { return a.empty(); }
    int size() const { return a.size(); }
};

#include <queue>
#include <vector>

std::vector<int> topK(const std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int x : nums) {
        minHeap.push(x);
        if (minHeap.size() > k) minHeap.pop();   // 维持堆大小为 k
    }
    std::vector<int> res;
    while (!minHeap.empty()) { res.push_back(minHeap.top()); minHeap.pop(); }
    return res;                                  // 从第 K 大到最大
}

#include <queue>
#include <vector>
#include <iostream>

int main() {
    // 默认大顶堆（less 比较，堆顶最大）
    std::priority_queue<int> maxHeap;
    maxHeap.push(3); maxHeap.push(1); maxHeap.push(5);
    std::cout << maxHeap.top() << '\n';          // 5

    // 小顶堆：greater 比较
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(3); minHeap.push(1); minHeap.push(5);
    std::cout << minHeap.top() << '\n';          // 1
    return 0;
}

#include <iostream>

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序：根 -> 左 -> 右
void preorder(TreeNode* root) {
    if (!root) return;
    std::cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

// 中序：左 -> 根 -> 右（BST 中序得到有序序列）
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    std::cout << root->val << " ";
    inorder(root->right);
}

// 后序：左 -> 右 -> 根
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    std::cout << root->val << " ";
}

#include <stack>
#include <vector>

std::vector<int> inorder_iter(TreeNode* root) {
    std::vector<int> res;
    std::stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) {              // 一路向左压栈
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top(); st.pop();  // 弹出访问
        res.push_back(cur->val);
        cur = cur->right;          // 转向右子树
    }
    return res;
}

#include <queue>
#include <vector>

std::vector<std::vector<int>> levelorder(TreeNode* root) {
    std::vector<std::vector<int>> res;
    if (!root) return res;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int n = q.size();
        std::vector<int> level;
        for (int i = 0; i < n; ++i) {          // 一次处理一层
            TreeNode* cur = q.front(); q.pop();
            level.push_back(cur->val);
            if (cur->left)  q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        res.push_back(level);
    }
    return res;
}

#include <iostream>

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// BST 查找：平均 O(log n)，退化 O(n)
TreeNode* search(TreeNode* root, int key) {
    while (root) {
        if (key < root->val)      root = root->left;
        else if (key > root->val) root = root->right;
        else                      return root;
    }
    return nullptr;
}

// BST 插入
TreeNode* insert(TreeNode* root, int key) {
    if (!root) return new TreeNode(key);
    if (key < root->val) root->left  = insert(root->left, key);
    else                 root->right = insert(root->right, key);
    return root;
}

#include <algorithm>

struct AVLNode {
    int val, height;
    AVLNode *left, *right;
    AVLNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {}
};

int h(AVLNode* n) { return n ? n->height : 0; }
int bf(AVLNode* n) { return n ? h(n->left) - h(n->right) : 0; } // 平衡因子

void update(AVLNode* n) { n->height = 1 + std::max(h(n->left), h(n->right)); }

AVLNode* rotateRight(AVLNode* y) {          // 右旋
    AVLNode* x = y->left;
    y->left = x->right;
    x->right = y;
    update(y); update(x);
    return x;
}

AVLNode* rotateLeft(AVLNode* x) {           // 左旋
    AVLNode* y = x->right;
    x->right = y->left;
    y->left = x;
    update(x); update(y);
    return y;
}

AVLNode* insert(AVLNode* n, int val) {
    if (!n) return new AVLNode(val);
    if (val < n->val) n->left  = insert(n->left, val);
    else              n->right = insert(n->right, val);
    update(n);

    int b = bf(n);
    if (b > 1 && val < n->left->val)  return rotateRight(n);       // LL
    if (b > 1 && val > n->left->val)  { n->left = rotateLeft(n->left); return rotateRight(n); }  // LR
    if (b < -1 && val > n->right->val) return rotateLeft(n);       // RR
    if (b < -1 && val < n->right->val) { n->right = rotateRight(n->right); return rotateLeft(n); }// RL
    return n;
}

#include <map>
#include <string>
#include <iostream>

int main() {
    std::map<std::string, int> m;   // 底层红黑树，key 有序
    m["banana"] = 2;
    m["apple"]  = 1;
    m["cherry"] = 3;
    for (auto& [k, v] : m)          // 按键有序输出：apple banana cherry
        std::cout << k << ':' << v << '\n';

    // 范围查询：找 key >= "b" 的区间，红黑树的中序有序性带来
    auto it = m.lower_bound("b");
    return 0;
}

#include <vector>
#include <iostream>

// 邻接矩阵
std::vector<std::vector<int>> build_matrix(int n, const std::vector<std::pair<int,int>>& edges) {
    std::vector<std::vector<int>> g(n, std::vector<int>(n, 0));
    for (auto& [u, v] : edges) g[u][v] = 1;   // 无向图再设 g[v][u] = 1
    return g;
}

// 邻接表（C++ 首选，稀疏图高效）
std::vector<std::vector<int>> build_adj(int n, const std::vector<std::pair<int,int>>& edges) {
    std::vector<std::vector<int>> g(n);
    for (auto& [u, v] : edges) {
        g[u].push_back(v);
        g[v].push_back(u);                    // 无向图双向
    }
    return g;
}

#include <vector>
#include <queue>
#include <iostream>

// BFS：从 s 出发遍历，返回访问顺序（求无权图最短距离同理）
std::vector<int> bfs(const std::vector<std::vector<int>>& g, int s) {
    std::vector<bool> visited(g.size(), false);
    std::vector<int> order;
    std::queue<int> q;
    q.push(s); visited[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : g[u])
            if (!visited[v]) { visited[v] = true; q.push(v); }
    }
    return order;
}

// DFS：递归版
void dfs_rec(const std::vector<std::vector<int>>& g, int u,
             std::vector<bool>& visited, std::vector<int>& order) {
    visited[u] = true;
    order.push_back(u);
    for (int v : g[u])
        if (!visited[v]) dfs_rec(g, v, visited, order);
}

#include <stack>

std::vector<int> dfs_iter(const std::vector<std::vector<int>>& g, int s) {
    std::vector<bool> visited(g.size(), false);
    std::vector<int> order;
    std::stack<int> st;
    st.push(s);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        order.push_back(u);
        for (int v : g[u]) if (!visited[v]) st.push(v);
    }
    return order;
}

#include <cstdlib>
#include <climits>
#include <iostream>

// 简化跳表节点：多层 next 指针
struct SkipNode {
    int val;
    std::vector<SkipNode*> next;
    SkipNode(int v, int level) : val(v), next(level, nullptr) {}
};

class SkipList {
    static const int MAX_LEVEL = 16;
    SkipNode* head;

    int random_level() {                 // 随机层高：50% 概率升一层
        int level = 1;
        while (level < MAX_LEVEL && (rand() & 1)) ++level;
        return level;
    }

public:
    SkipList() : head(new SkipNode(INT_MIN, MAX_LEVEL)) {}

    SkipNode* find(int target) {
        SkipNode* cur = head;
        for (int i = MAX_LEVEL - 1; i >= 0; --i) {
            while (cur->next[i] && cur->next[i]->val < target)
                cur = cur->next[i];      // 当前层向右跳
        }
        return cur->next[0] && cur->next[0]->val == target ? cur->next[0] : nullptr;
    }

    void insert(int val) {
        int level = random_level();
        SkipNode* node = new SkipNode(val, level);
        SkipNode* cur = head;
        for (int i = MAX_LEVEL - 1; i >= 0; --i) {
            while (cur->next[i] && cur->next[i]->val < val)
                cur = cur->next[i];
            if (i < level) {             // 在低层插入新节点
                node->next[i] = cur->next[i];
                cur->next[i] = node;
            }
        }
    }
};

#include <vector>

class UnionFind {
    std::vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;   // 各自独立成集合
    }

    // 查找根 + 路径压缩：把沿途节点直接挂到根
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    // 按秩合并：把矮树挂到高树下，避免退化成链
    void unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) std::swap(rx, ry);
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) ++rank[rx];
    }

    bool connected(int x, int y) { return find(x) == find(y); }
};

#include <unordered_map>
#include <string>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children; // 字符映射
    bool is_end = false;                          // 是否为某单词结尾
};

class Trie {
    TrieNode* root;
public:
    Trie() : root(new TrieNode()) {}

    void insert(const std::string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            if (!cur->children.count(c))
                cur->children[c] = new TrieNode();
            cur = cur->children[c];
        }
        cur->is_end = true;
    }

    bool search(const std::string& word) {        // 完整单词是否存在
        TrieNode* cur = root;
        for (char c : word) {
            if (!cur->children.count(c)) return false;
            cur = cur->children[c];
        }
        return cur->is_end;
    }

    bool startsWith(const std::string& prefix) {  // 是否存在该前缀
        TrieNode* cur = root;
        for (char c : prefix) {
            if (!cur->children.count(c)) return false;
            cur = cur->children[c];
        }
        return true;
    }
};

#include <vector>
#include <string>
#include <functional>

class BloomFilter {
    std::vector<bool> bits;                 // 位数组
    std::vector<std::hash<std::string>> hashers; // 简化：k 个哈希用不同种子
    int k;

    std::size_t nth_hash(const std::string& s, int i) {
        // 用双哈希技巧模拟 k 个哈希：h_i = h1 + i*h2
        std::size_t h1 = hashers[0](s);
        std::size_t h2 = hashers[1](s);
        return (h1 + i * h2) % bits.size();
    }

public:
    BloomFilter(std::size_t m, int k) : bits(m), hashers(2), k(k) {}

    void add(const std::string& s) {
        for (int i = 0; i < k; ++i) bits[nth_hash(s, i)] = true;
    }

    bool might_contain(const std::string& s) {
        for (int i = 0; i < k; ++i)
            if (!bits[nth_hash(s, i)]) return false;   // 一定不存在
        return true;                                   // 可能存在（可能误判）
    }
};

// B+ 树节点示意（仅结构，非完整实现）
#include <vector>

template <typename K, typename V>
struct BPlusNode {
    bool is_leaf;
    std::vector<K> keys;                       // 内部节点存 key 索引
    std::vector<BPlusNode*> children;          // 内部节点的子指针
    std::vector<V> values;                     // 叶子节点存数据
    BPlusNode* next_leaf = nullptr;            // 叶子节点串成链表
};

#include <unordered_map>
#include <list>

class LRUCache {
    int cap;
    std::list<std::pair<int, int>> lru;                 // 双向链表：头新尾旧
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> mp;

public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end()) return -1;
        lru.splice(lru.begin(), lru, it->second);       // 移到头部（最新）
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = mp.find(key);
        if (it != mp.end()) {                           // 已存在：更新并移到头部
            lru.splice(lru.begin(), lru, it->second);
            it->second->second = value;
            return;
        }
        if (lru.size() == cap) {                        // 满了：淘汰尾部（最旧）
            mp.erase(lru.back().first);
            lru.pop_back();
        }
        lru.emplace_front(key, value);
        mp[key] = lru.begin();
    }
};

#include <vector>

// 线段树：维护区间和，支持「区间加法 + 区间查询」
class SegmentTree {
    std::vector<long long> tree, lazy;   // 各开 4n 空间
    int n;

    void build(const std::vector<int>& a, int node, int l, int r) {
        if (l == r) { tree[node] = a[l]; return; }
        int mid = (l + r) >> 1;
        build(a, node * 2, l, mid);
        build(a, node * 2 + 1, mid + 1, r);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];   // 自底向上合并
    }

    void pushdown(int node, int l, int r) {                  // 懒标记下传
        if (lazy[node] == 0) return;
        int mid = (l + r) >> 1;
        tree[node * 2]     += lazy[node] * (mid - l + 1);
        tree[node * 2 + 1] += lazy[node] * (r - mid);
        lazy[node * 2]     += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
        lazy[node] = 0;
    }

    void range_add(int node, int l, int r, int ql, int qr, long long val) {
        if (ql <= l && r <= qr) {            // 完全覆盖：直接打懒标记
            tree[node] += val * (r - l + 1);
            lazy[node] += val;
            return;
        }
        pushdown(node, l, r);                // 部分覆盖：先下传再递归
        int mid = (l + r) >> 1;
        if (ql <= mid) range_add(node * 2, l, mid, ql, qr, val);
        if (qr > mid)  range_add(node * 2 + 1, mid + 1, r, ql, qr, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    long long query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[node];
        pushdown(node, l, r);
        int mid = (l + r) >> 1;
        long long res = 0;
        if (ql <= mid) res += query(node * 2, l, mid, ql, qr);
        if (qr > mid)  res += query(node * 2 + 1, mid + 1, r, ql, qr);
        return res;
    }

public:
    SegmentTree(const std::vector<int>& a) : n(a.size()) {
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
        build(a, 1, 0, n - 1);
    }
    void range_add(int l, int r, long long val) { range_add(1, 0, n - 1, l, r, val); }
    long long query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

#include <vector>

// 树状数组：单点更新 + 前缀和查询（下标从 1 开始）
class Fenwick {
    std::vector<long long> tree;
    int n;

    static int lowbit(int x) { return x & (-x); }

public:
    Fenwick(int n) : tree(n + 1, 0), n(n) {}

    // 单点更新：位置 i 加 val，O(log n)
    void add(int i, long long val) {
        for (; i <= n; i += lowbit(i)) tree[i] += val;
    }

    // 前缀和 [1, i]，O(log n)
    long long sum(int i) {
        long long res = 0;
        for (; i > 0; i -= lowbit(i)) res += tree[i];
        return res;
    }

    // 区间和 [l, r]
    long long range_sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};