C++ 基本算法知识点详解

📋 摘要

C++ 常用算法详解，含代码实现、复杂度分析与应用场景
对应面试问答见 03-Resources/interview/C++ 基本算法
完整系列：C++ 基础-初级、C++ 基础-中级、C++ 基础-高级、C++ STL、03-Resources/cpp/C++ 并发编程、03-Resources/cpp/C++ 网络编程、03-Resources/cpp/C++ 数据结构、03-Resources/cpp/C++ 设计模式、03-Resources/cpp/C++ 基本算法、03-Resources/cpp/C++ Linux 编程
当前覆盖：排序、查找、分治、双指针/滑动窗口、单调栈/单调队列、贪心、动态规划、回溯、位运算、KMP、图算法(BFS/DFS/Dijkstra/Bellman-Ford/Floyd/拓扑/最小生成树)

ℹ️ 代码约定

本文代码统一使用 #include <bits/stdc++.h>（GCC/Clang 下可用，macOS 用 g++ -std=c++17 编译），若用 MSVC 请替换为 <vector>、<queue>、<algorithm> 等具体头文件。
使用了结构化绑定 auto [a, b]，需 -std=c++17 或更高。
每个示例 main 均包含可直接运行的测试用例。

快速排序的原理和实现？

核心思想

快速排序是分治 + 原地的排序：每次选一个基准（pivot），把小于它的元素放到左边、大于它的放到右边，再对左右子区间递归。partition 是关键操作。

代码实现

C++

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

int partition(vector<int>& a, int l, int r) {
    int pivot = a[r];        // 选最右元素为基准
    int i = l;               // i 指向「第一个 >= pivot」的位置
    for (int j = l; j < r; ++j) {
        if (a[j] < pivot) {
            swap(a[i], a[j]);
            ++i;
        }
    }
    swap(a[i], a[r]);        // 把基准放到正确位置
    return i;
}

void quickSort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);
    quickSort(a, p + 1, r);
}

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    quickSort(a, 0, a.size() - 1);
    for (int x : a) cout << x << " ";
    cout << endl; // 1 1 2 3 4 5 6 9
    return 0;
}

QuickSort-Partition

复杂度

时间：平均 O(n log n)，最坏 O(n²)（已有序且每次选到最大/最小基准）
空间：O(log n)（递归栈深度，原地排序）

应用场景

一般内部排序首选，std::sort 即快排 + 插入排序 + 堆排序的混合（introsort）
大数据量、对空间敏感的场景（原地）

💡 面试加分项

提到「随机选 pivot / 三数取中」可避免最坏情况；提到 std::sort 是 introsort（递归过深转堆排序）能体现对标准库实现的理解。

归并排序的原理和实现？

核心思想

归并排序也是分治：先把数组对半递归排序，再把两个有序子数组合并。合并时 a[i] <= a[j] 先取左边，保证稳定性。

代码实现

C++

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

void mergeArr(vector<int>& a, int l, int mid, int r) {
    vector<int> tmp(r - l + 1);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= 保证稳定
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int p = 0; p < k; ++p) a[l + p] = tmp[p];
}

void mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(a, l, mid);
    mergeSort(a, mid + 1, r);
    mergeArr(a, l, mid, r);
}

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    mergeSort(a, 0, a.size() - 1);
    for (int x : a) cout << x << " ";
    cout << endl; // 1 1 2 3 4 5 6 9
    return 0;
}

复杂度

时间：O(n log n)（任何情况都稳定，最坏也是 O(n log n)）
空间：O(n)（需要临时数组，非原地）

应用场景

需要稳定排序且数据量大的外部排序（磁盘排序）
求逆序对数量、链表归并排序（O(1) 额外空间）

ℹ️ 对比快排

快排原地但最坏 O(n²)、不稳定；归并稳定且保证 O(n log n)，但要 O(n) 空间。工程上内存敏感用快排，稳定性要求用归并或 stable_sort。

堆排序的原理？

核心思想

利用大顶堆：先 O(n) 建堆，然后反复把堆顶（最大值）与末尾交换、缩小堆范围、下沉调整，得到升序序列。堆用数组模拟完全二叉树，节点 i 的左右孩子为 2i+1、2i+2。

代码实现

C++

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

void heapify(vector<int>& a, int n, int i) {
    int largest = i;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != i) {
        swap(a[i], a[largest]);
        heapify(a, n, largest);
    }
}

void heapSort(vector<int>& a) {
    int n = a.size();
    for (int i = n / 2 - 1; i >= 0; --i) heapify(a, n, i); // 建大顶堆
    for (int i = n - 1; i > 0; --i) {
        swap(a[0], a[i]);      // 最大值移到末尾
        heapify(a, i, 0);      // 缩小堆再调整
    }
}

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    heapSort(a);
    for (int x : a) cout << x << " ";
    cout << endl; // 1 1 2 3 4 5 6 9
    return 0;
}

复杂度

时间：O(n log n)（建堆 O(n)，每次调整 O(log n)）
空间：O(1)（原地）

应用场景

大数据中找 Top-K（用大小为 K 的小顶堆，O(n log K)）
优先队列/定时器/任务调度的底层实现（std::priority_queue）

💡 面试加分项

求 Top-K 时，K 大用小顶堆、K 小用大顶堆；std::priority_queue 默认大顶堆，小顶堆用 priority_queue<int, vector<int>, greater<int>>。

冒泡、插入、选择排序的对比？

三种简单排序实现

C++

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

void bubbleSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 提前终止
    }
}

void insertionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; ++i) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}



void selectionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[minIdx]) minIdx = j;
        swap(a[i], a[minIdx]);
    }
}

int main() {
    vector<int> a1 = {3, 1, 4, 1, 5};
    bubbleSort(a1);
    vector<int> a2 = {3, 1, 4, 1, 5};
    insertionSort(a2);
    vector<int> a3 = {3, 1, 4, 1, 5};
    selectionSort(a3);
    for (int x : a1) cout << x << " "; cout << endl;
    for (int x : a2) cout << x << " "; cout << endl;
    for (int x : a3) cout << x << " "; cout << endl;
    return 0;
}

对比表

排序	最好	平均	最坏	空间	稳定
冒泡	O(n)	O(n²)	O(n²)	O(1)	稳定
插入	O(n)	O(n²)	O(n²)	O(1)	稳定
选择	O(n²)	O(n²)	O(n²)	O(1)	不稳定

应用场景

数据规模小（几十以内）时插入排序效率常优于快排，是 std::sort 的底层小规模策略
近乎有序数据用插入/冒泡接近 O(n)
教学与理解排序思想

⚠️ 易错点

选择排序不稳定（交换会破坏相对顺序），插入排序稳定（> 而非 >= 保证）。面试常问「哪个简单排序最稳定」。

排序算法的稳定性总结？

稳定性定义

稳定：值相等的元素排序后相对顺序不变（可用于按多关键字依次排序）。

总结表

排序	时间（平均）	空间	稳定
冒泡	O(n²)	O(1)	稳定
插入	O(n²)	O(1)	稳定
选择	O(n²)	O(1)	不稳定
快速	O(n log n)	O(log n)	不稳定
归并	O(n log n)	O(n)	稳定
堆	O(n log n)	O(1)	不稳定
计数	O(n+k)	O(k)	稳定
基数	O(d(n+k))	O(n+k)	稳定

记忆口诀

稳定：冒泡、插入、归并、计数、基数、桶（取决于实现）
不稳定：选择、快排、堆排、希尔

应用场景

电商「先按价格降序、再按销量降序」需稳定排序
C++ 中 std::stable_sort 即稳定排序（内部为归并）

💡 面试加分项

不稳定原因各不同：快排是 partition 交换、选择是跨距交换、堆排是堆顶与末尾交换——能解释「哪一步破坏了稳定性」是高分答案。

二分查找的实现和边界处理？

核心思想

在有序数组上每次把搜索区间减半。边界处理是易错点：注意 l <= r 还是 l < r、mid 是否取整溢出。

代码实现（标准闭区间写法）

C++

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

int binarySearch(vector<int>& a, int target) {
    int l = 0, r = a.size() - 1;      // 闭区间 [l, r]
    while (l <= r) {
        int mid = l + (r - l) / 2;     // 防溢出，不用 (l+r)/2
        if (a[mid] == target) return mid;
        else if (a[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> a = {1, 3, 5, 7, 9};
    cout << binarySearch(a, 7) << endl;  // 3
    cout << binarySearch(a, 4) << endl;  // -1
    return 0;
}

复杂度

时间：O(log n)
空间：O(1)

应用场景

有序数组/有序结构查找，std::binary_search、std::lower_bound、std::upper_bound
有序集合 std::set/std::map 的查询底层（红黑树，也是 O(log n)）

⚠️ 边界易错点

① (l+r)/2 在大数下会溢出，用 l+(r-l)/2；② 闭区间用 l<=r，半开区间 [l,r) 用 l<r；③ mid 的加减 1 决定是否会死循环。

二分查找变体（找第一个/最后一个等于 target）？

核心思想

用 lower_bound（第一个 >= target）和 upper_bound（第一个 > target）组合得到边界，避免重复元素查找错位。

代码实现

C++

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

// 第一个 >= target
int lowerBound(vector<int>& a, int target) {
    int l = 0, r = a.size();            // 半开区间 [l, r)
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] < target) l = mid + 1;
        else r = mid;                    // 收缩右边界，不 -1
    }
    return l;
}

// 第一个 > target
int upperBound(vector<int>& a, int target) {
    int l = 0, r = a.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] <= target) l = mid + 1;
        else r = mid;
    }
    return l;
}

int main() {
    vector<int> a = {1, 2, 2, 2, 3, 5};
    int first = lowerBound(a, 2);       // 第一个等于 2 的位置 = 1
    int last  = upperBound(a, 2) - 1;   // 最后一个等于 2 的位置 = 3
    cout << "count=" << upperBound(a, 2) - lowerBound(a, 2) << endl; // 3
    cout << "first=" << first << " last=" << last << endl;
    return 0;
}

复杂度

时间：O(log n)，空间：O(1)

应用场景

有序数组中求某值的出现次数 = upperBound - lowerBound
找「第一个满足条件的元素」类问题（二分答案的泛化）

💡 面试加分项

std::lower_bound(v.begin(), v.end(), x) 返回迭代器，std::distance 得下标；直接说「STL 有现成的 lower_bound/upper_bound，自己写注意半开区间与收缩方向」。

双指针技巧？适用场景？

核心思想

用两个指针在数组/链表上同向或相向移动，把暴力 O(n²) 降到 O(n)。分「左右指针」「快慢指针」「滑动窗口」几类。

代码实现（有序数组两数之和 + 移动零）

C++

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

// 有序数组两数之和（左右指针相向）
vector<int> twoSumSorted(vector<int>& a, int target) {
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int sum = a[l] + a[r];
        if (sum == target) return {l, r};
        else if (sum < target) ++l;
        else --r;
    }
    return {-1, -1};
}

// 移动零（快慢指针同向）
void moveZeroes(vector<int>& a) {
    int slow = 0;
    for (int fast = 0; fast < a.size(); ++fast) {
        if (a[fast] != 0) swap(a[slow++], a[fast]);
    }
}

int main() {
    vector<int> a = {2, 7, 11, 15};
    auto r = twoSumSorted(a, 9);
    cout << r[0] << " " << r[1] << endl; // 0 1

    vector<int> b = {0, 1, 0, 3, 12};
    moveZeroes(b);
    for (int x : b) cout << x << " ";    // 1 3 12 0 0
    cout << endl;
    return 0;
}

复杂度

时间：O(n)（每个指针最多移动 n 次）
空间：O(1)

应用场景

有序数组两数之和、三数之和、接雨水、盛水最多容器
链表找中点、判环（快慢指针）、删除重复元素
原地去重/移动元素

💡 面试加分项

能说出「双指针本质是把暴力两层循环的一层用指针单调移动代替，前提是有序或满足单调性」即掌握精髓。

滑动窗口？适用场景？

核心思想

双指针的进阶：维护一个 [left, right] 窗口，right 扩张、left 收缩，常用于连续子数组/子串满足某条件的最长/最短问题。

代码实现（无重复字符的最长子串）

C++

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

int lengthOfLongestSubstring(string s) {
    unordered_set<char> win;
    int l = 0, ans = 0;
    for (int r = 0; r < s.size(); ++r) {
        while (win.count(s[r])) {   // 有重复就收缩左边界
            win.erase(s[l]);
            ++l;
        }
        win.insert(s[r]);
        ans = max(ans, r - l + 1);
    }
    return ans;
}

int main() {
    cout << lengthOfLongestSubstring("abcabcbb") << endl; // 3
    cout << lengthOfLongestSubstring("bbbbb") << endl;    // 1
    return 0;
}

复杂度

时间：O(n)（left/right 各移动 O(n) 次）
空间：O(k)（字符集大小）

应用场景

无重复字符最长子串、和为 target 的最短/最长子数组
字符串包含、异位词（字母排列）匹配

💡 面试加分项

模板：外层 for 扩张 right，内层 while 收缩 left；复杂度是 O(n) 而非 O(n²)，因为两个指针都单调移动。

贪心算法的思想？适用场景？

核心思想

每一步做当前看起来最优的选择，期望得到全局最优。前提是问题具有「贪心选择性质」和「最优子结构」。贪心无回溯，通常比 DP 快。

代码实现（活动选择问题）

C++

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

// 每个活动 [start, end)，选最多不重叠活动
int activitySelection(vector<pair<int,int>>& acts) {
    sort(acts.begin(), acts.end(),
         [](auto& x, auto& y) { return x.second < y.second; }); // 按结束时间排序
    int cnt = 1, lastEnd = acts[0].second;
    for (int i = 1; i < acts.size(); ++i) {
        if (acts[i].first >= lastEnd) {   // 不相交则选
            ++cnt;
            lastEnd = acts[i].second;
        }
    }
    return cnt;
}

int main() {
    vector<pair<int,int>> acts = {{1, 3}, {2, 5}, {4, 6}, {6, 7}, {5, 8}};
    cout << activitySelection(acts) << endl; // 3
    return 0;
}

复杂度

时间：O(n log n)（排序主导），空间：O(1)

应用场景

活动安排、区间调度、哈夫曼编码、找零（硬币面额特殊时）
最小生成树（Prim/Kruskal）、单源最短路径（Dijkstra）本质都是贪心

⚠️ 适用边界

贪心不总是最优，如 0/1 背包、部分找零组合不能用贪心。面试要能说出「贪心 vs DP：贪心每步不可撤销、DP 枚举所有子问题」。

动态规划的思想？如何写状态转移方程？

核心思想

DP 把大问题拆成重叠子问题，保存子问题结果避免重复计算，关键是「最优子结构 + 状态定义 + 状态转移」。

写状态转移方程的步骤

定义状态 dp[i]（或 dp[i][j]）表示什么
找状态如何由更小状态推得（转移方程）
确定 base case 与遍历顺序
可滚动数组/一维化优化空间

代码实现（斐波那契：记忆化 + 自底向上）

C++

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

// 自底向上（空间优化到 O(1)）
int fib(int n) {
    if (n <= 1) return n;
    int prev = 0, cur = 1;
    for (int i = 2; i <= n; ++i) {
        int next = prev + cur;
        prev = cur;
        cur = next;
    }
    return cur;
}

int main() {
    cout << fib(10) << endl; // 55
    return 0;
}

复杂度

时间：O(n)，空间：O(1)（原版 O(n) 空间）

应用场景

最优化问题：背包、LIS、编辑距离、矩阵链乘
计数问题、博弈问题、状态压缩 DP

💡 面试加分项

三大要素：状态定义、转移方程、边界条件。会说「先用递归 + 记忆化想清楚，再转成迭代」体现方法论。

经典 DP：01 背包问题？

核心思想

有 n 件物品（重量 w[i]、价值 v[i]），背包容量 W，每件只能选或不选。dp[j] = 容量 j 能装的最大价值，逆序遍历容量避免一件物品被重复选。

代码实现

C++

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

int knapsack01(vector<int>& w, vector<int>& v, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < w.size(); ++i)
        for (int j = W; j >= w[i]; --j)   // 逆序保证每件只用一次
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[W];
}

int main() {
    vector<int> w = {2, 3, 4, 5};
    vector<int> v = {3, 4, 5, 6};
    cout << knapsack01(w, v, 8) << endl; // 10
    return 0;
}

复杂度

时间：O(nW)，空间：O(W)（一维优化）

应用场景

资源分配、预算约束下的最优选择、装箱问题
完全背包（物品无限）改为正序遍历

💡 面试加分项

一维数组逆序是关键；二维 dp[i][j] 到一维 dp[j] 的优化理由：新值只依赖上一行，逆序防止覆盖后重复使用。

经典 DP：最长递增子序列 LIS？

核心思想

dp[i] = 以 a[i] 结尾的最长递增子序列长度，dp[i] = max(dp[j]+1)（j<i 且 a[j]<a[i]）。可用二分优化到 O(n log n)。

代码实现

C++

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

// O(n^2) DP
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int ans = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (nums[j] < nums[i])
                dp[i] = max(dp[i], dp[j] + 1);
    return *max_element(dp.begin(), dp.end());
}

// O(n log n) 贪心 + 二分：tails 存长度为 i+1 的 LIS 的最小末尾
int lengthOfLISFast(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << lengthOfLIS(nums) << endl;     // 4
    cout << lengthOfLISFast(nums) << endl; // 4
    return 0;
}

复杂度

DP：O(n²) 时间 O(n) 空间
二分优化：O(n log n) 时间 O(n) 空间

应用场景

序列分析、俄罗斯套娃信封、最少划分递增子序列数
求 LIS 长度用二分，求具体序列用 DP 记录前驱

💡 面试加分项

能讲清 tails 数组含义（长度 i 的 LIS 的最小末尾）及 lower_bound 的替换逻辑，是区分普通回答与高分的点。

回溯算法的思想？全排列问题？

核心思想

回溯 = 暴力搜索 + 剪枝：沿一条路径走到底，不行就撤销选择退回上一步换分支。本质是 DFS，核心三件事：做选择、递归、撤销。

代码实现（全排列）

C++

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

void backtrack(vector<int>& nums, int start, vector<vector<int>>& res) {
    if (start == nums.size()) {
        res.push_back(nums);
        return;
    }
    for (int i = start; i < nums.size(); ++i) {
        swap(nums[start], nums[i]);     // 做选择
        backtrack(nums, start + 1, res);
        swap(nums[start], nums[i]);     // 撤销选择
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> res;
    backtrack(nums, 0, res);
    for (auto& p : res) {
        for (int x : p) cout << x << " ";
        cout << endl;
    }
    return 0;
}

复杂度

时间：O(n·n!)（n! 种排列，每种 O(n) 拷贝）
空间：O(n)（递归栈）

应用场景

全排列、组合、子集、N 皇后、数独、括号生成
所有需要「穷举 + 剪枝」的搜索问题

💡 面试加分项

回溯框架：for 选择 in 选择列表 { 做选择; backtrack; 撤销 }；用 used 数组或 swap 去重，含重复元素时先排序再剪枝。

位运算的常用技巧？

核心思想

位运算 O(1) 时间操作二进制位，是常数优化与状态压缩的基础。

常用技巧代码

C++

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

int main() {
    int x = 12;              // 1100
    int y = 10;              // 1010

    cout << (x & y) << endl;   // 8  与
    cout << (x | y) << endl;   // 14 或
    cout << (x ^ y) << endl;   // 6  异或
    cout << (~x) << endl;      // -13 取反

    cout << (x << 1) << endl;  // 24 左移 = *2
    cout << (x >> 1) << endl;  // 6  右移 = /2

    // 判断奇偶
    cout << (x & 1) << endl;   // 0 偶数
    // 去掉最低位的 1
    cout << (x & (x - 1)) << endl;   // 8  (1100 -> 1000)
    // 取最低位的 1
    cout << (x & -x) << endl;        // 4  (lowbit)
    // 判断是否为 2 的幂
    cout << ((x & (x - 1)) == 0) << endl; // 0
    // 交换两数（异或法）
    int a = 3, b = 5;
    a ^= b; b ^= a; a ^= b;
    cout << a << " " << b << endl;   // 5 3
    return 0;
}

复杂度

时间：O(1)，空间：O(1)

应用场景

状态压缩 DP（用 bitmask 表示集合）、集合子集枚举
快速乘除 2 的幂、哈希、权限位、Bloom filter、位图

💡 面试加分项

x & -x 取 lowbit 用于树状数组；x & (x-1) 去最低位 1 可用于统计 1 的个数（__builtin_popcount）。

KMP 算法的原理？

核心思想

KMP 用前缀函数 next（最长相等前后缀）在失配时不回退主串指针，只回退模式串，把暴力 O(nm) 降到 O(n+m)。

代码实现

C++

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

vector<int> buildNext(const string& p) {
    int m = p.size();
    vector<int> next(m, 0);
    for (int i = 1, j = 0; i < m; ++i) {
        while (j > 0 && p[i] != p[j]) j = next[j - 1];
        if (p[i] == p[j]) ++j;
        next[i] = j;
    }
    return next;
}

int kmp(const string& s, const string& p) {
    vector<int> next = buildNext(p);
    for (int i = 0, j = 0; i < s.size(); ++i) {
        while (j > 0 && s[i] != p[j]) j = next[j - 1];
        if (s[i] == p[j]) ++j;
        if (j == p.size()) return i - j + 1; // 匹配成功，返回起始下标
    }
    return -1;
}

int main() {
    cout << kmp("ababcabcabababd", "ababd") << endl; // 10
    return 0;
}

复杂度

时间：O(n + m)（n 主串长、m 模式串长）
空间：O(m)（next 数组）

应用场景

字符串匹配（std::string::find 用更复杂的实现）、DNA 序列匹配、文本编辑器查找
求字符串周期（m - next[m-1] 是最小循环节长度）

💡 面试加分项

next 数组含义是「前缀与后缀的最长公共长度」；失配时 j = next[j-1] 是把模式串移动到已匹配后缀的前缀位置，主串 i 不回退。

BFS 和 DFS 的应用场景？

核心思想

DFS（深度优先）：沿一条路走到底再回溯，用栈（递归/显式），适合找所有解、连通性、拓扑、判环。
BFS（广度优先）：按层扩散，用队列，适合无权图最短路径。

代码实现（邻接表遍历）

C++

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

void dfs(int u, vector<vector<int>>& g, vector<bool>& vis) {
    vis[u] = true;
    cout << u << " ";
    for (int v : g[u])
        if (!vis[v]) dfs(v, g, vis);
}

void bfs(int s, vector<vector<int>>& g, int n) {
    vector<bool> vis(n, false);
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : g[u])
            if (!vis[v]) { vis[v] = true; q.push(v); }
    }
}

int main() {
    int n = 6;
    vector<vector<int>> g(n);
    vector<pair<int,int>> edges = {{0,1},{0,2},{1,3},{1,4},{2,5}};
    for (auto [u, v] : edges) { g[u].push_back(v); g[v].push_back(u); }

    vector<bool> vis(n, false);
    dfs(0, g, vis); cout << endl;   // 0 1 3 4 2 5
    bfs(0, g, n); cout << endl;      // 0 1 2 3 4 5
    return 0;
}

复杂度

时间：O(V + E)，空间：O(V)

应用场景

DFS：连通分量、环检测、拓扑排序（DFS 版）、回溯类题目、迷宫生成
BFS：无权图最短路径、层序遍历、朋友圈/岛屿数量、最小步数问题

💡 面试加分项

求「最少步数/最短路径」首选 BFS；求「所有路径/是否存在路径」用 DFS；记忆化搜索是 DFS + DP。

Dijkstra 最短路径算法？

核心思想

从源点出发，每次选距离最小且未确定的节点，用它的边松弛邻居。用最小堆优化到 O((V+E) log V)。要求边权非负。

代码实现（堆优化）

C++

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

vector<int> dijkstra(int n, vector<vector<pair<int,int>>>& g, int s) {
    vector<int> dist(n, INT_MAX);
    dist[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;          // 过期条目跳过
        for (auto [v, w] : g[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    int n = 5;
    vector<vector<pair<int,int>>> g(n);
    g[0] = {{1, 2}, {3, 6}};
    g[1] = {{2, 3}, {3, 8}, {4, 5}};
    g[2] = {{4, 7}};
    g[3] = {{4, 9}};
    auto dist = dijkstra(n, g, 0);
    for (int d : dist) cout << d << " "; // 0 2 5 6 7
    cout << endl;
    return 0;
}

复杂度

时间：O((V + E) log V)，空间：O(V)

应用场景

地图导航、网络路由（OSPF）、带权非负图最短路
有负权用 Bellman-Ford 或 SPFA

💡 面试加分项

堆优化用 priority_queue（可能有重复节点，用 d > dist[u] 跳过过期值）；与 BFS 区别：BFS 无权，Dijkstra 有权。

拓扑排序？

核心思想

对有向无环图（DAG），把节点排成线性序列使每条边 u->v 都满足 u 在 v 前。Kahn 算法：不断取出入度为 0 的节点。

代码实现（Kahn 算法）

C++

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

vector<int> topoSort(int n, vector<vector<int>>& g) {
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; ++u)
        for (int v : g[u]) ++indeg[v];
    queue<int> q;
    for (int i = 0; i < n; ++i)
        if (indeg[i] == 0) q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : g[u])
            if (--indeg[v] == 0) q.push(v);
    }
    return order.size() == n ? order : vector<int>(); // 空 = 有环
}

int main() {
    int n = 6;
    vector<vector<int>> g(n);
    g[5] = {2, 0};
    g[4] = {0, 1};
    g[2] = {3};
    g[3] = {1};
    auto order = topoSort(n, g);
    for (int x : order) cout << x << " "; // 4 5 0 2 3 1（其一）
    cout << endl;
    return 0;
}

复杂度

时间：O(V + E)，空间：O(V)

应用场景

课程表、任务调度依赖、编译依赖（make）、依赖解析
环检测（拓扑序列长度 < V 说明有环）

💡 面试加分项

两种实现：Kahn（BFS + 入度）与 DFS 后序遍历逆序；LeetCode 课程表 I/II 是经典题。

最小生成树 Prim 和 Kruskal？

核心思想

求连通加权无向图的边权和最小的生成树。

Prim：从点出发，每次选连接已选集合与外部的最小边（类似 Dijkstra，稠密图优）。
Kruskal：把所有边排序，用并查集贪心选不形成环的最小边（稀疏图优）。

代码实现

C++

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

// Prim（稠密图 O(V^2) 邻接矩阵版）
int prim(vector<vector<int>>& g) { // g[i][j] = 边权，无穷大表示无边
    int n = g.size();
    vector<int> dist(n, INT_MAX);
    vector<bool> inMST(n, false);
    dist[0] = 0;
    int total = 0;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int v = 0; v < n; ++v)
            if (!inMST[v] && (u == -1 || dist[v] < dist[u])) u = v;
        if (u == -1) return -1;          // 不连通
        inMST[u] = true;
        total += dist[u];
        for (int v = 0; v < n; ++v)
            if (!inMST[v] && g[u][v] < dist[v]) dist[v] = g[u][v];
    }
    return total;
}

struct DSU {
    vector<int> p;
    DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    void unite(int a, int b) { p[find(a)] = find(b); }
};

// Kruskal（稀疏图 O(E log E)）：edges 存 {w, u, v}
int kruskal(int n, vector<array<int,3>> edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    int total = 0, cnt = 0;
    for (auto [w, u, v] : edges) {
        if (dsu.find(u) != dsu.find(v)) {
            dsu.unite(u, v);
            total += w;
            ++cnt;
        }
    }
    return cnt == n - 1 ? total : -1;
}

int main() {
    int INF = INT_MAX;
    vector<vector<int>> g = {
        {0, 2, INF, 6, INF},
        {2, 0, 3, 8, 5},
        {INF, 3, 0, INF, 7},
        {6, 8, INF, 0, 9},
        {INF, 5, 7, 9, 0},
    };
    cout << "Prim=" << prim(g) << endl;       // 16

    vector<array<int,3>> edges = {
        {2, 0, 1}, {6, 0, 3},
        {3, 1, 2}, {8, 1, 3}, {5, 1, 4},
        {7, 2, 4}, {9, 3, 4},
    };
    cout << "Kruskal=" << kruskal(5, edges) << endl; // 16
    return 0;
}

复杂度

Prim：O(V²)（邻接矩阵）或 O(E log V)（堆优化）
Kruskal：O(E log E)

应用场景

网络布线、管道铺设、道路建设最小成本
稠密图选 Prim，稀疏图选 Kruskal

💡 面试加分项

Prim 与 Dijkstra 代码几乎一样，只是 dist 含义不同（到集合最小边 vs 到源最短距离）；Kruskal 用并查集判环。

单调栈和单调队列的原理？适用场景？

核心思想

单调栈：栈内元素的值保持单调（递增或递减）。新元素入栈前，先弹出所有「会破坏单调性」的栈顶元素。这样每个元素最多入栈、出栈各一次，把暴力 O(n²) 降到 O(n)，常用于「找每个元素左/右边第一个更大或更小的元素」。
单调队列：用双端队列维护一个单调序列，队头永远是当前「窗口」内的最值。入队时从队尾弹出破坏单调性的元素，再根据窗口范围从队头弹出过期元素。常用于「滑动窗口最值」。

两者都是双指针/滑动窗口的进阶：本质是用「单调性」让每个元素只进/出一次，替代两层循环中重复的扫描。

代码实现

C++

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

// 单调栈：找每个元素右边第一个更大的元素（Next Greater Element）
vector<int> nextGreater(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st;                 // 存下标，其值保持单调递减（栈底大、栈顶小）
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[i] > nums[st.top()]) {
            res[st.top()] = nums[i]; // 当前元素是栈顶元素右边第一个更大
            st.pop();
        }
        st.push(i);
    }
    return res;
}

// 单调队列：滑动窗口最大值
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;                 // 存下标，值单调递减，队头是窗口最大值
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        while (!dq.empty() && nums[i] >= nums[dq.back()]) dq.pop_back(); // 队尾维护单调递减
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front(); // 队头弹出窗口外的过期元素
        if (i >= k - 1) res.push_back(nums[dq.front()]);
    }
    return res;
}

int main() {
    vector<int> a = {2, 1, 2, 4, 3};
    auto ng = nextGreater(a);
    for (int x : ng) cout << x << " "; // 4 2 4 -1 -1
    cout << endl;

    vector<int> b = {1, 3, -1, -3, 5, 3, 6, 7};
    auto m = maxSlidingWindow(b, 3);
    for (int x : m) cout << x << " "; // 3 3 5 5 6 7
    cout << endl;
    return 0;
}

复杂度

单调栈：时间 O(n)，空间 O(n)（每个元素最多入栈、出栈一次）
单调队列：时间 O(n)，空间 O(k)（窗口大小，最坏 O(n)）

应用场景

单调栈：每日温度、下一个更大/更小元素、接雨水、柱状图中最大的矩形、字典序最小子序列
单调队列：滑动窗口最大值/最小值、带限制（下标跨度）的最优子序列、队列优化的 DP

💡 面试加分项

能说清「为什么是 O(n) 而非 O(n²)」：虽然有两层循环，但内层 while 总共只弹出 n 次（每个元素至多被弹出一次）。单调栈求「下一个更小」只需把比较方向反过来。

Bellman-Ford 和 Floyd 最短路径算法的原理？

核心思想

Bellman-Ford：求单源最短路，对所有边反复松弛 n-1 轮（最短路最多经过 n-1 条边）。能处理负权边，并能在第 n 轮检测负环（第 n 轮仍能松弛说明存在负环）。时间 O(VE)。
Floyd-Warshall：求多源最短路，动态规划：d[i][j] 表示 i 到 j 的最短距离，依次尝试把每个点 k 作为中转点，d[i][j] = min(d[i][j], d[i][k] + d[k][j])。可处理负权（但不能有负环）。时间 O(V³)。

与 Dijkstra 的对比：Dijkstra 只能处理非负权且是贪心；Bellman-Ford 用动态规划思想处理负权；Floyd 解决「任意两点」而非单源。

代码实现

C++

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

// Bellman-Ford：单源最短路，支持负权，可检测负环
vector<int> bellmanFord(int n, vector<array<int,3>>& edges, int s) {
    vector<int> dist(n, INT_MAX);
    dist[s] = 0;
    for (int i = 0; i < n - 1; ++i) {        // 松弛 n-1 轮
        bool relaxed = false;
        for (auto [u, v, w] : edges) {
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                relaxed = true;
            }
        }
        if (!relaxed) break;                 // 本轮无松弛，提前退出
    }
    for (auto [u, v, w] : edges)             // 第 n 轮检测负环
        if (dist[u] != INT_MAX && dist[u] + w < dist[v])
            return {};                       // 返回空表示存在负环
    return dist;
}

// Floyd-Warshall：多源最短路，可处理负权（无负环）
const int INF = INT_MAX;
void floyd(vector<vector<int>>& d, int n) {
    for (int k = 0; k < n; ++k)              // 中转点 k 必须放最外层
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (d[i][k] != INF && d[k][j] != INF)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
    // Bellman-Ford 测试：0->1=4, 0->2=5, 1->2=-2, 2->3=3, 1->3=6
    int n = 4;
    vector<array<int,3>> edges = {
        {0, 1, 4}, {0, 2, 5}, {1, 2, -2}, {2, 3, 3}, {1, 3, 6}
    };
    auto dist = bellmanFord(n, edges, 0);
    for (int d : dist) cout << d << " "; // 0 4 2 5（含负权边 -2 仍正确）
    cout << endl;

    // Floyd 测试：同构图用邻接矩阵表示
    vector<vector<int>> d = {
        {0, 4, 5, INF},
        {INF, 0, -2, 6},
        {INF, INF, 0, 3},
        {INF, INF, INF, 0},
    };
    floyd(d, n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            cout << (d[i][j] == INF ? -1 : d[i][j]) << " ";
        cout << endl;
    }
    // 输出（-1 表示不可达）：
    // 0 4 2 5
    // -1 0 -2 1
    // -1 -1 0 3
    // -1 -1 -1 0
    return 0;
}

复杂度

Bellman-Ford：时间 O(VE)，空间 O(V)
Floyd：时间 O(V³)，空间 O(V²)

应用场景

Bellman-Ford：含负权边的单源最短路、检测负环（如套汇问题）、SPFA 是其队列优化版
Floyd：小规模图的任意两点最短路（V ≤ 几百）、传递闭包、求最小环、多源最短路预处理

💡 面试加分项

Floyd 三层循环顺序固定为 k（中转点）、i、j，k 放最外层是正确性关键；Bellman-Ford 每轮松弛所有边、最多 n-1 轮，SPFA 是其入队优化但最坏仍是 O(VE)。