主题
数据结构源码
数据结构与算法里每个知识点的完整实现,共 27 个单文件、无外部依赖的 .cpp。用 g++ -std=c++17 文件名.cpp -o demo 即可编译。
右侧目录按编号排列,点击可跳转;每段默认折叠,展开后可直接阅读和复制。
01 动态数组
展开源码
cpp
// 01_vector.cpp —— 手写动态数组
// 覆盖:三指针语义、2 倍扩容、size/capacity、reserve/resize、深拷贝、移动语义
// 对应《3. 数据结构.md》§二.2、§二.3、§八.3
#include <cstddef>
#include <stdexcept>
#include <utility>
class MyVector {
public:
MyVector() = default;
explicit MyVector(std::size_t n) : data_(new int[n]()), size_(n), cap_(n) {}
~MyVector() { delete[] data_; }
MyVector(const MyVector& other)
: data_(other.size_ ? new int[other.size_] : nullptr),
size_(other.size_), cap_(other.size_) {
for (std::size_t i = 0; i < size_; ++i) data_[i] = other.data_[i];
}
MyVector& operator=(const MyVector& other) {
if (this != &other) {
MyVector tmp(other); // 拷贝再交换,异常安全
swap(tmp);
}
return *this;
}
MyVector(MyVector&& other) noexcept
: data_(other.data_), size_(other.size_), cap_(other.cap_) {
other.data_ = nullptr;
other.size_ = other.cap_ = 0;
}
MyVector& operator=(MyVector&& other) noexcept {
if (this != &other) {
delete[] data_;
data_ = other.data_;
size_ = other.size_;
cap_ = other.cap_;
other.data_ = nullptr;
other.size_ = other.cap_ = 0;
}
return *this;
}
void swap(MyVector& other) noexcept {
std::swap(data_, other.data_);
std::swap(size_, other.size_);
std::swap(cap_, other.cap_);
}
void push_back(int value) {
if (size_ == cap_) reserve(cap_ ? cap_ * 2 : 1); // 均摊 O(1)
data_[size_++] = value;
}
void pop_back() {
if (size_ > 0) --size_;
}
void reserve(std::size_t new_cap) {
if (new_cap <= cap_) return; // 只增不减
int* new_data = new int[new_cap];
for (std::size_t i = 0; i < size_; ++i) new_data[i] = data_[i];
delete[] data_;
data_ = new_data;
cap_ = new_cap;
}
void resize(std::size_t new_size, int value = 0) {
if (new_size > cap_) reserve(new_size);
for (std::size_t i = size_; i < new_size; ++i) data_[i] = value;
size_ = new_size;
}
void clear() noexcept { size_ = 0; } // 不释放 capacity
void shrink_to_fit() { // 标准语义是"请求"
if (size_ == cap_) return;
if (size_ == 0) {
delete[] data_;
data_ = nullptr;
cap_ = 0;
return;
}
int* p = new int[size_];
for (std::size_t i = 0; i < size_; ++i) p[i] = data_[i];
delete[] data_;
data_ = p;
cap_ = size_;
}
int& operator[](std::size_t i) { return data_[i]; }
const int& operator[](std::size_t i) const { return data_[i]; }
int& at(std::size_t i) {
if (i >= size_) throw std::out_of_range("MyVector::at");
return data_[i];
}
const int& at(std::size_t i) const {
if (i >= size_) throw std::out_of_range("MyVector::at");
return data_[i];
}
int& front() { return data_[0]; }
int& back() { return data_[size_ - 1]; }
int* begin() noexcept { return data_; }
int* end() noexcept { return data_ + size_; }
const int* begin() const noexcept { return data_; }
const int* end() const noexcept { return data_ + size_; }
std::size_t size() const noexcept { return size_; }
std::size_t capacity() const noexcept { return cap_; }
bool empty() const noexcept { return size_ == 0; }
int* data() noexcept { return data_; }
private:
int* data_ = nullptr;
std::size_t size_ = 0;
std::size_t cap_ = 0;
};02 链表
展开源码
cpp
// 02_linked_list.cpp —— 链表高频题
// 覆盖:反转、判环、环入口、合并、倒数第 k、相交、随机指针复制、K 个一组、排序、回文
// 对应《3. 数据结构.md》§二.8
#include <unordered_map>
#include <vector>
struct ListNode {
int val;
ListNode* next;
explicit ListNode(int v) : val(v), next(nullptr) {}
};
struct RandomNode {
int val;
RandomNode* next;
RandomNode* random;
explicit RandomNode(int v) : val(v), next(nullptr), random(nullptr) {}
};
class LinkedListProblems {
public:
// 反转链表:prev / cur / next 三指针
static ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
// 快慢指针判环
static bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
// 环入口:相遇后一个指针回到 head,同速再相遇
static ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode* p = head;
while (p != slow) {
p = p->next;
slow = slow->next;
}
return p;
}
}
return nullptr;
}
// 合并两个有序链表:dummy 哨兵
static ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (a && b) {
if (a->val <= b->val) { tail->next = a; a = a->next; }
else { tail->next = b; b = b->next; }
tail = tail->next;
}
tail->next = a ? a : b;
return dummy.next;
}
// 删除倒数第 n 个:快指针先走 n 步
static ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0);
dummy.next = head;
ListNode* fast = &dummy;
ListNode* slow = &dummy;
for (int i = 0; i < n; ++i) fast = fast->next;
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
ListNode* victim = slow->next;
slow->next = victim->next;
delete victim; // LeetCode 环境可去掉
return dummy.next;
}
// 相交链表:长度差对齐
static ListNode* getIntersectionNode(ListNode* a, ListNode* b) {
int lenA = 0, lenB = 0;
for (ListNode* p = a; p; p = p->next) ++lenA;
for (ListNode* p = b; p; p = p->next) ++lenB;
while (lenA > lenB) { a = a->next; --lenA; }
while (lenB > lenA) { b = b->next; --lenB; }
while (a != b) { a = a->next; b = b->next; }
return a;
}
// 复制带随机指针的链表:哈希存「原节点 -> 新节点」
static RandomNode* copyRandomList(RandomNode* head) {
if (!head) return nullptr;
std::unordered_map<RandomNode*, RandomNode*> mp;
for (RandomNode* p = head; p; p = p->next)
mp[p] = new RandomNode(p->val);
for (RandomNode* p = head; p; p = p->next) {
mp[p]->next = p->next ? mp[p->next] : nullptr;
mp[p]->random = p->random ? mp[p->random] : nullptr;
}
return mp[head];
}
// K 个一组翻转
static ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(0);
dummy.next = head;
ListNode* groupPrev = &dummy;
while (true) {
ListNode* kth = groupPrev;
for (int i = 0; i < k && kth; ++i) kth = kth->next;
if (!kth) break; // 不足 k 个,保持原样
ListNode* groupNext = kth->next;
ListNode* prev = groupNext;
ListNode* cur = groupPrev->next;
while (cur != groupNext) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
ListNode* oldStart = groupPrev->next;
groupPrev->next = kth; // kth 成为新头
groupPrev = oldStart; // 旧头变成组尾
}
return dummy.next;
}
// 链表排序:归并,O(n log n)、O(log n) 递归栈
static ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* slow = head;
ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow->next;
slow->next = nullptr;
return mergeTwoLists(sortList(head), sortList(mid));
}
// 回文链表:找中点 + 反转后半 + 比较
static bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* second = reverseList(slow);
ListNode* first = head;
while (second) {
if (first->val != second->val) return false;
first = first->next;
second = second->next;
}
return true;
}
// 方便构造测试链表(LeetCode 里通常不需要)
static ListNode* build(const std::vector<int>& values) {
ListNode dummy(0);
ListNode* tail = &dummy;
for (int v : values) {
tail->next = new ListNode(v);
tail = tail->next;
}
return dummy.next;
}
};03 LRU 缓存
展开源码
cpp
// 03_lru_cache.cpp —— LRU Cache
// 哈希表 O(1) 定位 + 双向链表 O(1) 维护顺序
// 对应《3. 数据结构.md》§七.1
#include <list>
#include <unordered_map>
#include <utility>
class LRUCache {
public:
explicit LRUCache(int capacity) : cap_(capacity) {}
int get(int key) {
auto it = mp_.find(key);
if (it == mp_.end()) return -1;
// splice 在链表内部 O(1) 移动节点,不失效迭代器
lst_.splice(lst_.begin(), lst_, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = mp_.find(key);
if (it != mp_.end()) {
it->second->second = value;
lst_.splice(lst_.begin(), lst_, it->second);
return;
}
if (static_cast<int>(lst_.size()) == cap_) {
mp_.erase(lst_.back().first);
lst_.pop_back();
}
lst_.emplace_front(key, value);
mp_[key] = lst_.begin();
}
private:
int cap_;
std::list<std::pair<int, int>> lst_; // front = 最近使用,back = 最久未使用
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> mp_;
};
// 并发追问:全局锁最简单,但争用大;工程上常按 key 哈希分片,
// 每个分片一个独立 LRU + 独立互斥锁,降低锁粒度。04 LFU 缓存
展开源码
cpp
// 04_lfu_cache.cpp —— LFU Cache(O(1) 版本)
// key -> {value, freq, 在频次链表中的位置}
// freq -> 该频次下的 key 链表(链表内按 LRU 顺序,front 为最近使用)
// 维护 minFreq,用于 O(1) 找到要淘汰的频次
// 对应《3. 数据结构.md》§七.2
#include <list>
#include <unordered_map>
class LFUCache {
public:
explicit LFUCache(int capacity) : cap_(capacity) {}
int get(int key) {
auto it = keyMap_.find(key);
if (it == keyMap_.end()) return -1;
touch(key);
return it->second.value;
}
void put(int key, int value) {
if (cap_ <= 0) return;
auto it = keyMap_.find(key);
if (it != keyMap_.end()) {
it->second.value = value;
touch(key);
return;
}
if (static_cast<int>(keyMap_.size()) == cap_) {
// minFreq_ 对应的链表尾部就是最该淘汰的 key
int victim = freqMap_[minFreq_].back();
freqMap_[minFreq_].pop_back();
pos_.erase(victim);
keyMap_.erase(victim);
}
keyMap_[key] = {value, 1};
freqMap_[1].push_front(key);
pos_[key] = freqMap_[1].begin();
minFreq_ = 1;
}
private:
struct Entry {
int value;
int freq;
};
// 把 key 从当前频次链表移到 freq+1 的链表头部
void touch(int key) {
Entry& e = keyMap_[key];
auto& oldList = freqMap_[e.freq];
oldList.erase(pos_[key]);
if (oldList.empty() && minFreq_ == e.freq) ++minFreq_;
++e.freq;
auto& newList = freqMap_[e.freq];
newList.push_front(key);
pos_[key] = newList.begin();
}
int cap_;
int minFreq_ = 0;
std::unordered_map<int, Entry> keyMap_;
std::unordered_map<int, std::list<int>> freqMap_;
std::unordered_map<int, std::list<int>::iterator> pos_;
};05 最小栈
展开源码
cpp
// 05_min_stack.cpp —— 最小栈
// 两个栈:data 存数据,mins 存「当前最小值」
// push / pop / top / getMin 全部 O(1)
// 对应《3. 数据结构.md》§七.3
#include <algorithm>
#include <stack>
class MinStack {
public:
void push(int x) {
data_.push(x);
mins_.push(mins_.empty() ? x : std::min(x, mins_.top()));
}
void pop() {
data_.pop();
mins_.pop();
}
int top() const { return data_.top(); }
int getMin() const { return mins_.top(); }
bool empty() const { return data_.empty(); }
private:
std::stack<int> data_;
std::stack<int> mins_;
};06 双栈队列
展开源码
cpp
// 06_queue_by_two_stacks.cpp —— 两个栈实现队列 / 一个队列实现栈
// 对应《3. 数据结构.md》§七.4
#include <cstddef>
#include <queue>
#include <stack>
// 队列:in 负责入队,out 负责出队
class MyQueue {
public:
void push(int x) { in_.push(x); }
int pop() {
transfer();
int v = out_.top();
out_.pop();
return v;
}
int peek() {
transfer();
return out_.top();
}
bool empty() const { return in_.empty() && out_.empty(); }
private:
void transfer() {
if (!out_.empty()) return;
while (!in_.empty()) {
out_.push(in_.top());
in_.pop();
}
}
std::stack<int> in_;
std::stack<int> out_;
};
// 栈:每次 push 后把前面的元素转到后面,队首始终是栈顶
class MyStack {
public:
void push(int x) {
q_.push(x);
for (std::size_t i = 0; i + 1 < q_.size(); ++i) {
q_.push(q_.front());
q_.pop();
}
}
int pop() {
int v = q_.front();
q_.pop();
return v;
}
int top() { return q_.front(); }
bool empty() const { return q_.empty(); }
private:
std::queue<int> q_;
};07 哈希表
展开源码
cpp
// 07_hash_table.cpp —— 手写哈希表(链地址法 + rehash)
// 对应《3. 数据结构.md》§三.1、§三.2
#include <cstddef>
#include <functional>
#include <vector>
class MyHashMap {
public:
MyHashMap() : buckets_(8, nullptr) {}
~MyHashMap() { clear(); }
MyHashMap(const MyHashMap&) = delete;
MyHashMap& operator=(const MyHashMap&) = delete;
void put(int key, int value) {
std::size_t idx = bucketIndex(key);
for (Node* p = buckets_[idx]; p; p = p->next) {
if (p->key == key) { p->value = value; return; }
}
buckets_[idx] = new Node(key, value, buckets_[idx]);
++size_;
if (size_ > buckets_.size() * kMaxLoad) rehash(buckets_.size() * 2);
}
int get(int key) const {
for (Node* p = buckets_[bucketIndex(key)]; p; p = p->next) {
if (p->key == key) return p->value;
}
return -1;
}
void remove(int key) {
Node** pp = &buckets_[bucketIndex(key)];
while (*pp) {
if ((*pp)->key == key) {
Node* victim = *pp;
*pp = victim->next;
delete victim;
--size_;
return;
}
pp = &(*pp)->next;
}
}
std::size_t size() const { return size_; }
private:
struct Node {
int key;
int value;
Node* next;
Node(int k, int v, Node* n) : key(k), value(v), next(n) {}
};
static constexpr double kMaxLoad = 0.75;
std::size_t bucketIndex(int key) const {
return std::hash<int>{}(key) % buckets_.size();
}
void rehash(std::size_t newCount) {
std::vector<Node*> old;
old.swap(buckets_);
buckets_.assign(newCount, nullptr);
size_ = 0;
for (Node* head : old) {
while (head) {
Node* next = head->next; // 先保存 next 再改链
std::size_t idx = bucketIndex(head->key);
head->next = buckets_[idx];
buckets_[idx] = head;
++size_;
head = next;
}
}
}
void clear() {
for (Node*& head : buckets_) {
while (head) {
Node* next = head->next;
delete head;
head = next;
}
}
buckets_.clear();
size_ = 0;
}
std::vector<Node*> buckets_;
std::size_t size_ = 0;
};08 二叉堆
展开源码
cpp
// 08_binary_heap.cpp —— 手写堆 + TopK
// 默认 std::less 是大顶堆;传 std::greater 得到小顶堆
// 对应《3. 数据结构.md》§四.7、§四.8
#include <cstddef>
#include <functional>
#include <utility>
#include <vector>
template <class Compare = std::less<int>>
class BinaryHeap {
public:
BinaryHeap() = default;
explicit BinaryHeap(Compare comp) : comp_(comp) {}
explicit BinaryHeap(std::vector<int> values) : data_(std::move(values)) {
build();
}
void push(int x) {
data_.push_back(x);
siftUp(data_.size() - 1);
}
int pop() {
int top = data_.front();
data_.front() = data_.back();
data_.pop_back();
if (!data_.empty()) siftDown(0);
return top;
}
int top() const { return data_.front(); }
bool empty() const { return data_.empty(); }
std::size_t size() const { return data_.size(); }
// 从最后一个非叶子节点开始下沉,O(n)
void build() {
for (int i = static_cast<int>(data_.size()) / 2 - 1; i >= 0; --i)
siftDown(static_cast<std::size_t>(i));
}
// 取最大的 k 个元素:维护大小为 k 的小顶堆
static std::vector<int> topK(const std::vector<int>& nums, std::size_t k) {
BinaryHeap<std::greater<int>> heap; // 小顶堆
for (int x : nums) {
if (heap.size() < k) {
heap.push(x);
} else if (x > heap.top()) {
heap.pop();
heap.push(x);
}
}
std::vector<int> res;
res.reserve(heap.size());
while (!heap.empty()) res.push_back(heap.pop()); // 升序
return res;
}
private:
void siftUp(std::size_t i) {
while (i > 0) {
std::size_t parent = (i - 1) / 2;
// comp_ 为 true 表示 parent 的优先级低于 child
if (!comp_(data_[parent], data_[i])) break;
std::swap(data_[parent], data_[i]);
i = parent;
}
}
void siftDown(std::size_t i) {
std::size_t n = data_.size();
while (true) {
std::size_t best = i;
std::size_t left = 2 * i + 1;
std::size_t right = 2 * i + 2;
if (left < n && comp_(data_[best], data_[left])) best = left;
if (right < n && comp_(data_[best], data_[right])) best = right;
if (best == i) break;
std::swap(data_[i], data_[best]);
i = best;
}
}
std::vector<int> data_;
Compare comp_{};
};09 二叉树遍历
展开源码
cpp
// 09_binary_tree_traversal.cpp —— 二叉树遍历
// 前序 / 中序 / 后序(迭代)+ 层序 + 最大深度
// 对应《3. 数据结构.md》§四.1
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
class TreeTraversal {
public:
// 根 -> 左 -> 右:栈先压右再压左
static std::vector<int> preorder(TreeNode* root) {
std::vector<int> res;
if (!root) return res;
std::stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
res.push_back(node->val);
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
return res;
}
// 左 -> 根 -> 右:一路向左入栈,弹栈访问,转向右子树
static std::vector<int> inorder(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;
}
// 后序:按「根 -> 右 -> 左」遍历后整体反转
static std::vector<int> postorder(TreeNode* root) {
std::vector<int> res;
if (!root) return res;
std::stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
res.push_back(node->val);
if (node->left) st.push(node->left);
if (node->right) st.push(node->right);
}
std::reverse(res.begin(), res.end());
return res;
}
// 层序:每层先记录 size
static 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 levelSize = static_cast<int>(q.size());
std::vector<int> level;
level.reserve(levelSize);
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res.push_back(std::move(level));
}
return res;
}
static int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}
};10 二叉搜索树
展开源码
cpp
// 10_bst.cpp —— 二叉搜索树
// 增删查 + 验证 BST + BST 最近公共祖先 + 第 k 小
// 对应《3. 数据结构.md》§四.3
#include <limits>
#include <stack>
class BST {
public:
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
BST() = default;
~BST() { destroy(root_); }
BST(const BST&) = delete;
BST& operator=(const BST&) = delete;
void insert(int val) { root_ = insert(root_, val); }
bool contains(int val) const { return contains(root_, val); }
void erase(int val) { root_ = erase(root_, val); }
bool empty() const { return root_ == nullptr; }
// 不能只比较父子,要传上下界
static bool isValidBST(TreeNode* root) {
return validate(root, std::numeric_limits<long long>::lowest(),
std::numeric_limits<long long>::max());
}
// BST 的 LCA:两个值都小往左,都大往右,否则当前就是
static TreeNode* lca(TreeNode* root, int p, int q) {
while (root) {
if (p < root->val && q < root->val) root = root->left;
else if (p > root->val && q > root->val) root = root->right;
else return root;
}
return nullptr;
}
// 第 k 小:中序遍历计数
static int kthSmallest(TreeNode* root, int k) {
std::stack<TreeNode*> st;
TreeNode* cur = root;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
if (--k == 0) return cur->val;
cur = cur->right;
}
return -1; // k 非法
}
private:
static TreeNode* insert(TreeNode* node, int val) {
if (!node) return new TreeNode(val);
if (val < node->val) node->left = insert(node->left, val);
else if (val > node->val) node->right = insert(node->right, val);
return node; // 重复值不插入
}
static bool contains(const TreeNode* node, int val) {
while (node) {
if (val == node->val) return true;
node = val < node->val ? node->left : node->right;
}
return false;
}
static TreeNode* erase(TreeNode* node, int val) {
if (!node) return nullptr;
if (val < node->val) {
node->left = erase(node->left, val);
return node;
}
if (val > node->val) {
node->right = erase(node->right, val);
return node;
}
// 找到:0 / 1 个孩子直接顶替
if (!node->left) {
TreeNode* right = node->right;
delete node;
return right;
}
if (!node->right) {
TreeNode* left = node->left;
delete node;
return left;
}
// 两个孩子:用中序后继替换值,再删除后继
TreeNode* succ = minNode(node->right);
node->val = succ->val;
node->right = erase(node->right, succ->val);
return node;
}
static TreeNode* minNode(TreeNode* node) {
while (node->left) node = node->left;
return node;
}
static bool validate(TreeNode* node, long long lower, long long upper) {
if (!node) return true;
if (node->val <= lower || node->val >= upper) return false;
return validate(node->left, lower, node->val) &&
validate(node->right, node->val, upper);
}
static void destroy(TreeNode* node) {
if (!node) return;
destroy(node->left);
destroy(node->right);
delete node;
}
TreeNode* root_ = nullptr;
};11 AVL 树
展开源码
cpp
// 11_avl.cpp —— AVL 树:四种旋转 + 插入 + 删除
// LL -> 右旋;RR -> 左旋;LR -> 先左旋孩子再右旋;RL -> 先右旋孩子再左旋
// 对应《3. 数据结构.md》§四.4
#include <algorithm>
#include <vector>
class AVLTree {
public:
struct Node {
int val;
int height;
Node* left;
Node* right;
explicit Node(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};
AVLTree() = default;
~AVLTree() { destroy(root_); }
AVLTree(const AVLTree&) = delete;
AVLTree& operator=(const AVLTree&) = delete;
void insert(int val) { root_ = insert(root_, val); }
void erase(int val) { root_ = erase(root_, val); }
bool empty() const { return root_ == nullptr; }
std::vector<int> inorder() const {
std::vector<int> res;
inorder(root_, res);
return res;
}
private:
static int height(const Node* node) { return node ? node->height : 0; }
static int balanceFactor(const Node* node) {
return height(node->left) - height(node->right);
}
static void update(Node* node) {
node->height = 1 + std::max(height(node->left), height(node->right));
}
/* 右旋示意(把 y 的左孩子 x 提上来):
y x
/ \ / \
x T3 -> T1 y
/ \ / \
T1 T2 T2 T3
*/
static Node* rotateRight(Node* y) {
Node* x = y->left;
Node* t2 = x->right;
x->right = y;
y->left = t2;
update(y);
update(x);
return x;
}
static Node* rotateLeft(Node* x) {
Node* y = x->right;
Node* t2 = y->left;
y->left = x;
x->right = t2;
update(x);
update(y);
return y;
}
static Node* balance(Node* node) {
update(node);
int bf = balanceFactor(node);
if (bf > 1) { // 左重
if (balanceFactor(node->left) < 0) // LR
node->left = rotateLeft(node->left);
return rotateRight(node); // LL / LR 收尾
}
if (bf < -1) { // 右重
if (balanceFactor(node->right) > 0) // RL
node->right = rotateRight(node->right);
return rotateLeft(node); // RR / RL 收尾
}
return node;
}
static Node* insert(Node* node, int val) {
if (!node) return new Node(val);
if (val < node->val) node->left = insert(node->left, val);
else if (val > node->val) node->right = insert(node->right, val);
else return node; // 重复值不插入
return balance(node);
}
static Node* erase(Node* node, int val) {
if (!node) return nullptr;
if (val < node->val) {
node->left = erase(node->left, val);
} else if (val > node->val) {
node->right = erase(node->right, val);
} else {
if (!node->left || !node->right) {
Node* child = node->left ? node->left : node->right;
delete node;
return child; // 子树本身平衡
}
Node* succ = minNode(node->right);
node->val = succ->val;
node->right = erase(node->right, succ->val);
}
return balance(node);
}
static Node* minNode(Node* node) {
while (node->left) node = node->left;
return node;
}
static void inorder(const Node* node, std::vector<int>& out) {
if (!node) return;
inorder(node->left, out);
out.push_back(node->val);
inorder(node->right, out);
}
static void destroy(Node* node) {
if (!node) return;
destroy(node->left);
destroy(node->right);
delete node;
}
Node* root_ = nullptr;
};12 前缀树
展开源码
cpp
// 12_trie.cpp —— Trie 前缀树
// insert / search / startsWith 均为 O(L)
// 对应《3. 数据结构.md》§四.9
#include <string>
class Trie {
public:
Trie() : root_(new Node()) {}
~Trie() { destroy(root_); }
Trie(const Trie&) = delete;
Trie& operator=(const Trie&) = delete;
void insert(const std::string& word) {
Node* cur = root_;
for (char c : word) {
int idx = c - 'a';
if (!cur->child[idx]) cur->child[idx] = new Node();
cur = cur->child[idx];
}
cur->end = true;
}
bool search(const std::string& word) const {
const Node* node = findNode(word);
return node && node->end;
}
bool startsWith(const std::string& prefix) const {
return findNode(prefix) != nullptr;
}
private:
struct Node {
Node* child[26] = {};
bool end = false;
};
const Node* findNode(const std::string& s) const {
const Node* cur = root_;
for (char c : s) {
int idx = c - 'a';
if (idx < 0 || idx >= 26) return nullptr;
cur = cur->child[idx];
if (!cur) return nullptr;
}
return cur;
}
static void destroy(Node* node) {
if (!node) return;
for (Node* child : node->child) destroy(child);
delete node;
}
Node* root_;
};13 并查集
展开源码
cpp
// 13_union_find.cpp —— 并查集
// 路径压缩 + 按秩合并,单次操作摊还 O(α(n)) ≈ O(1)
// 对应《3. 数据结构.md》§六.7
#include <numeric>
#include <utility>
#include <vector>
class UnionFind {
public:
explicit UnionFind(int n) : parent_(n), rank_(n, 0), count_(n) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int x) {
while (parent_[x] != x) {
parent_[x] = parent_[parent_[x]]; // 路径减半
x = parent_[x];
}
return x;
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (rank_[a] < rank_[b]) std::swap(a, b);
parent_[b] = a;
if (rank_[a] == rank_[b]) ++rank_[a];
--count_;
return true;
}
bool connected(int a, int b) { return find(a) == find(b); }
int count() const { return count_; }
private:
std::vector<int> parent_;
std::vector<int> rank_;
int count_;
};14 拓扑排序
展开源码
cpp
// 14_topo_sort.cpp —— 拓扑排序
// Kahn(入度队列,可判环)+ DFS 三色(可判环)
// 对应《3. 数据结构.md》§六.3
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
class TopoSort {
public:
// edges: {from, to} 表示 from -> to
static std::vector<int> kahn(int n, const std::vector<std::pair<int, int>>& edges) {
std::vector<std::vector<int>> adj(n);
std::vector<int> indeg(n, 0);
for (const auto& [u, v] : edges) {
adj[u].push_back(v);
++indeg[v];
}
std::queue<int> q;
for (int i = 0; i < n; ++i) {
if (indeg[i] == 0) q.push(i);
}
std::vector<int> order;
order.reserve(n);
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : adj[u]) {
if (--indeg[v] == 0) q.push(v);
}
}
// 输出节点数不足 n,说明有环
return static_cast<int>(order.size()) == n ? order : std::vector<int>{};
}
// DFS 三色:0 未访问,1 访问中,2 已完成
static std::vector<int> dfs(int n, const std::vector<std::pair<int, int>>& edges) {
std::vector<std::vector<int>> adj(n);
for (const auto& [u, v] : edges) adj[u].push_back(v);
std::vector<int> state(n, 0);
std::vector<int> order;
order.reserve(n);
bool hasCycle = false;
auto visit = [&](auto&& self, int u) -> void {
state[u] = 1;
for (int v : adj[u]) {
if (state[v] == 1) { // 遇到访问中的节点 -> 有环
hasCycle = true;
return;
}
if (state[v] == 0) {
self(self, v);
if (hasCycle) return;
}
}
state[u] = 2;
order.push_back(u); // 后序
};
for (int i = 0; i < n; ++i) {
if (state[i] == 0) visit(visit, i);
}
if (hasCycle) return {};
std::reverse(order.begin(), order.end()); // 后序的逆序才是拓扑序
return order;
}
};15 Dijkstra 最短路
展开源码
cpp
// 15_dijkstra.cpp —— Dijkstra 单源最短路(非负权)
// 优先队列 + 惰性删除,O((V + E) log V)
// 对应《3. 数据结构.md》§六.4
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
class Dijkstra {
public:
struct Edge {
int to;
int w;
};
// adj[u] 存 u 出发的边;返回 dist 数组,不可达为 INF/2
static std::vector<long long> shortest(
int n, const std::vector<std::vector<Edge>>& adj, int src) {
const long long INF = std::numeric_limits<long long>::max() / 2;
std::vector<long long> dist(n, INF);
dist[src] = 0;
using State = std::pair<long long, int>; // {dist, node}
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // 惰性删除:过期状态
for (const Edge& e : adj[u]) {
if (dist[u] + e.w < dist[e.to]) {
dist[e.to] = dist[u] + e.w;
pq.push({dist[e.to], e.to});
}
}
}
return dist;
}
};16 快速排序
展开源码
cpp
// 16_quick_sort.cpp —— 快速排序 + 快速选择
// 三数取中、小区间插入排序、先递归较小一侧控制栈深
// 对应《3. 数据结构.md》§五.2
#include <algorithm>
#include <utility>
#include <vector>
class QuickSort {
public:
static void sort(std::vector<int>& a) {
if (a.size() > 1)
sortRange(a, 0, static_cast<int>(a.size()) - 1);
}
// 第 k 小(1 <= k <= size),平均 O(n),最坏 O(n²)
static int quickSelect(std::vector<int>& a, int k) {
int l = 0;
int r = static_cast<int>(a.size()) - 1;
int target = k - 1;
while (l <= r) {
int p = partition(a, l, r);
if (p == target) return a[p];
if (p < target) l = p + 1;
else r = p - 1;
}
return -1; // k 非法
}
private:
static void sortRange(std::vector<int>& a, int l, int r) {
while (l < r) {
if (r - l < 16) {
insertionSort(a, l, r);
return;
}
int p = partition(a, l, r);
// 先递归较小的一侧,较大的一侧循环处理,栈深 O(log n)
if (p - l < r - p) {
sortRange(a, l, p - 1);
l = p + 1;
} else {
sortRange(a, p + 1, r);
r = p - 1;
}
}
}
static void insertionSort(std::vector<int>& a, int l, int r) {
for (int i = l + 1; i <= r; ++i) {
int value = a[i];
int j = i - 1;
while (j >= l && a[j] > value) {
a[j + 1] = a[j];
--j;
}
a[j + 1] = value;
}
}
static int partition(std::vector<int>& a, int l, int r) {
// 三数取中,避免有序输入退化为 O(n²)
int mid = l + (r - l) / 2;
if (a[mid] < a[l]) std::swap(a[mid], a[l]);
if (a[r] < a[l]) std::swap(a[r], a[l]);
if (a[r] < a[mid]) std::swap(a[r], a[mid]);
std::swap(a[l], a[mid]); // 中位数放到 l 作为 pivot
int pivot = a[l];
int i = l;
for (int j = l + 1; j <= r; ++j) {
if (a[j] < pivot) std::swap(a[++i], a[j]);
}
std::swap(a[l], a[i]);
return i;
}
};17 归并排序
展开源码
cpp
// 17_merge_sort.cpp —— 归并排序 + 逆序对
// 稳定排序,O(n log n),额外空间 O(n)
// 对应《3. 数据结构.md》§五.3
#include <vector>
class MergeSort {
public:
static void sort(std::vector<int>& a) {
if (a.size() < 2) return;
std::vector<int> tmp(a.size());
sortRange(a, tmp, 0, static_cast<int>(a.size()) - 1);
}
// 求逆序对数量:合并时 a[i] > a[j] 则 a[i..mid] 都大于 a[j]
static long long countInversions(std::vector<int> a) {
if (a.size() < 2) return 0;
std::vector<int> tmp(a.size());
return countRange(a, tmp, 0, static_cast<int>(a.size()) - 1);
}
private:
static void sortRange(std::vector<int>& a, std::vector<int>& tmp, int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
sortRange(a, tmp, l, mid);
sortRange(a, tmp, mid + 1, r);
int i = l;
int j = mid + 1;
int k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[k++] = a[i++]; // <= 保证稳定
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int p = l; p <= r; ++p) a[p] = tmp[p];
}
static long long countRange(std::vector<int>& a, std::vector<int>& tmp, int l, int r) {
if (l >= r) return 0;
int mid = l + (r - l) / 2;
long long inv = countRange(a, tmp, l, mid) + countRange(a, tmp, mid + 1, r);
int i = l;
int j = mid + 1;
int k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
tmp[k++] = a[j++];
inv += mid - i + 1; // 一次合并的贡献
}
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int p = l; p <= r; ++p) a[p] = tmp[p];
return inv;
}
};18 堆排序
展开源码
cpp
// 18_heap_sort.cpp —— 堆排序
// 建堆 O(n) + n 次取堆顶 O(n log n),原地、不稳定
// 对应《3. 数据结构.md》§五.4
#include <utility>
#include <vector>
class HeapSort {
public:
static void sort(std::vector<int>& a) {
int n = static_cast<int>(a.size());
// 建大顶堆:从最后一个非叶子节点开始下沉
for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, i, n);
// 每次把堆顶换到末尾,缩小堆范围
for (int end = n - 1; end > 0; --end) {
std::swap(a[0], a[end]);
siftDown(a, 0, end);
}
}
private:
static void siftDown(std::vector<int>& a, int i, int n) {
while (true) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && a[left] > a[largest]) largest = left;
if (right < n && a[right] > a[largest]) largest = right;
if (largest == i) break;
std::swap(a[i], a[largest]);
i = largest;
}
}
};19 二分查找
展开源码
cpp
// 19_binary_search.cpp —— 二分查找与二分答案
// lower_bound / upper_bound / 旋转数组 / 峰值 / 分割数组 / sqrt
// 对应《3. 数据结构.md》§五.6、§五.7
#include <algorithm>
#include <vector>
class BinarySearch {
public:
// 第一个 >= target
static int lowerBound(const std::vector<int>& a, int target) {
int l = 0;
int r = static_cast<int>(a.size()); // [l, r)
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] < target) l = mid + 1;
else r = mid;
}
return l;
}
// 第一个 > target
static int upperBound(const std::vector<int>& a, int target) {
int l = 0;
int r = static_cast<int>(a.size());
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] <= target) l = mid + 1;
else r = mid;
}
return l;
}
// 旋转有序数组:先判断哪一半有序
static int searchRotated(const std::vector<int>& a, int target) {
if (a.empty()) return -1;
int l = 0;
int r = static_cast<int>(a.size()) - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == target) return mid;
if (a[l] <= a[mid]) { // 左半有序
if (a[l] <= target && target < a[mid]) r = mid - 1;
else l = mid + 1;
} else { // 右半有序
if (a[mid] < target && target <= a[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
// 峰值下标:比右边小就往右走,否则往左收
static int findPeak(const std::vector<int>& a) {
if (a.empty()) return -1;
int l = 0;
int r = static_cast<int>(a.size()) - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] < a[mid + 1]) l = mid + 1;
else r = mid;
}
return l;
}
// 分割数组的最大值:最小化 m 段中的最大和
static int splitArrayMinMax(const std::vector<int>& a, int m) {
int lo = 0;
long long hi = 0;
for (int x : a) {
lo = std::max(lo, x); // 下界:单个元素
hi += x; // 上界:全部放一段
}
while (lo < hi) {
int mid = lo + static_cast<int>((hi - lo) / 2);
if (canSplit(a, m, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
static int mySqrt(int x) {
if (x < 2) return x;
int l = 1;
int r = x / 2;
while (l <= r) {
int mid = l + (r - l) / 2;
long long sq = 1LL * mid * mid;
if (sq == x) return mid;
if (sq < x) l = mid + 1;
else r = mid - 1;
}
return r;
}
private:
static bool canSplit(const std::vector<int>& a, int m, int limit) {
int parts = 1;
long long sum = 0;
for (int x : a) {
if (sum + x > limit) {
++parts;
sum = x;
if (parts > m) return false;
} else {
sum += x;
}
}
return true;
}
};20 无锁环形队列
展开源码
cpp
// 20_ring_buffer_spsc.cpp —— 无锁 SPSC 环形队列
// 容量必须是 2 的幂;牺牲一个槽位区分空 / 满
// 生产者只写 tail_,消费者只写 head_,acquire/release 建立 happens-before
// 对应《3. 数据结构.md》§二.7、§七.8
#include <atomic>
#include <cstddef>
#include <stdexcept>
#include <vector>
template <typename T>
class SpscRingBuffer {
public:
explicit SpscRingBuffer(std::size_t capacity)
: buffer_(capacity), mask_(capacity - 1) {
if (capacity < 2 || (capacity & (capacity - 1)) != 0)
throw std::invalid_argument("capacity must be a power of two >= 2");
}
bool push(const T& value) {
const std::size_t tail = tail_.load(std::memory_order_relaxed);
const std::size_t next = (tail + 1) & mask_;
// 先读对方下标,再写数据:acquire 保证能看到消费者的释放
if (next == head_.load(std::memory_order_acquire)) return false;
buffer_[tail] = value;
tail_.store(next, std::memory_order_release); // 发布:数据先可见
return true;
}
bool pop(T& out) {
const std::size_t head = head_.load(std::memory_order_relaxed);
if (head == tail_.load(std::memory_order_acquire)) return false;
out = buffer_[head];
head_.store((head + 1) & mask_, std::memory_order_release);
return true;
}
std::size_t capacity() const { return buffer_.size() - 1; }
bool empty() const {
return head_.load(std::memory_order_acquire) ==
tail_.load(std::memory_order_acquire);
}
private:
std::vector<T> buffer_;
std::size_t mask_;
// 分开到不同缓存行,避免伪共享
alignas(64) std::atomic<std::size_t> head_{0}; // 消费者写
alignas(64) std::atomic<std::size_t> tail_{0}; // 生产者写
};21 布隆过滤器
展开源码
cpp
// 21_bloom_filter.cpp —— 布隆过滤器
// k 个哈希函数、m 个 bit;无假阴性,有假阳性,不支持删除
// 对应《3. 数据结构.md》§三.6
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <string>
#include <utility>
#include <vector>
class BloomFilter {
public:
BloomFilter(std::size_t expectedItems, double falsePositiveRate) {
auto [m, k] = optimalParams(expectedItems, falsePositiveRate);
bitCount_ = m;
hashCount_ = k;
bits_.assign((bitCount_ + 63) / 64, 0);
}
void add(const std::string& key) {
for (std::size_t i = 0; i < hashCount_; ++i) {
std::size_t idx = index(key, i);
bits_[idx >> 6] |= (std::uint64_t{1} << (idx & 63));
}
}
bool contains(const std::string& key) const {
for (std::size_t i = 0; i < hashCount_; ++i) {
std::size_t idx = index(key, i);
if ((bits_[idx >> 6] & (std::uint64_t{1} << (idx & 63))) == 0)
return false; // 任一位为 0 就一定不存在
}
return true; // 全为 1,可能存在
}
std::size_t bitCount() const { return bitCount_; }
std::size_t hashCount() const { return hashCount_; }
// m = -n ln p / (ln 2)^2, k = (m / n) ln 2
static std::pair<std::size_t, std::size_t> optimalParams(std::size_t n, double p) {
const double ln2 = std::log(2.0);
std::size_t m = static_cast<std::size_t>(
-(static_cast<double>(n) * std::log(p)) / (ln2 * ln2));
std::size_t k = static_cast<std::size_t>(
std::round((static_cast<double>(m) / static_cast<double>(n)) * ln2));
if (m == 0) m = 1;
if (k == 0) k = 1;
return {m, k};
}
private:
static std::uint64_t mix(std::uint64_t x) {
x ^= x >> 33;
x *= 0xff51afd7ed558ccdULL;
x ^= x >> 33;
x *= 0xc4ceb9fe1a85ec53ULL;
x ^= x >> 33;
return x;
}
// 双重哈希派生 k 个位置:h + i * delta 再混合
std::size_t index(const std::string& key, std::size_t i) const {
std::uint64_t h = std::hash<std::string>{}(key);
h += (i + 1) * 0x9e3779b97f4a7c15ULL;
return static_cast<std::size_t>(mix(h) % bitCount_);
}
std::vector<std::uint64_t> bits_;
std::size_t bitCount_ = 0;
std::size_t hashCount_ = 0;
};22 位图
展开源码
cpp
// 22_bitmap.cpp —— 位图
// set / clear / test / flip / count 均为 O(1)(count 为 O(n/64))
// 40 亿个整数约需 512MB
// 对应《3. 数据结构.md》§三.5
#include <cstddef>
#include <cstdint>
#include <vector>
class Bitmap {
public:
explicit Bitmap(std::size_t n) : bits_((n + 63) / 64, 0), n_(n) {}
void set(std::size_t i) {
bits_[i >> 6] |= (std::uint64_t{1} << (i & 63));
}
void clear(std::size_t i) {
bits_[i >> 6] &= ~(std::uint64_t{1} << (i & 63));
}
bool test(std::size_t i) const {
return (bits_[i >> 6] >> (i & 63)) & 1ULL;
}
void flip(std::size_t i) {
bits_[i >> 6] ^= (std::uint64_t{1} << (i & 63));
}
std::size_t count() const {
std::size_t total = 0;
for (std::uint64_t word : bits_)
total += static_cast<std::size_t>(__builtin_popcountll(word));
return total;
}
// 从 from 开始第一个置位的位置;没有则返回 n_
std::size_t nextSet(std::size_t from) const {
for (std::size_t i = from; i < n_; ++i)
if (test(i)) return i;
return n_;
}
std::size_t size() const { return n_; }
private:
std::vector<std::uint64_t> bits_;
std::size_t n_;
};23 跳表
展开源码
cpp
// 23_skiplist.cpp —— 跳表
// 多层索引 + 随机层数,期望 O(log n);Redis zset 用它 + 哈希表
// 对应《3. 数据结构.md》§四.10
#include <cstdlib>
#include <vector>
class Skiplist {
public:
Skiplist() : head_(new Node(-1, kMaxLevel)), level_(1) {}
~Skiplist() {
// 只沿第 0 层释放,避免同一节点被重复 delete
Node* p = head_->next[0];
while (p) {
Node* next = p->next[0];
delete p;
p = next;
}
delete head_;
}
Skiplist(const Skiplist&) = delete;
Skiplist& operator=(const Skiplist&) = delete;
bool search(int target) const {
const Node* cur = head_;
for (int i = level_ - 1; i >= 0; --i) {
while (cur->next[i] && cur->next[i]->val < target)
cur = cur->next[i];
}
cur = cur->next[0];
return cur && cur->val == target;
}
void add(int num) {
std::vector<Node*> update(kMaxLevel, nullptr);
Node* cur = head_;
for (int i = level_ - 1; i >= 0; --i) {
while (cur->next[i] && cur->next[i]->val < num)
cur = cur->next[i];
update[i] = cur;
}
int newLevel = randomLevel();
if (newLevel > level_) {
for (int i = level_; i < newLevel; ++i) update[i] = head_;
level_ = newLevel;
}
Node* node = new Node(num, newLevel);
for (int i = 0; i < newLevel; ++i) {
node->next[i] = update[i]->next[i];
update[i]->next[i] = node;
}
}
bool erase(int num) {
std::vector<Node*> update(kMaxLevel, nullptr);
Node* cur = head_;
for (int i = level_ - 1; i >= 0; --i) {
while (cur->next[i] && cur->next[i]->val < num)
cur = cur->next[i];
update[i] = cur;
}
Node* victim = cur->next[0];
if (!victim || victim->val != num) return false;
for (int i = 0; i < level_; ++i) {
if (update[i]->next[i] == victim)
update[i]->next[i] = victim->next[i];
}
delete victim;
while (level_ > 1 && !head_->next[level_ - 1]) --level_;
return true;
}
private:
struct Node {
int val;
std::vector<Node*> next;
Node(int v, int level) : val(v), next(level, nullptr) {}
};
static constexpr int kMaxLevel = 16;
// p = 1/4:每 4 个节点期望升一层
static int randomLevel() {
int level = 1;
while (level < kMaxLevel && std::rand() % 4 == 0) ++level;
return level;
}
Node* head_;
int level_;
};24 KMP 算法
展开源码
cpp
// 24_kmp.cpp —— KMP 字符串匹配
// pi[i] = pat[0..i] 的最长相等真前缀 / 真后缀长度
// 预处理 O(m),匹配 O(n)
// 对应《3. 数据结构.md》§二.9
#include <cstddef>
#include <string>
#include <vector>
class KMP {
public:
static std::vector<int> buildPi(const std::string& pat) {
std::vector<int> pi(pat.size(), 0);
for (std::size_t i = 1, j = 0; i < pat.size(); ++i) {
while (j > 0 && pat[i] != pat[j]) j = pi[j - 1];
if (pat[i] == pat[j]) ++j;
pi[i] = static_cast<int>(j);
}
return pi;
}
// 返回所有匹配的起始下标
static std::vector<int> search(const std::string& text, const std::string& pat) {
std::vector<int> res;
if (pat.empty()) return res;
std::vector<int> pi = buildPi(pat);
for (std::size_t i = 0, j = 0; i < text.size(); ++i) {
while (j > 0 && text[i] != pat[j]) j = pi[j - 1];
if (text[i] == pat[j]) ++j;
if (j == pat.size()) {
res.push_back(static_cast<int>(i - j + 1));
j = pi[j - 1]; // 继续找下一处
}
}
return res;
}
// 最短循环节:n % (n - pi[n-1]) == 0 时返回该节,否则返回原串
static std::string shortestPeriod(const std::string& s) {
if (s.empty()) return s;
std::vector<int> pi = buildPi(s);
int n = static_cast<int>(s.size());
int p = n - pi[n - 1];
if (n % p == 0) return s.substr(0, p);
return s;
}
};25 随机集合
展开源码
cpp
// 25_randomized_set.cpp —— O(1) 随机插入 / 删除 / 取随机元素
// vector + 哈希表(值 -> 下标),删除用「与末尾交换再 pop」
// 对应《3. 数据结构.md》§七.5
#include <cstddef>
#include <cstdlib>
#include <unordered_map>
#include <vector>
class RandomizedSet {
public:
bool insert(int val) {
if (pos_.count(val)) return false;
pos_[val] = nums_.size();
nums_.push_back(val);
return true;
}
bool remove(int val) {
auto it = pos_.find(val);
if (it == pos_.end()) return false;
std::size_t idx = it->second;
int last = nums_.back();
nums_[idx] = last; // 末尾元素填到待删位置
pos_[last] = idx;
nums_.pop_back();
pos_.erase(it); // 注意在覆盖之后删,val == last 也正确
return true;
}
int getRandom() const {
return nums_[static_cast<std::size_t>(std::rand()) % nums_.size()];
}
bool contains(int val) const { return pos_.count(val) > 0; }
std::size_t size() const { return nums_.size(); }
private:
std::vector<int> nums_;
std::unordered_map<int, std::size_t> pos_;
};26 合并 K 个有序链表
展开源码
cpp
// 26_merge_k_lists.cpp —— 合并 K 个有序链表
// 小顶堆 O(N log k);分治两两合并 O(N log k),常数更小
// 对应《3. 数据结构.md》§七.6
#include <queue>
#include <vector>
struct ListNode {
int val;
ListNode* next;
explicit ListNode(int v) : val(v), next(nullptr) {}
};
class MergeKLists {
public:
// 小顶堆:比较器返回 true 表示 a 的优先级低于 b
static ListNode* mergeHeap(std::vector<ListNode*>& lists) {
auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(cmp)> pq(cmp);
for (ListNode* head : lists) {
if (head) pq.push(head);
}
ListNode dummy(0);
ListNode* tail = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
tail->next = node;
tail = node;
if (node->next) pq.push(node->next);
}
return dummy.next;
}
// 分治:两两合并
static ListNode* mergeDivide(std::vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
return divide(lists, 0, static_cast<int>(lists.size()) - 1);
}
private:
static ListNode* divide(std::vector<ListNode*>& lists, int l, int r) {
if (l == r) return lists[l];
int mid = l + (r - l) / 2;
return mergeTwo(divide(lists, l, mid), divide(lists, mid + 1, r));
}
static ListNode* mergeTwo(ListNode* a, ListNode* b) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (a && b) {
if (a->val <= b->val) {
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
tail->next = a ? a : b;
return dummy.next;
}
};27 线程安全队列
展开源码
cpp
// 27_thread_safe_queue.cpp —— 有界阻塞队列
// mutex + 两个条件变量;wait 必须带谓词(防虚假唤醒)
// close 后仍会把队列剩余任务消费完,再返回 false(优雅关闭)
// 对应《3. 数据结构.md》§七.7
#include <condition_variable>
#include <cstddef>
#include <mutex>
#include <queue>
#include <utility>
template <typename T>
class BoundedBlockingQueue {
public:
explicit BoundedBlockingQueue(std::size_t capacity) : capacity_(capacity) {}
bool push(T value) {
std::unique_lock<std::mutex> lock(mutex_);
notFull_.wait(lock, [this] { return closed_ || queue_.size() < capacity_; });
if (closed_) return false;
queue_.push(std::move(value));
notEmpty_.notify_one();
return true;
}
bool pop(T& out) {
std::unique_lock<std::mutex> lock(mutex_);
notEmpty_.wait(lock, [this] { return closed_ || !queue_.empty(); });
if (queue_.empty()) return false; // 已关闭且队列已排空
out = std::move(queue_.front());
queue_.pop();
notFull_.notify_one();
return true;
}
void close() {
{
std::lock_guard<std::mutex> lock(mutex_);
closed_ = true;
}
notEmpty_.notify_all();
notFull_.notify_all();
}
bool closed() const {
std::lock_guard<std::mutex> lock(mutex_);
return closed_;
}
std::size_t size() const {
std::lock_guard<std::mutex> lock(mutex_);
return queue_.size();
}
private:
std::size_t capacity_;
std::queue<T> queue_;
bool closed_ = false;
mutable std::mutex mutex_;
std::condition_variable notEmpty_;
std::condition_variable notFull_;
};