常见数据结构

#include <iostream>
#include <unordered_map>

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

// 反转链表（迭代）
Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        Node* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

// LRU Cache（双向链表 + unordered_map，get/put 均 O(1)）
struct DNode {
    int key, val;
    DNode* prev;
    DNode* next;
    DNode(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
};

struct LRUCache {
    int cap;
    std::unordered_map<int, DNode*> cache;
    DNode* head;  // dummy head
    DNode* tail;  // dummy tail

    LRUCache(int capacity) : cap(capacity) {
        head = new DNode(0, 0);
        tail = new DNode(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    void remove(DNode* n) { n->prev->next = n->next; n->next->prev = n->prev; }
    void addFront(DNode* n) { n->next = head->next; n->prev = head; head->next->prev = n; head->next = n; }
    int get(int key) {
        if (!cache.count(key)) return -1;
        DNode* n = cache[key]; remove(n); addFront(n); return n->val;    // 命中：移到头部
    }
    void put(int key, int val) {
        if (cache.count(key)) { DNode* n = cache[key]; n->val = val; remove(n); addFront(n); return; }
        if ((int)cache.size() == cap) {                                 // 超容：淘汰尾部
            DNode* lru = tail->prev; remove(lru); cache.erase(lru->key); delete lru;
        }
        DNode* n = new DNode(key, val); addFront(n); cache[key] = n;
    }
};

int main() {
    // 反转链表：1->2->3 变 3->2->1
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head = reverseList(head);
    std::cout << "反转后: ";
    for (Node* p = head; p; p = p->next) std::cout << p->val << (p->next ? "->" : "\n");

    // LRU（容量 2）
    LRUCache lru(2);
    lru.put(1, 10);
    lru.put(2, 20);
    std::cout << "get(1) = " << lru.get(1) << "\n";   // 10（1 变为最近使用）
    lru.put(3, 30);                                    // 容量满 → 淘汰最久未用的 key 2
    std::cout << "get(2) = " << lru.get(2) << "\n";   // -1（已淘汰）
    return 0;
}

#include <iostream>
#include <vector>
#include <stack>

// 单调递减栈：求每个元素右侧第一个更大元素
std::vector<int> nextGreater(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> res(n, 0);
    std::stack<int> stk;  // 存索引
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && nums[stk.top()] < nums[i]) {
            int idx = stk.top();
            stk.pop();
            res[idx] = nums[i];
        }
        stk.push(i);
    }
    return res;
}

int main() {
    std::vector<int> nums = {2, 1, 2, 4, 3};
    auto res = nextGreater(nums);
    std::cout << "下一个更大元素: ";
    for (int x : res) std::cout << x << " ";   // 4 2 4 0 0（0 表示右侧无更大）
    std::cout << "\n";
    return 0;
}

#include <iostream>
#include <vector>
#include <stack>

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

TreeNode* insert(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);
    if (val < root->val)
        root->left = insert(root->left, val);
    else
        root->right = insert(root->right, val);
    return root;
}

// 中序遍历（迭代）
std::vector<int> inorder(TreeNode* root) {
    std::vector<int> res;
    std::stack<TreeNode*> stk;
    TreeNode* cur = root;
    while (cur != nullptr || !stk.empty()) {
        while (cur != nullptr) {
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        stk.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

int main() {
    TreeNode* root = nullptr;
    for (int x : {5, 3, 7, 2, 4, 6, 8}) root = insert(root, x);
    auto io = inorder(root);
    std::cout << "BST 中序(有序): ";
    for (int x : io) std::cout << x << " ";   // 2 3 4 5 6 7 8
    std::cout << "\n";
    return 0;
}

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

// Top K 最大元素：用最小堆（priority_queue 默认最大堆，greater<int> 变最小堆）维护 k 个
std::vector<int> topK(const std::vector<int>& nums, int k) {
    // min-heap: 堆顶是最小元素
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int v : nums) {
        minHeap.push(v);
        if ((int)minHeap.size() > k) {
            minHeap.pop();  // 弹出最小的，保留最大的 k 个
        }
    }
    std::vector<int> res;
    while (!minHeap.empty()) {
        res.push_back(minHeap.top());
        minHeap.pop();
    }
    return res;  // 返回 Top K 最大元素（升序）
}

int main() {
    std::vector<int> nums = {3, 1, 5, 12, 2, 11};
    auto res = topK(nums, 3);
    std::cout << "Top-3 最大: ";
    for (int x : res) std::cout << x << " ";   // 5 11 12（升序）
    std::cout << "\n";
    return 0;
}

#include <iostream>
#include <string>
#include <array>

struct TrieNode {
    std::array<TrieNode*, 26> children{};
    bool isEnd = false;
    TrieNode() { children.fill(nullptr); }
};

struct Trie {
    TrieNode* root;
    Trie() : root(new TrieNode()) {}

    void insert(const std::string& word) {
        TrieNode* cur = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (cur->children[idx] == nullptr)
                cur->children[idx] = new TrieNode();
            cur = cur->children[idx];
        }
        cur->isEnd = true;
    }

    bool search(const std::string& word) {
        TrieNode* cur = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (cur->children[idx] == nullptr) return false;
            cur = cur->children[idx];
        }
        return cur->isEnd;
    }

    bool startsWith(const std::string& prefix) {
        TrieNode* cur = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (cur->children[idx] == nullptr) return false;
            cur = cur->children[idx];
        }
        return true;
    }
};

int main() {
    Trie t;
    t.insert("apple");
    std::cout << std::boolalpha
              << "search(apple)   = " << t.search("apple")      << "\n"   // true
              << "search(app)     = " << t.search("app")        << "\n"   // false（不是完整单词）
              << "startsWith(app) = " << t.startsWith("app")    << "\n";  // true（是前缀）
    return 0;
}

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

constexpr int MAX_LEVEL = 16;
constexpr double P = 0.5;

struct SkipNode {
    int val;
    std::array<SkipNode*, MAX_LEVEL> forward{};
    SkipNode(int v) : val(v) { forward.fill(nullptr); }
};

struct SkipList {
    SkipNode* head;
    int level;

    SkipList() : level(1) {
        head = new SkipNode(INT_MIN);  // 哨兵节点
    }

    static int randomLevel() {
        int lv = 1;
        while (lv < MAX_LEVEL && (double)rand() / RAND_MAX < P)
            lv++;
        return lv;
    }

    void insert(int val) {
        std::array<SkipNode*, MAX_LEVEL> update{};      // 各层待更新的前驱
        SkipNode* cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur->forward[i] && cur->forward[i]->val < val) cur = cur->forward[i];
            update[i] = cur;
        }
        int lv = randomLevel();
        if (lv > level) { for (int i = level; i < lv; i++) update[i] = head; level = lv; }
        SkipNode* node = new SkipNode(val);
        for (int i = 0; i < lv; i++) {                   // 在每一层把新节点接进链表
            node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = node;
        }
    }

    bool search(int val) const {
        SkipNode* cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur->forward[i] != nullptr && cur->forward[i]->val < val)
                cur = cur->forward[i];
        }
        cur = cur->forward[0];
        return cur != nullptr && cur->val == val;
    }
};

int main() {
    srand(42);
    SkipList sl;
    for (int x : {1, 3, 4, 7, 9}) sl.insert(x);
    std::cout << std::boolalpha
              << "search(7) = " << sl.search(7) << "\n"   // true
              << "search(5) = " << sl.search(5) << "\n";  // false
    return 0;
}

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

struct BloomFilter {
    std::vector<bool> bits;
    std::vector<std::function<size_t(const std::string&)>> hashFns;

    BloomFilter(int m, std::vector<std::function<size_t(const std::string&)>> fns)
        : bits(m, false), hashFns(std::move(fns)) {}

    void add(const std::string& s) {
        for (auto& fn : hashFns)
            bits[fn(s) % bits.size()] = true;
    }

    bool test(const std::string& s) const {
        for (auto& fn : hashFns) {
            if (!bits[fn(s) % bits.size()]) return false;   // 有一位为 0 → 一定不存在
        }
        return true;                                        // 全 1 → 可能存在
    }
};

int main() {
    // 两个不同的哈希函数（教学用；生产用不同 seed 的 murmur/xxhash）
    std::vector<std::function<size_t(const std::string&)>> fns = {
        [](const std::string& s) { return std::hash<std::string>{}(s); },
        [](const std::string& s) {                          // FNV-1a
            size_t h = 1469598103934665603ULL;
            for (char c : s) { h ^= (size_t)(unsigned char)c; h *= 1099511628211ULL; }
            return h;
        }
    };
    BloomFilter bf(1000, fns);
    bf.add("hello");
    std::cout << std::boolalpha
              << "test(hello) = " << bf.test("hello") << "\n"   // true（一定被加过）
              << "test(world) = " << bf.test("world") << "\n";  // 多半 false（一定不存在，除非碰撞）
    return 0;
}

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

int main() {
    std::unordered_map<std::string, int> m;
    m.reserve(16);                 // 预分配桶，减少 rehash（4. 预分配减少 rehash）

    m["a"] = 1;
    m["b"] = 2;
    m["a"]++;                      // 已存在则更新

    // 查找：先判断存在再取值（operator[] 会插入默认值，只读用 find/count）
    auto it = m.find("a");
    if (it != m.end())
        std::cout << "a = " << it->second << "\n";     // a = 2
    std::cout << "count(c) = " << m.count("c") << "\n"; // 0（不存在）

    // 2. 遍历顺序不保证（哈希桶顺序，不同实现/rehash 后都可能变）
    for (auto& kv : m) std::cout << kv.first << ":" << kv.second << " ";
    std::cout << "\n";
    // 1. 并发：std::unordered_map 非线程安全，多线程需 std::shared_mutex
    //    （读 std::shared_lock、写 std::unique_lock）
    return 0;
}