数据结构

前缀树

前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

字符前缀树

#include <iostream>
#include <unordered_map>
using namespace std;

// 字典树节点结构
struct TrieNode {
    bool isEnd;  // 标记是否是单词结尾
    unordered_map<char, TrieNode*> children;  // 子节点映射表，键是字符，值是对应节点
  
    // 构造函数，初始化节点
    TrieNode() {
        isEnd = false;  // 默认不是单词结尾
    }
};

// 字典树类
class Trie {
public:
    TrieNode* root;  // 根节点指针

    // 构造函数，初始化字典树
    Trie() {
        root = new TrieNode();  // 创建根节点
    }
  
    // 插入单词到字典树
    void insert(string word) {
        TrieNode* cur = root;  // 从根节点开始
  
        // 遍历单词中的每个字符
        for (char c : word) {
            // 如果当前字符不存在于子节点中，创建新节点
            if (cur->children.find(c) == cur->children.end()) {
                cur->children[c] = new TrieNode();
            }
            cur = cur->children[c];  // 移动到子节点
        }
  
        cur->isEnd = true;  // 标记单词结尾
    }
  
    // 搜索完整单词
    bool search(string word) {
        TrieNode* cur = root;  // 从根节点开始
  
        // 遍历单词中的每个字符
        for (char c : word) {
            // 如果当前字符不存在于子节点中，返回false
            if (cur->children.find(c) == cur->children.end()) {
                return false;
            }
            cur = cur->children[c];  // 移动到子节点
        }
  
        return cur->isEnd;  // 检查是否是单词结尾
    }
  
    // 检查是否存在以指定前缀开头的单词
    bool startsWith(string prefix) {
        TrieNode* cur = root;  // 从根节点开始
  
        // 遍历前缀中的每个字符
        for (char c : prefix) {
            // 如果当前字符不存在于子节点中，返回false
            if (cur->children.find(c) == cur->children.end()) {
                return false;
            }
            cur = cur->children[c];  // 移动到子节点
        }
  
        return true;  // 前缀存在
    }
};

int main() {
    Trie trie;  // 创建字典树实例
  
    cout << "===== 测试插入和搜索功能 =====" << endl;
    // 测试1: 插入单词并搜索
    trie.insert("apple");
    cout << "搜索 'apple': " << (trie.search("apple") ? "找到" : "未找到") << endl;   // 预期：找到
    cout << "搜索 'app': " << (trie.search("app") ? "找到" : "未找到") << endl;       // 预期：未找到
  
    // 测试2: 插入另一个单词并测试前缀
    trie.insert("app");
    cout << "搜索 'app': " << (trie.search("app") ? "找到" : "未找到") << endl;       // 预期：找到
    cout << "前缀 'app': " << (trie.startsWith("app") ? "存在" : "不存在") << endl;   // 预期：存在
  
    cout << "\n===== 测试前缀功能 =====" << endl;
    // 测试3: 测试前缀功能
    cout << "前缀 'ap': " << (trie.startsWith("ap") ? "存在" : "不存在") << endl;     // 预期：存在
    cout << "前缀 'ban': " << (trie.startsWith("ban") ? "存在" : "不存在") << endl;   // 预期：不存在
  
    return 0;
}

URL前缀树

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

// URL字典树节点类
class UrlTrieNode {
public:
    unordered_map<string, UrlTrieNode*> children;  // 子节点映射表，键是URL部分，值是对应节点
    bool isEndpoint;                               // 标记是否是URL终点

    // 构造函数，初始化节点
    UrlTrieNode(const string& val = "")
        : isEndpoint(false) {}  // 默认不是终点节点
};

// URL字典树类
class UrlTrie {
private:
    UrlTrieNode* root;  // 根节点指针

    // 将URL路径拆分为部分
    vector<string> splitPath(const string& path) {
        vector<string> parts;  // 存储拆分后的部分
        size_t start = 0;      // 当前部分的起始位置
        size_t end = path.find("/");  // 查找第一个斜杠

        // 处理开头的斜杠（如果有）
        if (end == 0) {
            start = 1;
            end = path.find("/", start);
        }

        // 循环查找所有部分
        while (end != string::npos) {
            string part = path.substr(start, end - start);  // 提取当前部分
            if (!part.empty()) {
                parts.push_back(part);  // 非空部分加入结果
            }
            start = end + 1;            // 更新起始位置
            end = path.find("/", start); // 查找下一个斜杠
        }

        // 处理最后的部分（如果有）
        if (start < path.length()) {
            string part = path.substr(start);
            if (!part.empty()) {
                parts.push_back(part);
            }
        }

        return parts;
    }

    // 根据部分路径搜索节点
    UrlTrieNode* searchParts(const vector<string>& parts) {
        UrlTrieNode* current = root;  // 从根节点开始

        // 遍历所有部分
        for (const string& part : parts) {
            // 如果当前部分不存在于子节点中，返回nullptr
            if (current->children.find(part) == current->children.end()) {
                return nullptr;
            }
            current = current->children[part];  // 移动到子节点
        }

        return current;  // 返回最终节点
    }

public:
    // 构造函数，初始化字典树
    UrlTrie() {
        root = new UrlTrieNode();  // 创建根节点
    }

    // 插入URL路径
    void insert(const string& path) {
        vector<string> parts = splitPath(path);  // 拆分路径
        UrlTrieNode* current = root;             // 从根节点开始

        // 遍历所有部分
        for (const string& part : parts) {
            // 如果当前部分不存在于子节点中，创建新节点
            if (current->children.find(part) == current->children.end()) {
                current->children[part] = new UrlTrieNode();
            }
            current = current->children[part];  // 移动到子节点
        }

        current->isEndpoint = true;  // 标记为终点节点
    }

    // 搜索完整URL路径
    bool search(const string& path) {
        vector<string> parts = splitPath(path);  // 拆分路径
        UrlTrieNode* node = searchParts(parts);  // 搜索节点
        return node != nullptr && node->isEndpoint;  // 检查是否是终点节点
    }

    // 检查是否存在以指定前缀开头的URL
    bool startsWith(const string& prefix) {
        vector<string> parts = splitPath(prefix);  // 拆分前缀
        return searchParts(parts) != nullptr;     // 只需检查节点是否存在
    }
};

int main() {
    UrlTrie urlTrie;  // 创建URL字典树实例

    cout << "===== 测试基本URL插入和搜索 =====" << endl;
    // 测试1: 插入简单URL路径并搜索
    urlTrie.insert("/user/profile");
    urlTrie.insert("/user/settings");
  
    // 预期结果：找到
    cout << "搜索 '/user/profile': " << (urlTrie.search("/user/profile") ? "找到" : "未找到") << endl;
    // 预期结果：找到
    cout << "搜索 '/user/settings': " << (urlTrie.search("/user/settings") ? "找到" : "未找到") << endl;
    // 预期结果：未找到（因为/user不是终点节点）
    cout << "搜索 '/user': " << (urlTrie.search("/user") ? "找到" : "未找到") << endl;
  
    cout << "\n===== 测试前缀功能 =====" << endl;
    // 测试2: 测试前缀功能
    // 预期结果：存在（因为有/user/profile和/user/settings）
    cout << "前缀 '/user': " << (urlTrie.startsWith("/user") ? "存在" : "不存在") << endl;
    // 预期结果：不存在
    cout << "前缀 '/admin': " << (urlTrie.startsWith("/admin") ? "存在" : "不存在") << endl;
  
    return 0;
}

LRU缓存

LRU（Least Recently Used）缓存是一种淘汰最近最少使用数据的缓存策略，当缓存空间不足时，优先移除最久未被访问的数据。

#include <iostream>
#include <unordered_map>
using namespace std;

// 双向链表节点结构
struct Node{
    int key;        // 键
    int value;      // 值
    Node *prev;     // 前驱节点指针
    Node *next;     // 后继节点指针

    Node()          // 构造函数初始化
    : prev(NULL), next(NULL), key(0), value(0) {}
};

class LRUCache {
public:
    // 构造函数，初始化容量和哨兵节点
    LRUCache(int capacity) {
        dummy = new Node;       // 创建哨兵节点
        dummy -> next = dummy;  // 初始化时指向自己
        dummy -> prev = dummy;
        this -> capacity = capacity;  // 设置缓存容量
    }
  
    // 获取键对应的值
    int get(int key) {
        Node *node = get_node(key);  // 获取节点
        if ( node == NULL ) return -1;  // 不存在返回-1
        return node -> value;       // 存在返回值
    }
  
    // 插入或更新键值对
    void put(int key, int value) {
        Node *node = get_node(key);  // 先尝试获取节点
        if ( node != NULL ) {        // 如果已存在
            node -> value = value;   // 更新值
            return;
        }

        // 不存在则创建新节点
        node = new Node;
        node -> key = key;
        node -> value = value;
        push_front(node);            // 插入到链表头部
        key_to_node[key] = node;     // 存入哈希表

        // 如果超过容量，移除最久未使用的节点
        if ( key_to_node.size() > capacity ) {
            Node *k = dummy -> prev;  // 链表尾部是最久未使用的
            remove(k);               // 从链表中移除
            key_to_node.erase(k -> key);  // 从哈希表中移除
            delete k;                // 释放内存
        }
    }

private:
    unordered_map<int, Node*> key_to_node;  // 哈希表存储键到节点的映射
    Node *dummy;        // 哨兵节点，简化链表操作
    int capacity;       // 缓存容量

    // 从链表中移除节点
    void remove(Node *node) {
        node -> prev -> next = node -> next;
        node -> next -> prev = node -> prev;
    }

    // 将节点插入到链表头部
    void push_front(Node *node) {
        node -> prev = dummy;
        node -> next = dummy -> next;
        node -> prev -> next = node;
        node -> next -> prev = node;
    }

    // 获取节点并移动到链表头部
    Node* get_node(int key) {
        if ( key_to_node.find(key) == key_to_node.end() ) {
            return NULL;  // 不存在返回NULL
        }
        Node *node = key_to_node[key];  // 获取节点
        remove(node);      // 从当前位置移除
        push_front(node);  // 移动到头部
        return node;
    }
};

int main() {
    // 测试用例1：基本插入和查询
    {
        cout << "测试用例1：基本插入和查询" << endl;
        LRUCache cache(2);
        cache.put(1, 1);            // 缓存: {1=1}
        cache.put(2, 2);            // 缓存: {1=1, 2=2}
        cout << cache.get(1) << endl;  // 输出1 (缓存: {2=2, 1=1})
        cout << cache.get(2) << endl;  // 输出2 (缓存: {1=1, 2=2})
        cout << cache.get(3) << endl;  // 输出-1 (不存在)
        cout << "----------------" << endl;
    }
  
    // 测试用例2：LRU淘汰机制
    {
        cout << "测试用例2：LRU淘汰机制" << endl;
        LRUCache cache(2);
        cache.put(1, 1);            // 缓存: {1=1}
        cache.put(2, 2);            // 缓存: {1=1, 2=2}
        cache.put(3, 3);            // 淘汰1，缓存: {2=2, 3=3}
        cout << cache.get(1) << endl;  // 输出-1 (已被淘汰)
        cout << cache.get(2) << endl;  // 输出2 (缓存: {3=3, 2=2})
        cout << cache.get(3) << endl;  // 输出3 (缓存: {2=2, 3=3})
        cout << "----------------" << endl;
    }
  
    // 测试用例3：更新已有键的值
    {
        cout << "测试用例3：更新已有键的值" << endl;
        LRUCache cache(2);
        cache.put(1, 1);            // 缓存: {1=1}
        cache.put(1, 10);           // 更新值，缓存: {1=10}
        cout << cache.get(1) << endl;  // 输出10
        cout << "----------------" << endl;
    }
  
    // 测试用例4：get操作影响LRU顺序
    {
        cout << "测试用例4：get操作影响LRU顺序" << endl;
        LRUCache cache(2);
        cache.put(1, 1);            // 缓存: {1=1}
        cache.put(2, 2);            // 缓存: {1=1, 2=2}
        cout << cache.get(1) << endl;  // 输出1，使1成为最近使用 (缓存: {2=2, 1=1})
        cache.put(3, 3);            // 淘汰2，缓存: {1=1, 3=3}
        cout << cache.get(1) << endl;  // 输出1
        cout << cache.get(2) << endl;  // 输出-1 (已被淘汰)
        cout << cache.get(3) << endl;  // 输出3
        cout << "----------------" << endl;
    }
  
    return 0;
}

哈希表

哈希表是一种通过哈希函数快速定位数据存储位置的高效数据结构。

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

using namespace std;

class MyHashSet {
public:
    // 构造函数，初始化哈希表大小为1000
    MyHashSet()
    : data(size) {
  
    }

    // 哈希函数，使用取模运算确定键的位置
    int hash(int key) {
        return key % size;
    }
  
    // 添加元素到集合中
    void add(int key) {
        if (contains(key)) return; // 如果已存在则不添加
        int index = hash(key);
        data[index].push_back(key);
    }
  
    // 从集合中移除元素
    void remove(int key) {
        if (!contains(key)) {
            return; // 如果不存在则直接返回
        }
        int index = hash(key);
        data[index].remove(key);
    }
  
    // 检查集合中是否包含指定元素
    bool contains(int key) {
        int index = hash(key);
        for (auto it = data[index].begin(); it != data[index].end(); it++) {
            if ((*it) == key) {
                return true;
            }
        }
        return false;
    }
private:
    int size = 1000; // 哈希表大小
    vector<list<int>> data; // 使用链表解决冲突
};

int main() {
    // 测试用例1：基本添加和包含测试
    MyHashSet set1;
    set1.add(1);
    set1.add(2);
    set1.add(3);
    cout << "测试1 - 基本功能:" << endl;
    cout << "集合包含1? " << (set1.contains(1) ? "是" : "否") << endl; // 预期: 是
    cout << "集合包含5? " << (set1.contains(5) ? "是" : "否") << endl; // 预期: 否
    cout << endl;

    // 测试用例2：重复添加测试
    MyHashSet set2;
    set2.add(10);
    set2.add(10); // 重复添加
    cout << "测试2 - 重复添加:" << endl;
    cout << "集合包含10? " << (set2.contains(10) ? "是" : "否") << endl; // 预期: 是
    cout << endl;

    // 测试用例3：删除测试
    MyHashSet set3;
    set3.add(100);
    set3.add(200);
    set3.remove(100);
    cout << "测试3 - 删除功能:" << endl;
    cout << "集合包含100? " << (set3.contains(100) ? "是" : "否") << endl; // 预期: 否
    cout << "集合包含200? " << (set3.contains(200) ? "是" : "否") << endl; // 预期: 是
    cout << endl;

    // 测试用例4：哈希冲突测试
    MyHashSet set4;
    set4.add(1);
    set4.add(1001); // 1001 % 1000 = 1，与1冲突
    cout << "测试4 - 哈希冲突:" << endl;
    cout << "集合包含1? " << (set4.contains(1) ? "是" : "否") << endl; // 预期: 是
    cout << "集合包含1001? " << (set4.contains(1001) ? "是" : "否") << endl; // 预期: 是
    cout << endl;

    return 0;
}

堆

堆是一种特殊的完全二叉树，满足每个节点的值都大于等于（或小于等于）其子节点的值，常用于优先队列和动态排序。

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

using namespace std;

class MaxHeap {
private:
    vector<int> heap; // 使用数组存储堆元素

    // 上浮操作：将新插入的元素调整到合适位置
    void Up(int i) {
        while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
            swap(heap[(i - 1) / 2], heap[i]); // 如果父节点小于当前节点，交换
            i = (i - 1) / 2; // 继续向上检查
        }
    }

    // 下沉操作：将不符合堆性质的元素下沉到合适位置
    void Down(int i) {
        int maxIndex = i; // 假设当前节点是最大的
        int left = 2 * i + 1; // 左子节点索引
        int right = 2 * i + 2; // 右子节点索引

        // 找出当前节点、左子节点、右子节点中的最大值
        if (left < heap.size() && heap[left] > heap[maxIndex])
            maxIndex = left;
        if (right < heap.size() && heap[right] > heap[maxIndex])
            maxIndex = right;

        // 如果最大值不是当前节点，交换并继续下沉
        if (i != maxIndex) {
            swap(heap[i], heap[maxIndex]);
            Down(maxIndex);
        }
    }

public:
    // 插入元素
    void push(int value) {
        heap.push_back(value); // 添加到数组末尾
        Up(heap.size() - 1); // 执行上浮操作
    }

    // 弹出最大值（堆顶元素）
    void pop() {
        if (heap.empty()) return; // 空堆直接返回
        heap[0] = heap.back(); // 将最后一个元素移到堆顶
        heap.pop_back(); // 删除最后一个元素
        if (!heap.empty()) Down(0); // 执行下沉操作
    }

    // 获取最大值（堆顶元素）
    int top() const {
        if (heap.empty()) return -1; // 简单处理空堆情况
        return heap[0];
    }

    // 获取堆大小
    int size() const {
        return heap.size();
    }

    // 检查堆是否为空
    bool empty() const {
        return heap.empty();
    }
};

int main() {
    // 测试用例1：基本功能测试
    MaxHeap heap1;
    heap1.push(3);
    heap1.push(1);
    heap1.push(4);
    heap1.push(1);
    heap1.push(5);
    heap1.push(9);
  
    cout << "测试1 - 基本功能:" << endl;
    cout << "堆顶元素: " << heap1.top() << endl; // 预期: 9
    heap1.pop();
    cout << "弹出后堆顶元素: " << heap1.top() << endl; // 预期: 5
    cout << "堆大小: " << heap1.size() << endl; // 预期: 5
    cout << endl;

    // 测试用例2：空堆测试
    MaxHeap heap2;
    cout << "测试2 - 空堆测试:" << endl;
    cout << "空堆堆顶: " << heap2.top() << endl; // 预期: -1
    heap2.pop(); // 应该不会崩溃
    cout << "对空堆执行pop操作后堆大小: " << heap2.size() << endl; // 预期: 0
    cout << endl;

    // 测试用例3：大量元素测试
    MaxHeap heap3;
    for (int i = 0; i < 100; ++i) {
        heap3.push(i);
    }
    cout << "测试3 - 大量元素测试:" << endl;
    cout << "堆顶元素: " << heap3.top() << endl; // 预期: 99
    for (int i = 0; i < 50; ++i) {
        heap3.pop();
    }
    cout << "弹出50次后堆顶元素: " << heap3.top() << endl; // 预期: 49
    cout << "剩余堆大小: " << heap3.size() << endl; // 预期: 50
    cout << endl;

    // 测试用例4：重复元素测试
    MaxHeap heap4;
    for (int i = 0; i < 10; ++i) {
        heap4.push(5);
    }
    cout << "测试4 - 重复元素测试:" << endl;
    cout << "堆顶元素: " << heap4.top() << endl; // 预期: 5
    for (int i = 0; i < 5; ++i) {
        heap4.pop();
    }
    cout << "弹出5次后堆顶元素: " << heap4.top() << endl; // 预期: 5
    cout << "剩余堆大小: " << heap4.size() << endl; // 预期: 5
    cout << endl;

    return 0;
}

布隆过滤器

布隆过滤器（Bloom Filter）是一种空间高效的概率型数据结构，用于快速判断一个元素是否可能存在于集合中（可能存在误判，但不会漏判）。

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

class IntBloomFilter {
private:
    vector<bool> bits;  // 位数组
    int size;          // 位数组大小
    int numHashes;     // 哈希函数数量

    // 简单的哈希函数1
    int hash1(int key) const {
        return key % size;
    }

    // 简单的哈希函数2
    int hash2(int key) const {
        return (key * 31) % size;
    }

    // 简单的哈希函数3
    int hash3(int key) const {
        return (key * 17 + 7) % size;
    }

public:
    // 构造函数，初始化位数组大小和哈希函数数量
    IntBloomFilter(int size, int numHashes = 3) 
        : size(size), numHashes(numHashes), bits(size, false) {
        if (numHashes < 1 || numHashes > 3) {
            cout << "警告: 哈希函数数量限制为1-3个，将使用默认值3" << endl;
            this->numHashes = 3;
        }
    }

    // 添加元素
    void add(int key) {
        bits[hash1(key)] = true;
        if (numHashes >= 2) bits[hash2(key)] = true;
        if (numHashes >= 3) bits[hash3(key)] = true;
    }

    // 检查元素是否存在（可能有误判）
    bool contains(int key) const {
        if (!bits[hash1(key)]) return false;
        if (numHashes >= 2 && !bits[hash2(key)]) return false;
        if (numHashes >= 3 && !bits[hash3(key)]) return false;
        return true;
    }

    // 打印位数组状态（用于调试）
    void printBits() const {
        cout << "位数组状态: ";
        for (bool bit : bits) {
            cout << (bit ? '1' : '0');
        }
        cout << endl;
    }
};

int main() {
    // 测试用例1：基本功能测试
    cout << "=== 测试1: 基本功能 ===" << endl;
    IntBloomFilter bf1(100); // 100位，3个哈希函数
  
    bf1.add(42);
    bf1.add(123);
    bf1.add(999);
  
    cout << "包含42? " << (bf1.contains(42) ? "是" : "否") << endl;    // 预期: 是
    cout << "包含123? " << (bf1.contains(123) ? "是" : "否") << endl;  // 预期: 是
    cout << "包含999? " << (bf1.contains(999) ? "是" : "否") << endl;  // 预期: 是
    cout << "包含456? " << (bf1.contains(456) ? "是" : "否") << endl;  // 预期: 否
    cout << endl;

    // 测试用例2：误判测试
    cout << "=== 测试2: 误判测试 ===" << endl;
    IntBloomFilter bf2(20); // 小位数组增加碰撞概率
  
    bf2.add(1);
    bf2.add(2);
    bf2.add(3);
  
    cout << "包含1? " << (bf2.contains(1) ? "是" : "否") << endl;      // 预期: 是
    cout << "包含10? " << (bf2.contains(10) ? "是" : "否") << endl;    // 可能误判
    cout << "包含15? " << (bf2.contains(15) ? "是" : "否") << endl;    // 可能误判
    cout << endl;

    // 测试用例3：不同哈希函数数量测试
    cout << "=== 测试3: 哈希函数数量影响 ===" << endl;
    IntBloomFilter bf3_1(100, 1); // 1个哈希函数
    IntBloomFilter bf3_3(100, 3); // 3个哈希函数
  
    bf3_1.add(42);
    bf3_3.add(42);
  
    cout << "1个哈希函数 - 包含42? " << (bf3_1.contains(42) ? "是" : "否") << endl;  // 预期: 是
    cout << "1个哈希函数 - 包含43? " << (bf3_1.contains(43) ? "是" : "否") << endl;  // 可能误判
    cout << "3个哈希函数 - 包含42? " << (bf3_3.contains(42) ? "是" : "否") << endl;  // 预期: 是
    cout << "3个哈希函数 - 包含43? " << (bf3_3.contains(43) ? "是" : "否") << endl;  // 误判概率更低
    cout << endl;

    // 测试用例4：边界值测试
    cout << "=== 测试4: 边界值 ===" << endl;
    IntBloomFilter bf4(10);
  
    bf4.add(0);
    bf4.add(9);
    bf4.add(1000);
  
    cout << "包含0? " << (bf4.contains(0) ? "是" : "否") << endl;          // 预期: 是
    cout << "包含9? " << (bf4.contains(9) ? "是" : "否") << endl;          // 预期: 是
    cout << "包含1000? " << (bf4.contains(1000) ? "是" : "否") << endl;    // 预期: 是
    cout << "包含5? " << (bf4.contains(5) ? "是" : "否") << endl;          // 可能误判
    cout << endl;

    return 0;
}

算法

排序

冒泡排序

1. 冒泡排序是一种简单的交换排序算法，通过反复比较相邻元素并交换顺序，使较大的元素逐渐“浮”到数组末尾（或较小的元素“沉”到开头），像气泡一样上升，因此得名。
2. 时间复杂度：O(n²)
3. 空间复杂度：O(1)
4. 稳定性：稳定

#include <iostream>
#include <vector>

using namespace std;

// 冒泡排序函数
void bubbleSort(vector<int> &arr) {
    int n = arr.size();
    // 外层循环控制排序轮数，从末尾向前遍历
    // 每轮结束后，当前最大的元素会沉到数组底部
    for (int i = n - 1; i > 0; i--) {
        // 内层循环控制每轮的比较和交换
        // 比较相邻元素，将较大的元素向后移动
        for (int j = 0; j < i; j++) {
            // 如果前一个元素比后一个元素大，则交换它们
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    // 单个测试用例
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    bubbleSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

选择排序

1. 选择排序是一种简单直观的排序算法，核心思想是每次从未排序部分选出最小（或最大）元素，放到已排序部分的末尾，逐步构建有序序列。
2. 时间复杂度：O(n²)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

#include <iostream>
#include <vector>

using namespace std;

// 选择排序函数
void selectionSort(vector<int>& arr) {
    int n = arr.size();
    // 外层循环控制当前要填充的位置
    for (int i = 0; i < n - 1; i++) {
        // 假设当前位置是最小值的位置
        int minIndex = i;
  
        // 内层循环寻找未排序部分的最小值
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
  
        // 将找到的最小值与当前位置交换
        swap(arr[i], arr[minIndex]);
    }
}

int main() {
    // 测试用例
    vector<int> arr = {64, 25, 12, 22, 11};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    selectionSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

插入排序

1. 插入排序是一种简单直观的排序算法，其核心思想是将未排序部分的元素逐个插入到已排序部分的正确位置，类似于整理扑克牌时的排序方式。
2. 时间复杂度：O(n²)
3. 空间复杂度：O(1)
4. 稳定性：稳定

#include <iostream>
#include <vector>

using namespace std;

// 插入排序函数
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    // 从第二个元素开始（下标1），因为单个元素默认是有序的
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 当前要插入的元素
        int j = i - 1;     // 已排序部分的最后一个元素索引
  
        // 将比key大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
  
        // 插入key到正确位置
        arr[j + 1] = key;
    }
}

int main() {
    // 测试用例
    vector<int> arr = {12, 11, 13, 5, 6};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    insertionSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

归并排序

1. 此得名。归并排序是一种基于分治法（Divide and Conquer）的高效排序算法，核心思想是将数组递归拆分为最小单元（单个元素），再逐步合并为有序序列。
2. 时间复杂度：O(n log n)
3. 空间复杂度：O(n)
4. 稳定性：稳定

#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序数组
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;  // 左子数组大小
    int n2 = right - mid;     // 右子数组大小
  
    // 创建临时数组
    vector<int> L(n1), R(n2);
  
    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
  
    // 合并临时数组到原数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
  
    // 拷贝剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序主函数
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // 防止溢出
  
        // 递归排序左右子数组
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
  
        // 合并已排序的子数组
        merge(arr, left, mid, right);
    }
}

// 包装函数，简化调用
void mergeSort(vector<int>& arr) {
    mergeSort(arr, 0, arr.size() - 1);
}

int main() {
    // 测试用例
    vector<int> arr = {12, 11, 13, 5, 6, 7};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    mergeSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

快速排序

1. 快速排序是一种基于分治法的高效排序算法，核心思想是通过“分区（Partition）”操作将数组分为两部分，并递归排序子数组，最终完成整体排序。
2. 时间复杂度：O(n log n)
3. 空间复杂度：O(log n) ~ O(n)
4. 稳定性：不稳定

#include <iostream>
#include <vector>

using namespace std;

// 分区函数，选择基准值并将数组分为两部分
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准值
    int i = low - 1;        // i是小于基准值的元素的边界
  
    for (int j = low; j < high; j++) {
        // 如果当前元素小于或等于基准值
        if (arr[j] <= pivot) {
            i++;  // 扩大小于基准值的区域
            swap(arr[i], arr[j]);
        }
    }
    // 将基准值放到正确位置
    swap(arr[i + 1], arr[high]);
    return i + 1;  // 返回基准值的最终位置
}

// 快速排序主函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // pi是分区索引，arr[pi]现在在正确位置
        int pi = partition(arr, low, high);
  
        // 递归排序分区前后的子数组
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 包装函数，简化调用
void quickSort(vector<int>& arr) {
    quickSort(arr, 0, arr.size() - 1);
}

int main() {
    // 测试用例
    vector<int> arr = {10, 7, 8, 9, 1, 5};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    quickSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

堆排序

1. 堆排序是一种基于二叉堆（Binary Heap）数据结构的高效排序算法，核心思想是将待排序数组构建成堆结构，并利用堆的性质逐步提取最大（或最小）元素，从而完成排序。
2. 时间复杂度：O(n log n)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

#include <iostream>
#include <vector>

using namespace std;

// 调整堆，使其满足堆性质
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;        // 初始化最大元素为当前节点
    int left = 2 * i + 1;   // 左子节点索引
    int right = 2 * i + 2;  // 右子节点索引

    // 如果左子节点比当前节点大
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点比当前最大节点大
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大元素不是当前节点，交换并继续调整
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// 堆排序主函数
void heapSort(vector<int>& arr) {
    int n = arr.size();

    // 构建最大堆（从最后一个非叶子节点开始）
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 逐个提取堆顶元素（最大值）
    for (int i = n - 1; i > 0; i--) {
        // 将当前最大值移到数组末尾
        swap(arr[0], arr[i]);
        // 调整剩余元素使其满足堆性质
        heapify(arr, i, 0);
    }
}

int main() {
    // 测试用例
    vector<int> arr = {12, 11, 13, 5, 6, 7};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    heapSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

计数排序

1. 计数排序是一种基于元素值范围统计出现次数来排序的非比较排序算法，适用于非负整数且最大值不大的情况。
2. 时间复杂度：O(n + k)，其中 n 是元素个数，k 是最大值
3. 空间复杂度：O(k)
4. 稳定性：稳定（若实现中保持相同元素的相对顺序）

#include <iostream>
#include <vector>
#include <algorithm>  // 为了使用 std::max
using namespace std;

// 计数排序函数，假设输入数组中所有元素都是非负整数
void countingSort(vector<int>& arr) {
    if (arr.empty()) return;  // 空数组不需要排序

    // 找出数组中的最大值，用于确定计数数组的大小
    int maxVal = *max_element(arr.begin(), arr.end());

    // 创建并初始化计数数组，大小为 maxVal + 1
    vector<int> count(maxVal + 1, 0);

    // 统计每个元素出现的次数
    for (int num : arr) {
        count[num]++;
    }

    // 根据计数数组重建原数组
    int index = 0;
    for (int i = 0; i <= maxVal; ++i) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

// 主函数用于测试计数排序
int main() {
    // 定义一个待排序的数组
    vector<int> data = {4, 2, 2, 8, 3, 3, 1};

    cout << "排序前: ";
    for (int num : data) {
        cout << num << " ";
    }
    cout << endl;

    // 调用计数排序
    countingSort(data);

    cout << "排序后: ";
    for (int num : data) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

KMP

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它通过预处理模式串，避免在匹配失败时重复比较已经匹配过的字符。其核心在于构建一个“部分匹配表”（next数组），用来指导主串中指针的回退，从而将时间复杂度优化到 O(n)。

#include <string>
#include <vector>
#include <iostream>
using namespace std;

// 构建 KMP 的部分匹配表（即 next 数组）
vector<int> getNext(const string &s) {
    vector<int> next(s.size(), 0); // next[i] 表示 s[0..i] 子串中，最长的相同前后缀长度
    int j = 0;                     // j 表示前缀末尾的下标
    next[0] = 0;                   // 第一个字符的 next 值为 0

    for (int i = 1; i < s.size(); i++) { // 从第二个字符开始计算
        // 如果当前字符与前缀末尾不匹配，回退 j，直到匹配或 j == 0
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }

        // 如果当前字符匹配成功，前缀长度加一
        if (s[i] == s[j]) j++;

        // 更新 next[i] 为当前的匹配长度
        next[i] = j;
    }

    return next;
}

// 在 haystack 中查找 needle 的起始位置，若不存在返回 -1
int strStr(string haystack, string needle) {
    if (needle.size() == 0) return 0; // 空字符串默认匹配成功，返回 0

    vector<int> next = getNext(needle); // 构造 needle 的部分匹配表
    int j = 0; // needle 的指针

    for (int i = 0; i < haystack.size(); i++) { // 遍历 haystack
        // 若当前字符不匹配，根据 next 数组回退 j
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }

        // 若当前字符匹配成功，j 向后移动一位
        if (haystack[i] == needle[j]) j++;

        // 如果 j 到达 needle 末尾，说明匹配成功
        if (j == needle.size()) {
            return i - needle.size() + 1; // 返回匹配的起始位置
        }
    }

    return -1; // 匹配失败
}

int main() {
    cout << strStr("hello", "ll") << endl;         // 应该输出 2
    cout << strStr("aaaaa", "bba") << endl;        // 应该输出 -1
    cout << strStr("abc", "") << endl;             // 应该输出 0（空 needle）
    cout << strStr("a", "a") << endl;              // 应该输出 0
    cout << strStr("mississippi", "issip") << endl; // 应该输出 4
    return 0;
}

多线程

用三个线程，顺序打印字母A-Z，输出结果是1A 2B 3C 1D 2E…

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

using namespace std;

class Test {
private:
    static char c;          // 当前输出的字符，从 'A' 开始
    static int i;           // 当前输出的字符索引
    static mutex mtx;       // 用于线程同步的互斥锁
    static condition_variable cv;  // 条件变量，用于线程等待和通知

public:
    static void run(int id) {
        unique_lock<mutex> lock(mtx);
        while (i < 26) {
            if (i % 3 == id - 1) { // 轮到该线程打印
                cout << "线程id：" << id << " " << c++ << endl;
                i++;
                cv.notify_all(); // 唤醒所有线程
            } else {
                cv.wait(lock);   // 条件不满足时等待
            }
        }
    }
};

// 静态变量初始化
char Test::c = 'A';
int Test::i = 0;
mutex Test::mtx;
condition_variable Test::cv;

int main() {
    // 创建三个线程，对应 id 为 1, 2, 3
    thread t1(Test::run, 1);
    thread t2(Test::run, 2);
    thread t3(Test::run, 3);

    // 等待三个线程完成
    t1.join();
    t2.join();
    t3.join();

    return 0;
}

每个线程把自己的ID打印10遍，要求结果必须按ABC的顺序显示

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

using namespace std;

class Test {
private:
    static char current_char;          // 当前应该输出的字符（A/B/C）
    static int count;                  // 当前已经打印的轮数
    static mutex mtx;                  // 用于线程同步的互斥锁
    static condition_variable cv;      // 条件变量，用于线程等待和通知

public:
    static void run(char my_char) {
        unique_lock<mutex> lock(mtx);
    
        for (int i = 0; i < 10; ) {    // 每个线程打印10次
            // 等待轮到自己的字符
            while (current_char != my_char) {
                cv.wait(lock);
            }
            // 打印字符
            cout << my_char;
            // 更新下一个应该打印的字符
            current_char = (current_char == 'C') ? 'A' : current_char + 1;
            i++;  // 增加本线程的打印计数
            cv.notify_all(); // 唤醒所有线程
        }
    }
};

// 静态变量初始化
char Test::current_char = 'A';
int Test::count = 0;
mutex Test::mtx;
condition_variable Test::cv;

int main() {
    // 创建三个线程，分别打印A、B、C
    thread t1(Test::run, 'A');
    thread t2(Test::run, 'B');
    thread t3(Test::run, 'C');

    // 等待三个线程完成
    t1.join();
    t2.join();
    t3.join();

    cout << endl;  // 输出换行
    return 0;
}

两线程奇偶数打印

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

using namespace std;

int value = 0; // 全局共享变量
mutex mtx;
condition_variable conA, conB;
bool turnA = true; // 控制当前由哪个线程打印，A先开始

void threadA() {
    unique_lock<mutex> lock(mtx);
    while (value <= 100) {
        // 如果不是线程A的回合，就等待
        while (!turnA && value <= 100)
            conA.wait(lock);

        if (value > 100) break;

        cout << "A " << value++ << endl;

        turnA = false;       // 交给线程B
        conB.notify_one();   // 唤醒线程B

        if (value <= 100)
            conA.wait(lock); // 打印后等待下一次唤醒
    }
    conB.notify_one(); // 防止B阻塞在 wait
}

void threadB() {
    unique_lock<mutex> lock(mtx);
    while (value <= 100) {
        // 如果不是线程B的回合，就等待
        while (turnA && value <= 100)
            conB.wait(lock);

        if (value > 100) break;

        cout << "B " << value++ << endl;

        turnA = true;       // 交给线程A
        conA.notify_one();  // 唤醒线程A

        if (value <= 100)
            conB.wait(lock); // 打印后等待下一次唤醒
    }
    conA.notify_one(); // 防止A阻塞在 wait
}

int main() {
    thread t1(threadA);
    thread t2(threadB);

    t1.join();
    t2.join();

    return 0;
}

启动3个线程打印递增的数字, 线程1先打印1,2,3,4,5, 然后是线程2打印6,7,8,9,10。直到75

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

using namespace std;

int value = 1;
mutex mtx;
condition_variable conA, conB;
bool turnA = true; // A 先开始

void threadA() {
    unique_lock<mutex> lock(mtx);
    while (value <= 75) {
        while (!turnA && value <= 75)
            conA.wait(lock);

        if (value > 75) break;

        cout << "A ";
        for (int i = 0; i < 5 && value <= 75; ++i) {
            cout << value++ << " ";
        }
        cout << endl;

        turnA = false;
        conB.notify_one();

        if (value <= 75)
            conA.wait(lock);
    }
    conB.notify_one(); // 避免B被挂住
}

void threadB() {
    unique_lock<mutex> lock(mtx);
    while (value <= 75) {
        while (turnA && value <= 75)
            conB.wait(lock);

        if (value > 75) break;

        cout << "B ";
        for (int i = 0; i < 5 && value <= 75; ++i) {
            cout << value++ << " ";
        }
        cout << endl;

        turnA = true;
        conA.notify_one();

        if (value <= 75)
            conB.wait(lock);
    }
    conA.notify_one(); // 避免A被挂住
}

int main() {
    thread tA(threadA);
    thread tB(threadB);

    tA.join();
    tB.join();

    return 0;
}

每个线程等待前一个线程执行完后再开始执行

#include <iostream>
#include <thread>
using namespace std;

// 线程工作函数，参数是指向上一个线程的指针（可为空）
void work(thread* beforeThread) {
    if (beforeThread != nullptr) {
        beforeThread->join();  // 等待前一个线程执行完成
    }
    cout << "thread start: " << this_thread::get_id() << endl;
}

int main() {
    thread* t1 = new thread(work, nullptr);
    thread* t2 = new thread(work, t1);
    thread* t3 = new thread(work, t2);

    // 等待最后一个线程执行完成
    t3->join();

    // 清理资源
    delete t1;
    delete t2;
    delete t3;

    return 0;
}

使用原子变量实现互斥锁（自旋锁）

#include <iostream>
#include <atomic>
#include <thread>
#include <vector>

using namespace std;

// 自定义的自旋锁
class SpinLock {
    atomic_flag flag = ATOMIC_FLAG_INIT; // 初始状态为 false（未被锁）

public:
    void lock() {
        while (flag.test_and_set(std::memory_order_acquire)) {
            // busy-wait 直到 flag 被清除
        }
    }

    void unlock() {
        flag.clear(std::memory_order_release);
    }
};

SpinLock spinLock;
int counter = 0; // 共享变量

void incrementTask(int id) {
    for (int i = 0; i < 10000; ++i) {
        spinLock.lock();      // 加锁
        ++counter;            // 临界区
        spinLock.unlock();    // 解锁
    }
}

int main() {
    vector<thread> threads;

    for (int i = 0; i < 4; ++i) {
        threads.emplace_back(incrementTask, i);
    }

    for (auto& t : threads) {
        t.join();
    }

    cout << "Final counter: " << counter << endl; // 应为 40000
    return 0;
}

使用原子变量实现信号量

#include <iostream>
#include <atomic>
#include <thread>
#include <vector>
#include <chrono>

using namespace std;

class SpinSemaphore {
private:
    atomic<int> count;

public:
    SpinSemaphore(int initial = 0) : count(initial) {}

    void wait() {
        while (true) {
            int expected = count.load();
            while (expected <= 0) {
                // busy wait
                expected = count.load();
                this_thread::yield(); // 让出时间片，降低 CPU 占用
            }
            if (count.compare_exchange_weak(expected, expected - 1)) {
                break;
            }
        }
    }

    void signal() {
        count.fetch_add(1);
    }
};

SpinSemaphore sem(0);

void worker(int id) {
    cout << "Thread " << id << " waiting..." << endl;
    sem.wait();
    cout << "Thread " << id << " resumed!" << endl;
}

int main() {
    vector<thread> threads;

    for (int i = 0; i < 3; ++i)
        threads.emplace_back(worker, i);

    this_thread::sleep_for(chrono::seconds(2));

    for (int i = 0; i < 3; ++i) {
        sem.signal();
        this_thread::sleep_for(chrono::milliseconds(500));
    }

    for (auto& t : threads) t.join();
    return 0;
}