C++ 算法模板库¶

#include <bits/stdc++.h>
using namespace std;

/**
 * 打印一维数组
 * 时间: O(n)
 * 空间: O(1)
 */
template<typename T>
void printArray(const vector<T>& arr, const string& name = "") {
    if (!name.empty()) cout << name << ": ";
    cout << "[";
    for (int i = 0; i < arr.size(); i++) {
        if (i > 0) cout << ", ";
        cout << arr[i];
    }
    cout << "]" << endl;
}

vector<int> arr = {1, 2, 3, 4, 5};
printArray(arr, "数组");  // 输出: 数组: [1, 2, 3, 4, 5]

/**
 * 打印二维数组
 * 时间: O(m×n)
 * 空间: O(1)
 */
template<typename T>
void print2DArray(const vector<vector<T>>& arr, const string& name = "") {
    if (!name.empty()) cout << name << ":" << endl;
    for (const auto& row : arr) {
        cout << "  [";
        for (int i = 0; i < row.size(); i++) {
            if (i > 0) cout << ", ";
            cout << row[i];
        }
        cout << "]" << endl;
    }
}

/**
 * 快速排序 - 原地版（Lomuto分区）
 * 时间: O(n log n) 平均，O(n²) 最坏
 * 空间: O(log n)
 */
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // 选择最后一个元素作为pivot
        int pivot = arr[high];
        int i = low - 1;

        // 分区操作
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i + 1], arr[high]);
        int pi = i + 1;

        // 递归排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

vector<int> arr = {3, 6, 8, 10, 1, 2, 1};
quickSort(arr, 0, arr.size() - 1);
// 结果: [1, 1, 2, 3, 6, 8, 10]

/**
 * 快速排序 - 简洁版（返回新数组）
 * 适合理解算法思想
 */
vector<int> quickSortSimple(vector<int> arr) {
    if (arr.size() <= 1) return arr;

    int pivot = arr[arr.size() / 2];
    vector<int> left, middle, right;

    for (int x : arr) {
        if (x < pivot) left.push_back(x);
        else if (x == pivot) middle.push_back(x);
        else right.push_back(x);
    }

    left = quickSortSimple(left);
    right = quickSortSimple(right);

    left.insert(left.end(), middle.begin(), middle.end());
    left.insert(left.end(), right.begin(), right.end());
    return left;
}

/**
 * 归并排序
 * 时间: O(n log n)
 * 空间: O(n)
 * 特点: 稳定排序
 */
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);

        // 合并两个有序数组
        vector<int> temp(right - left + 1);
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }

        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        // 复制回原数组
        for (int p = 0; p < k; p++) {
            arr[left + p] = temp[p];
        }
    }
}

/**
 * 堆排序
 * 时间: O(n log n)
 * 空间: O(1)
 */
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);
    }
}

/**
 * 二分搜索 - 标准版
 * 时间: O(log n)
 * 空间: O(1)
 * 返回: target的索引，不存在返回-1
 * 前提: 数组必须是有序的
 */
int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防止溢出

        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1;
}

vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
int idx = binarySearch(arr, 7);  // 返回: 3

/**
 * lower_bound - 第一个 >= target 的位置
 * 时间: O(log n)
 * 空间: O(1)
 * 返回: 插入位置（可能等于数组长度）
 */
int lowerBound(const vector<int>& arr, int target) {
    int left = 0, right = arr.size();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }

    return left;
}

/**
 * upper_bound - 第一个 > target 的位置
 * 时间: O(log n)
 * 空间: O(1)
 */
int upperBound(const vector<int>& arr, int target) {
    int left = 0, right = arr.size();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) left = mid + 1;
        else right = mid;
    }

    return left;
}

// C++ STL中的二分搜索函数
#include <algorithm>

lower_bound(arr.begin(), arr.end(), target);  // 第一个 >= target
upper_bound(arr.begin(), arr.end(), target);  // 第一个 > target
binary_search(arr.begin(), arr.end(), target); // 是否存在

/**
 * BFS - 广度优先搜索
 * 时间: O(V + E)
 * 空间: O(V)
 * 适用: 无权图最短路径、层序遍历
 */
vector<int> bfs(const unordered_map<int, vector<int>>& graph, int start) {
    vector<int> result;
    unordered_set<int> visited;
    queue<int> q;

    visited.insert(start);
    q.push(start);

    while (!q.empty()) {
        int node = q.front(); q.pop();
        result.push_back(node);

        auto it = graph.find(node);
        if (it != graph.end()) {
            for (int neighbor : it->second) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
    }

    return result;
}

unordered_map<int, vector<int>> graph = {
    {0, {1, 2}},
    {1, {2}},
    {2, {0, 3}},
    {3, {3}}
};
vector<int> result = bfs(graph, 2);  // [2, 0, 3, 1]

/**
 * DFS - 深度优先搜索（递归版）
 * 时间: O(V + E)
 * 空间: O(V)
 */
void dfsRecursive(const unordered_map<int, vector<int>>& graph,
                  int node, unordered_set<int>& visited, vector<int>& result) {
    visited.insert(node);
    result.push_back(node);

    auto it = graph.find(node);
    if (it != graph.end()) {
        for (int neighbor : it->second) {
            if (visited.find(neighbor) == visited.end()) {
                dfsRecursive(graph, neighbor, visited, result);
            }
        }
    }
}

// 使用包装函数
vector<int> dfs(const unordered_map<int, vector<int>>& graph, int start) {
    vector<int> result;
    unordered_set<int> visited;
    dfsRecursive(graph, start, visited, result);
    return result;
}

/**
 * Dijkstra最短路径算法
 * 时间: O((V + E) log V)
 * 空间: O(V)
 * 适用: 非负权图的单源最短路径
 */
vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;

    // 小顶堆: {距离, 节点}
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();

        if (d > dist[u]) continue;  // 已处理过

        for (auto [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

// 邻接表: graph[u] = {{v, weight}, ...}
vector<vector<pair<int, int>>> graph = {
    {{1, 4}, {2, 1}},    // 节点0
    {{3, 1}},            // 节点1
    {{1, 2}, {3, 5}},    // 节点2
    {}                   // 节点3
};
vector<int> dist = dijkstra(graph, 0);
// dist = [0, 3, 1, 4]

/**
 * 爬楼梯 - 动态规划
 * 时间: O(n)
 * 空间: O(1)
 * 问题: 每次爬1或2阶，n阶有多少种方法
 * 状态转移: dp[i] = dp[i-1] + dp[i-2]
 */
int climbStairs(int n) {
    if (n <= 2) return n;

    int prev = 1, curr = 2;
    for (int i = 3; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }

    return curr;
}

/**
 * 0-1背包问题
 * 时间: O(n × capacity)
 * 空间: O(capacity)
 * 问题: n个物品，重量weights[i]，价值values[i]，容量capacity，求最大价值
 */
int knapsack01(const vector<int>& weights, const vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < n; i++) {
        // 倒序遍历防止重复选取
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }

    return dp[capacity];
}

vector<int> weights = {1, 3, 4, 5};
vector<int> values = {1, 4, 5, 7};
int capacity = 7;
int maxValue = knapsack01(weights, values, capacity);  // 返回: 9

/**
 * 最长公共子序列（LCS）
 * 时间: O(m × n)
 * 空间: O(m × n)
 * 返回: 最长公共子序列的长度
 */
int longestCommonSubsequence(const string& text1, const string& text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

/**
 * 最长递增子序列（LIS）- 二分优化版
 * 时间: O(n log n)
 * 空间: O(n)
 */
int lengthOfLIS(const vector<int>& nums) {
    if (nums.empty()) return 0;

    vector<int> tails;  // tails[i]表示长度为i+1的递增子序列的最小末尾

    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);  // 扩展最长子序列
        } else {
            *it = num;  // 替换，保持更小末尾
        }
    }

    return tails.size();
}

/**
 * 最大子数组和（Kadane算法）
 * 时间: O(n)
 * 空间: O(1)
 */
int maxSubArraySum(const vector<int>& nums) {
    if (nums.empty()) return 0;

    int currentSum = nums[0];
    int maxSum = nums[0];

    for (size_t i = 1; i < nums.size(); i++) {
        // 要么从当前开始，要么延续之前的子数组
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }

    return maxSum;
}

/**
 * 链表节点定义
 */
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

/**
 * 二叉树节点定义
 */
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/**
 * 并查集（Union-Find）
 * 时间: 均摊O(α(n))，近似O(1)
 * 空间: O(n)
 * 功能: 连通性判断、连通分量计数
 */
struct UnionFind {
    vector<int> parent;  // 父节点
    vector<int> rank;    // 秩（用于按秩合并）
    int count;           // 连通分量数

    UnionFind(int n) : count(n) {
        parent.resize(n);
        rank.resize(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];
    }

    // 合并两个集合
    bool unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;

        // 按秩合并
        if (rank[rootX] < rank[rootY]) swap(rootX, rootY);
        parent[rootY] = rootX;
        if (rank[rootX] == rank[rootY]) rank[rootX]++;

        count--;
        return true;
    }

    // 判断是否连通
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

UnionFind uf(5);  // 5个节点: 0, 1, 2, 3, 4
uf.unite(0, 1);
uf.unite(1, 2);
cout << uf.connected(0, 2);  // true
cout << uf.count;            // 3 (连通分量数)

/**
 * Trie树节点
 */
struct TrieNode {  // struct结构体：自定义复合数据类型
    TrieNode* children[26];
    bool isEnd;
    int count;  // 经过该节点的单词数

    TrieNode() {
        memset(children, 0, sizeof(children));
        isEnd = false;
        count = 0;
    }
};

/**
 * Trie树
 * 时间: 插入/搜索/前缀匹配都是O(m)，m为单词长度
 * 空间: O(N × m)，N为单词数
 */
class Trie {
private:
    TrieNode* root;

public:
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
            node->count++;
        }
        node->isEnd = true;
    }

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

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

Trie trie;
trie.insert("apple");
trie.insert("app");
cout << trie.search("apple");   // true
cout << trie.search("app");     // true
cout << trie.startsWith("ap");  // true

/**
 * 线段树 - 区间和查询 + 单点修改
 * 时间: 查询/修改都是O(log n)
 * 空间: O(4n)
 */
class SegmentTree {
private:
    vector<int> tree;   // 线段树数组
    vector<int> lazy;   // 懒标记数组
    int n;

    void build(const vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void pushDown(int node, int start, int end) {
        if (lazy[node] != 0) {
            int mid = (start + end) / 2;
            tree[2 * node] += lazy[node] * (mid - start + 1);
            lazy[2 * node] += lazy[node];
            tree[2 * node + 1] += lazy[node] * (end - mid);
            lazy[2 * node + 1] += lazy[node];
            lazy[node] = 0;
        }
    }

    int queryRange(int node, int start, int end, int left, int right) {
        if (left > end || right < start) return 0;
        if (left <= start && end <= right) return tree[node];

        pushDown(node, start, end);
        int mid = (start + end) / 2;
        return queryRange(2 * node, start, mid, left, right) +
               queryRange(2 * node + 1, mid + 1, end, left, right);
    }

    void updatePoint(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        pushDown(node, start, end);
        int mid = (start + end) / 2;
        if (idx <= mid) updatePoint(2 * node, start, mid, idx, val);
        else updatePoint(2 * node + 1, mid + 1, end, idx, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

public:
    SegmentTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        lazy.resize(4 * n, 0);
        build(arr, 1, 0, n - 1);
    }

    int query(int left, int right) {
        return queryRange(1, 0, n - 1, left, right);
    }

    void update(int idx, int val) {
        updatePoint(1, 0, n - 1, idx, val);
    }
};

SegmentTree st({1, 3, 5, 7, 9, 11});
cout << st.query(1, 4);  // 3+5+7+9 = 24
st.update(2, 10);        // 将索引2的值改为10
cout << st.query(1, 4);  // 3+10+7+9 = 29

/**
 * 树状数组（Fenwick Tree / BIT）
 * 时间: 查询/修改都是O(log n)
 * 空间: O(n)
 * 适用: 前缀和查询、单点修改
 */
class FenwickTree {
private:
    vector<int> tree;
    int n;

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

public:
    FenwickTree(int size) : n(size) {
        tree.resize(n + 1, 0);
    }

    // 在索引idx处增加val
    void update(int idx, int val) {
        idx++;
        while (idx <= n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }

    // 查询[0, idx]的和
    int query(int idx) {
        idx++;
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }

    // 查询[left, right]的和
    int query(int left, int right) {
        if (left == 0) return query(right);
        return query(right) - query(left - 1);
    }
};

/**
 * LRU缓存
 * 时间: get/put都是O(1)
 * 空间: O(capacity)
 * 实现: 哈希表 + 双向链表
 */
class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache;  // {key, value}
    unordered_map<int, list<pair<int, int>>::iterator> map;

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

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;
        // 移到队首（最近使用）
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            // 更新值并移到队首
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
            return;
        }
        // 插入新元素
        cache.push_front({key, value});
        map[key] = cache.begin();
        // 超出容量，删除最久未使用的
        if (cache.size() > capacity) {
            map.erase(cache.back().first);
            cache.pop_back();
        }
    }
};

/**
 * 全排列 - 回溯算法
 * 时间: O(n! × n)
 * 空间: O(n)
 */
void backtrackPermute(vector<int>& nums, vector<bool>& used,
                      vector<int>& current, vector<vector<int>>& result) {
    if (current.size() == nums.size()) {
        result.push_back(current);
        return;
    }

    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;

        used[i] = true;
        current.push_back(nums[i]);
        backtrackPermute(nums, used, current, result);
        current.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    vector<bool> used(nums.size(), false);
    backtrackPermute(nums, used, current, result);
    return result;
}

vector<int> nums = {1, 2, 3};
vector<vector<int>> result = permute(nums);
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

/**
 * 快速幂
 * 时间: O(log exp)
 * 空间: O(1)
 * 计算: (base^exp) % mod
 */
long long fastPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;

    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }

    return result;
}