Data Structure & Algorithms
Data Structure & Algorithms
This is for test takers to quickly review the basics and key points of DSA. Moreover, this is the masterpiece written by toutou(偷偷).The main language is in Chinese but you can see some concepts in English & Japanese. And the pseudocode is in the style of C++. Let’s quickly review this subject!
这是偷偷刷了很多修考题之后总结出来的修考秘籍，全文都是考点，彻底高能。
1. Introduction to Algorithms
这一章主要计划复习时间复杂度(Time Complexity) 和 空间复杂度(Space Complexity) 两个概念，然后再仔细回顾 分治递归(DIvide & Conquer) 这一重要的概念。最后再给出解决时间复杂度常用的分析方法和万能的主定理公式（Master Theorem）
1.1 时间复杂度与空间复杂度
Space Complexity: 空间复杂度描述的是算法运行时所需的额外内存空间。通俗解释就是算法在运行的时候需要开辟多少空间的大小。O(1)指一个点集；O(n)就是开辟一个一维空间；O(n^2)开辟二维空间；O(n^3)开辟三维空间。在第二章讲解排序算法的时候，也会用到本章非常多的前置知识。
O(1): 常数空间复杂度，表示算法所需的额外空间是固定的，不随输入规模变化。例如，一个固定大小的变量。
O(n): 线性空间复杂度，表示算法所需的额外空间与输入规模成正比。例如，一个长度为 n 的数组。
O(n^2): 平方空间复杂度，表示算法所需的额外空间与输入规模的平方成正比。例如，一个 n x n 的二维数组。
O(n^3): 立方空间复杂度，表示算法所需的额外空间与输入规模的立方成正比。例如，一个 n x n x n 的三维数组。
一些常见的数据结构的空间复杂度：
vector<vector<vector<int>>> nums // 三维数组：O(n^3)
vector<vector<int>> nums // 二维数组：O(n^2)
stack<int> st; // 栈：O(n)
deque<int> que; // 双端队列：O(n)
list<int> linkedList; // 链表：O(n)Time complexity: 时间复杂度是衡量算法效率的重要指标之一，它描述了算法执行所需时间随输入规模增长的变化情况。这是修考中必考的一个地方：（1）如分析给出的代码的时间复杂度（Hint：关注for，while循环）（2）根据源代码优化时间复杂度设计新的算法（Hint：空间换时间）
常见的时间复杂度有以下几种：
O(1): 常数时间复杂度，算法的执行时间不随输入规模变化。例如，访问数组中的某个元素。
int a = nums[10] // 给a赋值数组下标为10的元素
O(n): 线性时间复杂度，算法的执行时间与输入规模成正比。例如，遍历一个长度为 n 的数组。
for (int i = 0; i < n; i++) { /* 操作 */ }
O(log n): 对数时间复杂度，算法的执行时间随输入规模的对数增长。例如，二分查找(Binary Search)算法。
int binarySearch(int[] arr, int target) { /* 二分查找逻辑 */ }
O(n^2) : 平方时间复杂度，算法的执行时间与输入规模的平方成正比。例如，冒泡排序(Bubble Sort)算法。
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { /* 冒泡排序逻辑 */ } }
O(2^n): 指数时间复杂度，算法的执行时间随输入规模的指数增长。例如，解决所有子集问题的递归算法。
void subsets(int[] nums) { /* 递归逻辑 */ }
在描述使劲复杂度的时候，有三种表示需要注意一下：
$O$: 表示渐进上界； $\Omega$: 表示渐进下界； $\Theta$: 渐进紧确界
1.2 分治递归(Divide & Conquer)
分治递归(Divide & conquer)的思想是将原问题分割成更小的子问题，自顶向下地解决每个子问题，并最终自底向上合并它们的解来解决主问题。
常见的分治递归有：二分查找(Binary Search) 和归并排序(Merge Sort).
1.2.1 二分查找(Binary Search)
// 前提nums是有序数组
int binarySearch(vector<int>& nums, int target){
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int mid = left + (right - left) / 2; // (避免left + right) / 2 的溢出
if(nums[mid] == target) return mid; // 找到目标，返回索引
else if(nums[mid] > target) right = mid - 1; // 目标在左半部分
else left = mid + 1; // 目标在右半部分
}
return -1;
}根据上图我们得出递归表达式：
$T(n) = T(n / 2) + O(1)$， 得出$T(n) = O(log_{2}{n})$
1.2.2 归并排序(Merge Sort)
这个图像有效地展示了归并排序的"分而治之"策略：
1.将大问题（排序整个数组）分解成小问题（排序子数组）
2.解决小问题（对小数组排序）
3.将小问题的解合并成大问题的解（合并有序子数组）
// 合并两个有序的子数组
void merge(vector<int>& nums, int left, int mid, int right) {
int n1 = mid - left + 1; // 左子数组的长度
int n2 = right - mid; // 右子数组的长度
// 创建临时数组存储左右子数组
vector<int> leftArr(n1), rightArr(n2);
// 复制数据到临时数组
for (int i = 0; i < n1; ++i) leftArr[i] = nums[left + i];
for (int i = 0; i < n2; ++i) rightArr[i] = nums[mid + 1 + i];
int i = 0, j = 0, k = left; // i是左子数组指针，j是右子数组指针，k是合并后数组的指针
// 合并左右子数组
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
nums[k] = leftArr[i];
i++;
} else {
nums[k] = rightArr[j];
j++;
}
k++;
}
// 将剩余的左子数组元素加入nums
while (i < n1) {
nums[k] = leftArr[i];
i++;
k++;
}
// 将剩余的右子数组元素加入nums
while (j < n2) {
nums[k] = rightArr[j];
j++;
k++;
}
}
// 递归实现归并排序
void mergeSort(vector<int>& nums, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 递归排序左右两部分
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 合并已排序的部分
merge(nums, left, mid, right);
}
}递归式：$T(n) = 2T(n / 2) + O(n)$, 所以$T(n) = O(nlog_{2}{n})$
1.3 主定理(Master Theorem)
递归方程形式如：
$$T(n) = aT(n / b) + O(n^d)$$
其中，$a$表示子问题的数量，b表示每个子问题是原问题规模的$1/b$, $O(n^d)$ 表示在每一层分治过程之外，解决问题所需的额外代价，通常是合并或分割的代价。
情况 1：
如果$log_{b}{a} > d$，则递归式的解为：
$$ T(n) = O(\log_{b}{a}) $$
解释： 在这种情况下，分治产生的子问题数量增长得更快，主导时间复杂度的是递归中的分治部分。
情况 2：
如果$log_{b}{a} = d$，则递归式的解为：
$$ T(n) = O(n^d\log{n}) $$
解释： 在这种情况下，分治和额外开销的增长速度相同，因此总的时间复杂度是 $n^d\log{n}$。
情况 3：
如果 $log_{b}{a} < d$，则递归式的解为：
$$T(n) = O(n^d)$$
解释： 在这种情况下，额外的开销主导时间复杂度，因此复杂度主要由 $n^d$决定。
斯特林近似公式（Stirling’s Formula）: $n! \approx \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n$
2.Sorting Algorithm
再时间复杂度和空间复杂度的概念后，并引入了分治递归和归并排序算法；接下来这一章就主要回顾常见的一些排序算法，然后分析他们的时间复杂度和空间复杂度。
2.1 插入排序(Insertion Sort)
这个算法的过程也很直观：插入排序的核心思想是将一个新元素插入到已经排好序的子序列中的适当位置。
最好的情况下是：原数组规模小或者大部分数据有序，那么我们一次遍历就可以完成好排序。 最坏的情况下是：原数组是降序排列的，意思是每一次插入新元素的时候，都要遍历一遍已排好序的子数组。
void insertion_sort(vector<int>& nums){
// 从第二个元素开始
for(int i = 1; i < nums.size(); i++){
int j = i;
// 回溯检查并交换
while(j > 0 && nums[j] < nums[j - 1]){
swap(nums[j], nums[j - 1]);
j--;
}
}
return;
}最坏情况：$T(n) = T(n - 1) + O(n)$, $T(n) = O(n^2)$
最好情况：$T(n) = T(n - 1) + O(1)$, $T(n) = O(n)$
2.2冒泡排序(Bubble Sort)
冒泡排序是一个直观的算法，通过重复地遍历数组来工作。在每次遍历中，它比较相邻的元素并在需要时交换它们，这样每次迭代都会将当前未排序部分中的最大元素’冒泡’到数组的末尾正确位置。这个过程从左到右重复进行，直到整个数组排序完成。一句话概括就是：不断的进行两两比较。
void bubbleSort(vector<int>& arr) {
int n = arr.size();
// 控制循环的轮数
for (int i = 0; i < n - 1; i++) {
// 内层循环，相邻比较
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
std::swap(arr[j], arr[j + 1]);
}
}
}
}冒泡排序平均时间复杂度：$T(n) = O(n^2)$
2.3选择排序(Selection Sort)
选择排序的基本思想是分阶段地将数组划分为两部分：已排序部分和未排序部分。每一轮从未排序部分中找到最小（或最大）的元素，放到已排序部分的末尾，直到整个数组排序完成。
void selectionSort(vector<int>& arr) {
int n = arr.size();
// 已排序数组末尾
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
// 找未排序数组中的最小元素
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
swap(arr[i], arr[minIdx]);
}
}
}选择排序时间复杂度： $T(n) = O(n^2)$
2.4快速排序(Quick Sort)
快速排序的本质是分治法。它通过选择一个基准元素，将原数组划分为小于基准元素和大于基准元素的两个子数组，然后对这两个子数组进行递归排序。
// 分区函数
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // 小于基准的元素的索引
for (int j = low; j <= high - 1; 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);
}
}在最坏情况下，基准元素可能是最大或最小值，这会导致一个子数组为空，另一个子数组的大小为 $n-1$，此时的时间复杂度为 $T(n) = T(n-1) + O(n) =O(n^2)$。而在平均情况下，基准元素能够较好地划分数组，时间复杂度为 $T(n) = 2T(n/2) + O(n)=O(n\log{n})$ 。
2.5堆排序(Heap Sort)
这个考点应该是修考最爱考的一个了！（敲重点）堆排序的基本思想是不断维护一个最大堆。在每次排序过程中，首先将最大堆的根节点（最大值）与堆的最后一个元素交换，然后缩小堆的范围（排除最后一个元素），并对新的根节点进行下沉操作，以恢复最大堆的性质。重复这一过程，直到所有元素都被排序。
// 堆化函数，用于维护最大堆性质
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]);
// 在减小的堆上调用 max heapify
heapify(arr, i, 0);
}
}建堆的时间复杂度为$O(n)$,每个节点的调整最多为$O(\log{n})$次。在排序的过程中需要建堆$O(n)$次，并且每次需要$O(logn)$来维护堆(heapify),因此对排序总的时间复杂度为$O(n\log{n})$
3.Data Structure
这一章主要讲解常见的数据结构,如栈(stack),队列(queue),链表(linked list),哈希表(hash map),以及字符串(string)。二叉树考点众多我会单独做成一章并且和图算法一块复习。
3.1 Stack & Queue
栈(stack) :后进先出(LIFO), 队列 :先进先出(FIFO)。另外，栈和队列是可以相互实现的，了解到这个程度，我认为就掌握到栈和队列的基本性质了。
Q1: 如何用栈实现队列？
A: 开两个栈，一个负责栈负责放入元素，另一个栈负责弹出元素
class MyQueue {
public:
// 一个栈负责放入元素，一个栈负责弹出元素
stack<int> in, out;
MyQueue() {}
// 模拟入队过程
void push(int x) {
in.push(x);
return;
}
// 模拟弹出队首元素过程
int pop() {
if(out.empty()){
while(!in.empty()){
out.push(in.top());
in.pop();
}
}
int ans = out.top();
out.pop();
return ans;
}
// 获取队首元素的值
int peek() {
// 获取队首元素的值
int ans = this->pop();
// 放回
out.push(ans);
return ans;
}
// 判断队列是否为空
bool empty() {
return in.empty() && out.empty();
}
};Q2：如何用队列实现栈？
A：开两个队列，一个模拟入栈，一个模拟出栈。更优化的方式是直接开一个队列即可,不断的出队入队就可以实现栈的性质。
class MyStack {
public:
// 一个队列负责入栈，一个负责出栈
queue<int> in, out;
MyStack() {}
// 放入元素
void push(int x) {
in.push(x);
return;
}
// 把in队列的元素不断出队只剩一个，即时栈顶
int pop() {
while(in.size() > 1){
out.push(in.front());
in.pop();
}
int ans = in.front();
in.pop();
swap(in, out); // 交换两个队列
return ans;
}
// 获取栈顶的元素
int top() {
int ans = this->pop(); // 获取弹出后的值
in.push(ans); // 再放入队列
return ans;
}
bool empty() {
return in.empty() && out.empty();
}
};优化后的实现：
class MyStack {
public:
queue<int> que;
MyStack() {}
// 放入元素
void push(int x) {
que.push(x);
}
// 弹出栈顶元素
int pop() {
int n = que.size();
n--; // 把对位元素调整到队首
while(n--){
que.push(que.front());
que.pop();
}
int ans = que.front();
que.pop();
return ans;
}
// 获取栈顶元素
int top() {
int ans = this->pop();
que.push(ans);
return ans;
}
// 判断队列是否为空
bool empty() {
return que.empty();
}
};3.2 Linked List
常见的链表有单链表和双链表。单链表：每个节点只包含一个指向下一个节点的指针，访问节点时只能从头节点开始向后遍历。双链表：每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。这使得可以在链表中向前和向后遍历。
链表的优缺点
优点：1)动态大小：链表的大小可以动态调整，不像数组那样需要预先定义大小。2)方便插入和删除：在链表中插入或删除节点的时间复杂度为 O(1)，只需调整指针，而数组则可能需要移动大量元素。
缺点：1)内存占用：每个节点需要额外的存储空间来存储指针，导致比数组更高的内存开销。2)随机访问困难：链表不支持快速随机访问，查找元素的时间复杂度为 O(n)。
3.3 Hash Map
哈希映射（Hash Map） 是一种数据结构，用于以键值对（key-value pairs）形式存储数据。它通过一个哈希函数将键映射到数组中的索引，从而实现快速的数据访问。主要特点有：
1）快速查找：平均情况下，哈希映射可以在 O(1) 时间内进行查找、插入和删除操作。
2）键值对存储：每个元素都由一个唯一的键和与之关联的值组成，可以通过键快速访问对应的值。
3）哈希函数：将键转换为数组索引的函数，好的哈希函数可以减少冲突（不同键映射到相同索引）。
4）处理冲突：常用的方法包括链式法(chaining)和开放寻址法（open addressing）。
为了减少哈希冲突，哈希映射的函数要尽量将不同的输入键均匀地映射到哈希表的不同索引，以减少冲突（即不同键映射到相同索引的情况）。
3.4 string
字符串这个数据结构直观易懂，主要涉及到的考点有KMP算法和sequence alignment算法。这里主要回顾一下KMP算法，关于string类型的其他考点：最长子序列问题和序列比对(Sequence Alignment)，会在后面动态规划章节中仔细讲解。
3.4.1 KMP算法
KMP算法可以说是学一次忘一次……建议考前一定要临时报佛脚记一下。这个算法的美妙之处就是在于优化了暴力匹配，用前缀表来跳过重复的匹配过程。前缀表就是模式串中每个位置的最长相等前缀和后缀的长度。在发生不匹配的情况下，将子串移动前一个字符串的前缀表的具体值。（感觉京大最喜欢考KMP算法了）
4.Binary Tree
关于二叉树的考点有许多，像是考二叉树的遍历，二叉搜索树（Binary Search Tree），最小生成树（MST），以及AVL树。首先需要了解二叉树的一些基本性质，例如每个节点的下标，以及二叉树的多种遍历方式。
4.1 Concepts of Binary Tree
完全二叉树（complete binary tree）：是一种二叉树，其中每一层都是满的，除了可能是最后一层，且最后一层的节点从左到右排列。在完全二叉树中，所有的节点都尽可能地靠左排列，这种结构使得它在存储和操作上更为高效。与全二叉树不同，完全二叉树允许最后一层不满，但仍需保持左侧填充。
对于一个完全二叉树，如果节点的索引为$i$,节点数为$n$那么：
- 左孩子节点索引: $2i$
- 右孩子节点索引: $2i + 1$
- 父亲节点索引: $[i/2]$
- 二叉树高度: $ceil(log_{2}{(n+1)})$ 或 $floor(log_{2}{n}) + 1$
全二叉树（full binary tree）：是指每个节点要么没有子节点，要么恰好有两个子节点的二叉树。在这种树中，除了叶子节点外，所有节点都有两个子节点。这样的结构确保了树的每一层都被完全填满，只有最后一层可能不满。
二叉搜索树（Binary Search Tree, BST）: 是一种二叉树，其中每个节点都包含一个键值，左子树的所有节点键值小于该节点，右子树的所有节点键值大于该节点。这种结构使得查找、插入和删除操作的平均时间复杂度为 O(log n)。其主要性质包括：每个节点最多有两个子节点，左子树和右子树都是二叉搜索树，且没有重复的键值。
二叉搜索树的搜索迭代实现：
TreeNode* searchBST(TreeNode* root, int val) {
while(root){
if(val > root->val) root = root->right;
else if(val < root->val) root = root->left;
else return root;
}
return nullptr;
}4.2 Tree Traversal
层序遍历（Level Order Traversal）： 开一个队列处理一层的节点并放入下一层的节点。这个遍历也属于广度优先遍历（BFS）。
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
vector<int> nums;
int n = que.size();
while(n--){
auto node = que.front();
que.pop();
nums.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
res.push_back(nums);
}
return res;
}二叉树的深度优先遍历（DFS） 可以分为三种：前序遍历，中序遍历和后序遍历。
前序遍历（Preorder Traversal）： 根->左->右，递归实现
vector<int> res;
vector<int> preorderTraversal(TreeNode* root) {
if(!root) return res;
res.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
return res;
}当然也可以开一个栈来实现
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
while(root || !st.empty()){
if(root){
ans.push_back(root->val);
if(root->right){
st.push(root->right);
}
root = root->left;
}
else{
root = st.top();
st.pop();
}
}
return ans;
}后序遍历（Postorder Traversal）： 左->右->根，递归实现
vector<int> res;
vector<int> postorderTraversal(TreeNode* root) {
if(!root) return res;
postorderTraversal(root->left);
postorderTraversal(root->right);
res.push_back(root->val);
return res;
}后序遍历同样可以开一个栈来实现
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if(root == nullptr) return ans;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()){
TreeNode* cur = st.top();
if(cur->left){
st.push(cur->left);
cur->left = NULL;
}
else{
if(cur->right){
st.push(cur->right);
cur->right = NULL;
}
else{
ans.push_back(cur->val);
st.pop();
}
}
}
return ans;
}中序遍历（Inorder Traversal）： 左->根->右，递归实现
vector<int> res;
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return res;
inorderTraversal(root->left);
res.push_back(root->val);
inorderTraversal(root->right);
return res;当然也可以开一个栈来实现：
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
while(root || !st.empty()){
while(root){
st.push(root);
root = root->left;
}
root = st.top();
st.pop();
ans.push_back(root->val);
root = root-> right;
}
return ans;
}二叉树的中序遍历还有一个重要的考点是逆波兰表达式,这个曾经在京大的过去问中出现过。逆波兰表达式（Reverse Polish Notation, RPN） 是一种后缀表示法，用于表示算术表达式。在这种表示法中，运算符跟在操作数之后，而不是在它们之间。这种形式的好处是消除了括号的需要，因为操作的顺序总是由操作符的位置决定。具体的实现方法可以开一个栈轻松解决。
4.3 AVL Tree
AVL树是一种自平衡的二叉搜索树，确保每个节点的左右子树高度差（平衡因子）最多为1。这样可以保证树的高度在 $O(log{n})$ 范围内，确保高效的插入、删除和查找操作。AVL树通过旋转操作来维持平衡，从而优化性能，特别是在频繁修改的场景中。东工有一年考到了这个点，但我认为了解到AVL树的工作原理就ok了,主要聚焦在节点的添加和删除以及树的旋转。
5.Graph Theory
本章主要讲解图的基本算法，最小生成树，单源最短路径算法，单源最短路径算法和多源最短路径算法，以及最大流问题。修考题的图算法都是套的模版，因此了解算法的核心思想非常关键。
5.1图的基本算法
对于图的表示，我们需要建立一个邻接矩阵(adjacency matrix),简单图的邻接矩阵是(0,1)矩阵并且对角线元素都为0。无向图的邻接矩阵是对称矩阵。
5.1.1 BFS
在二叉树章节中讲解了树的深度遍历算法，在图中，我们可以同样的利用邻接链表（也就是建一个数组）来获取当前遍历的节点的邻接节点，开一个数组记录已访问的节点，最后利用队列实现层序遍历。
class Graph {
private:
int V; // Number of vertices
std::vector<std::vector<int>> adj; // Adjacency list
public:
Graph(int v) : V(v), adj(v) {}
// Function to add an edge to the graph
void addEdge(int v, int w) {
adj[v].push_back(w);
}
// BFS traversal starting from given source vertex
void BFS(int s) {
// Mark all vertices as not visited
vector<bool> visited(V, false);
// Create a queue for BFS
queue<int> queue;
// Mark the source node as visited and enqueue it
visited[s] = true;
queue.push(s);
while (!queue.empty()) {
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop();
// Get all adjacent vertices of the dequeued vertex s
// If an adjacent has not been visited, then mark it visited
// and enqueue it
for (int adjacent : adj[s]) {
if (!visited[adjacent]) {
visited[adjacent] = true;
queue.push(adjacent);
}
}
}
}
};5.1.2 DFS
DFS（深度优先搜索，Depth-First Search）是一种用于遍历或搜索图形或树数据结构的算法。它尽可能深地访问节点，然后回溯，寻找未访问过的节点。
基本原理：
- 初始化：从起始节点出发，将其标记为访问过。之后开始递归或使用栈
- 递归：对每个未访问的邻接节点，递归调用DFS。（递归的实现方式就是利用栈来记录每一次函数调用的状态）
栈：将节点压入栈中，访问节点时将其出栈，继续访问其未访问的邻接节点，并将这些邻接节点压入栈。 - 回溯：如果当前节点的所有邻接节点都访问过，则回溯到上一个节点，继续这个过程，直到所有节点都访问完。
class Graph { private: int V; // Number of vertices vector<vector<int>> adj; // Adjacency list void DFS(int v, vector<bool> &visited) { // Mark the current node as visited and print it visited[v] = true; cout << v << " "; // Recur for all the vertices adjacent to this vertex for (int adjacent : adj[v]) { if (!visited[adjacent]) { DFS(adjacent, visited); } } } public: Graph(int v) : V(v), adj(v) {} // Function to add an edge to the graph void addEdge(int v, int w) { adj[v].push_back(w); } // DFS traversal starting from given source vertex void DFS(int s) { // Mark all the vertices as not visited vector<bool> visited(V, false); // Call the recursive helper function to print DFS traversal DFS(s, visited); }BFS和DFS对比非常鲜明。BFS的性格是保守，害怕风险，尽量做到“广撒网，细收鱼”；而DFS则是奔放，秉持着一颗“不撞南墙不回头”，“不到黄河不死心”的感觉。
5.1.3 Topological Sort
拓扑排序（Topological Sorting）是图论中的一种线性排序方法，主要用于对有向无环图（Directed Acyclic Graph, DAG 中的顶点进行排序，使得对于图中的每一条有向边 (u → v)，顶点 u 在排序中都出现在顶点 v 的前面。
拓扑排序算法步骤：
- 计算每个顶点的入度：统计每个顶点被其他顶点指向的次数（即入度, inDegree）。
- 将所有入度为 0 的顶点加入队列：这些顶点没有任何前置依赖。
- 重复以下步骤直到队列为空：（1）从队列中取出一个顶点 u，将其加入拓扑排序结果中。（2）遍历 u 的所有邻接顶点 v，将 v 的入度减 1；如果 v 的入度变为 0，则将 v 加入队列。
- 检查结果：如果所有顶点都被处理过，则返回拓扑排序；否则，图中有环，无法进行拓扑排序。
在初始化时，需要遍历所有顶点计算入度，耗时$O(V)$；然后遍历所有边来更新入度并处理顶点，耗时$O(E)$。因此总的时间复杂度是$O(V + E)$。最终的排序顺序是: $1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7$。
class Graph {
private:
int V; // 顶点数
unordered_map<int, vector<int>> adj; // 邻接表
vector<int> inDegree; // 入度数组
public:
Graph(int v) : V(v), inDegree(v + 1, 0) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
inDegree[v]++;
}
vector<int> topologicalSort() {
vector<int> result;
queue<int> q;
// 将所有入度为0的顶点加入队列
for (int i = 1; i <= V; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
// 对于所有相邻的顶点，将其入度减1
for (int v : adj[u]) {
if (--inDegree[v] == 0) {
q.push(v);
}
}
}
// 检查是否存在环
if (result.size() != V) {
std::cout << "图中存在环，无法进行拓扑排序" << std::endl;
return {};
}
return result;
}
};5.1.4 Union Find
并查集（Union-Find） 算法，又称为不相交集数据结构，是一种用于处理元素分组及查询元素所属组的高效数据结构。它广泛应用于图论（如判断图的连通性、Kruskal算法求最小生成树）并查集主要支持两种操作：
- 查找（Find）：确定某个元素属于哪个集合（即找到该元素所在集合的代表元素或根节点）。
- 合并（Union）：将两个不同的集合合并为一个集合。
为了提高并查集的效率，通常结合以下两种优化策略：
- 路径压缩（Path Compression）：在 Find 操作中，将访问过的所有节点直接连接到根节点，从而降低树的高度。
- 按秩合并（Union by Rank）或按大小合并（Union by Size）：在 Union 操作中，总是将较小的树挂到较大的树下，保持树的平衡。
结合这两种优化后，并查集的时间复杂度几乎接近于常数时间，具体为 反阿克曼函数 的时间复杂度，几乎可以认为是 $O(1)$。
以下是一个使用路径压缩和按秩合并优化的并查集实现：
#include <vector>
class UnionFind {
private:
vector<int> parent; // 存储每个节点的父节点
vector<int> rank; // 存储每个节点的秩（树的高度）
public:
// 构造函数：初始化每个节点的父节点为自身，秩为1
UnionFind(int size) {
parent.resize(size);
rank.resize(size, 1);
for(int i = 0; i < size; ++i){
parent[i] = i;
}
}
// 查找操作：查找元素x所在集合的根节点，并进行路径压缩
int find(int x) {
if(parent[x] != x){
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
// 合并操作：将元素x和元素y所在的集合合并
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY){
return; // 已经在同一个集合中
}
// 按秩合并：将秩较小的树挂到秩较大的树下
if(rank[rootX] < rank[rootY]){
parent[rootX] = rootY;
}
else if(rank[rootX] > rank[rootY]){
parent[rootY] = rootX;
}
else{
parent[rootY] = rootX;
rank[rootX] += 1;
}
}
};5.2 Minimum Spanning Tree
最小生成树（Minimum Spanning Tree, MST） 是指在一个带权无向图中，连接所有顶点的一个子图，使得：
- 这个子图是一个树（即没有环，并且连通所有顶点）。
- 这个树的总边权和最小。
特点：
- 最小生成树包含图中所有的顶点，但只包含连接这些顶点的最少数量的边（即 $V - 1$条边，$V$为顶点数）。
- 它保证生成的树的边权总和最小。
常见的MST生成算法有2种：Kruskal算法和Prim算法。简单来说，Kruskal是基于边的选择，而Prim算法是从某个顶点开始构建最小生成树的，逐步扩展树的边界。
5.2.1 Kruskal
具体步骤为：
- 首先对所有边按权重从小到大排序。
- 然后依次利用并查集（Union Find）检查每条边的两个顶点是否属于不同的集合，如果是，则将它们合并，并将该边加入最小生成树。
- 重复这个过程，直到最小生成树中包含了$V−1$条边。
时间复杂度： 边排序耗时$O(ElogE)$，并查集操作近似为$O(1)$，因此总时间复杂度为$O(ElogE)$。
// 边的结构体，包含起点、终点和权重
struct Edge {
int u, v, weight;
// 比较函数，按照权重升序排序
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};
// 并查集（Union-Find）结构体
struct UnionFind {
vector<int> parent, rank;
// 初始化并查集，所有节点的父节点初始化为自己，秩(rank)初始化为0
UnionFind(int n) : parent(n), rank(n, 0) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找操作，使用路径压缩
int find(int u) {
if (parent[u] != u) {
parent[u] = find(parent[u]);
}
return parent[u];
}
// 合并操作，按秩合并
void unite(int u, int v) {
int rootU = find(u);
int rootV = find(v);
if (rootU != rootV) {
if (rank[rootU] > rank[rootV]) {
parent[rootV] = rootU;
} else if (rank[rootU] < rank[rootV]) {
parent[rootU] = rootV;
} else {
parent[rootV] = rootU;
rank[rootU]++;
}
}
}
};
// Kruskal算法实现
int kruskal(int numVertices, vector<Edge>& edges) {
// 按权重升序排序所有边(至关重要的一环)
sort(edges.begin(), edges.end());
UnionFind uf(numVertices);
int mstWeight = 0; // 最小生成树的总权重
int edgesUsed = 0; // 已经加入生成树的边数
// 遍历所有边
for (const auto& edge : edges) {
// 查找两个顶点是否属于不同的集合（不同的连通分量）
if (uf.find(edge.u) != uf.find(edge.v)) {
uf.unite(edge.u, edge.v); // 将它们合并到同一个集合
mstWeight += edge.weight; // 将这条边的权重加入总权重
edgesUsed++;
// 如果已经加入V-1条边，生成树构建完毕
if (edgesUsed == numVertices - 1) {
break;
}
}
}
return mstWeight;
}5.2.2 Prim算法
Prim算法的基本思想是从一个顶点开始，逐步将与当前生成树相连的最小边加入到树中，直到包含图中所有顶点为止。不同于Kruskal算法选择的是边，Prim算法在每一步选择的是与已连接的顶点相连的最小权重边。
算法步骤：
- 初始化：选择一个起始顶点，标记为生成树的一部分。
使用一个数组/优先队列来记录所有尚未加入生成树的顶点到当前生成树的最小边的权重。 - 选择最小边：
在每一步中，从所有与生成树相连的边中选择权重最小的边（维护一个优先队列），确保这个边不会形成环。 - 更新距离：将选择的边的顶点加入生成树并更新尚未加入树的顶点到新生成树的最小边的权重。
- 重复上述步骤，直到所有顶点都被加入生成树。
对每条边的操作（插入、删除、更新最小边权重）是$O(logV)$的，因此总的时间复杂度为$O(ElogV)$，其中$E$是边的数量，$V$是顶点的数量。
// 边的结构体，包含终点和权重
struct Edge {
int to, weight;
Edge(int t, int w) : to(t), weight(w) {}
};
// Prim算法的实现
int prim(int numVertices, vector<vector<Edge>>& graph) {
// 最小生成树的总权重
int mstWeight = 0;
// 标记每个顶点是否在生成树中
vector<bool> inMST(numVertices, false);
// 记录最小权重的边的权重，初始化为无穷大(敲重点)
vector<int> minEdgeWeight(numVertices, INT_MAX);
// 优先队列（最小堆），存储{边的权重，顶点编号}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 从第0号顶点开始
minEdgeWeight[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
// 取出权重最小的边
int weight = pq.top().first;
int u = pq.top().second;
pq.pop();
// 如果顶点u已经在MST中，跳过
if (inMST[u]) continue;
// 将顶点u加入MST
inMST[u] = true;
mstWeight += weight;
// 更新与顶点u相连的其他顶点的最小边权重
for (const Edge& edge : graph[u]) {
int v = edge.to;
int w = edge.weight;
if (!inMST[v] && w < minEdgeWeight[v]) {
minEdgeWeight[v] = w;
pq.push({w, v});
}
}
}
return mstWeight;
}5.3 单源最短路径算法
单源最短路径算法（Single-Source Shortest Path, SSSP）用于从图中的一个指定起点（源点）出发，找到该点到图中所有其他顶点的最短路径。常用的单源路径算法为Dijkstra算法和Bellman-Ford算法。Dijkstra算法只能用于无负权边的图。如果图中存在负权边，Dijkstra算法的结果可能不正确。Bellman-Ford算法可以处理带负权边的图，且能够检测负权环（如果存在负权环，则说明不存在最短路径）。
5.3.1 Dijkstra’s algorithm
Dijkstra算法的基本思想是：每次贪心地从当前未处理的顶点中选择一个距离源点最近的顶点，标记其最短路径为确定，然后通过该顶点更新其邻接点的最短路径。过反复选择距离最小的顶点，并更新邻接点的路径长度，最终能确定所有顶点的最短路
时间复杂度：在使用优先队列（最小堆）的情况下，Dijkstra算法的时间复杂度为$O(ElogV)$，其中E是图中边的数量，V是顶点的数量。取出当前最小距离顶点的操作需要$O(logV)$时间。每条边被检查一次，更新时需要$O(logV)$的时间来调整优先队列。在稠密图中，算法的效率略低，因为每次更新都需要重新维护优先队列，但在稀疏图中性能良好。
struct Edge {
int to, weight;
Edge(int t, int w) : to(t), weight(w) {}
};
vector<int> dijkstra(int numVertices, vector<vector<Edge>>& graph, int source) {
vector<int> dist(numVertices, INT_MAX); // 存储从源点到每个顶点的最短距离
dist[source] = 0; // 源点到自身的距离为0
// 优先队列：最小堆，存储的是{距离, 顶点编号}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, source});
while (!pq.empty()) {
int u = pq.top().second; // 取出距离源点最近的顶点
int d = pq.top().first; // 当前顶点的最短距离
pq.pop();
// 如果当前距离已经不是最优解，跳过
if (d > dist[u]) continue;
// 更新顶点 u 的邻接点
for (const Edge& edge : graph[u]) {
int v = edge.to;
int weight = edge.weight;
// 如果通过 u 到 v 的路径更短，更新路径
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v}); // 将 v 插入优先队列
}
}
}
return dist;
}5.3.2 Bellman-Ford Algorithm
Bellman-Ford算法是一种经典的算法，用于解决单源最短路径问题（Single Source Shortest Path, SSSP），即从图中的某个源点到其他所有顶点的最短路径。它与Dijkstra算法的不同之处在于，Bellman-Ford可以处理权值为负数的边，并且能够检测出图中是否存在负权环（negative-weight cycle）。
Bellman-Ford算法的核心思想是通过松弛（relaxation） 操作逐步更新每个顶点的最短路径估计值。松弛操作的含义是，如果从某条边可以得到比当前已知更短的路径，则更新路径长度。算法通过多次迭代更新路径，确保找到全局的最短路径。
算法步骤：
- 初始化：将源点到源点的距离设为0（即$dist[source] = 0$），其他所有顶点到源点的距离初始设为正无穷大（$dist[v] = ∞$）。设定前驱节点为None或相应的初始值。
- 松弛所有边：对于图中的所有边$(u,v)$，检查是否可以通过$u$达到$v$的更短路径，即$dist[v] > dist[u] + weight(u, v)$。如果是，则更新$dist[v] = dist[u] + weight(u, v)$。重复这个过程最多$n−1$次，其中$n$是顶点的数量。因为最短路径最多包含$n−1$条边。
- 检测负权环（可选步骤）：在完成$n−1$次松弛操作后，再对所有边执行一次松弛操作。如果此时还能继续更新某个顶点的最短路径值，则说明图中存在负权环，因为在无负权环的情况下，经过$n−1$次松弛操作后，所有最短路径应该已经收敛。
边的松弛操作需要对每条边执行，图中一共有𝑚条边。算法需要对所有边重复𝑛−1次（因为最短路径最多包含𝑛−1条边），因此时间复杂度为𝑂(𝑛⋅𝑚)
// Bellmanford算法伪代码
function BellmanFord(Graph, source):
// Step 1: Initialize distances
for each vertex v in Graph:
dist[v] = ∞ // Set all distances to infinity
predecessor[v] = null // No predecessors initially
dist[source] = 0 // The distance from the source to itself is zero
// Step 2: Relax all edges n-1 times
for i from 1 to |V| - 1:
for each edge (u, v) in Graph:
if dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
predecessor[v] = u
// Step 3: Check for negative-weight cycles
for each edge (u, v) in Graph:
if dist[u] + weight(u, v) < dist[v]:
error "Graph contains a negative-weight cycle"
return dist, predecessor5.4 多源最短路径算法
5.4.1 Floyd-Wallshall’s Algorithm
Floyd-Warshall算法 是一种经典的动态规划算法，用于解决所有点对最短路径问题。它可以在加权图中找出每一对顶点之间的最短路径，即使图中包含负权重边，只要没有负权重环路（即从某个顶点出发经过一些边又回到该顶点且路径总权重为负）。京大知能的一年过去问就考了这道题的手动迭代推理，在复习这个题的时候建议和京大的过去问配合看。
算法步骤：
初始化：将距离矩阵$dist[][]$初始化为图的邻接矩阵。如果$i == j$，则$dist[i][j] = 0$，表示从节点$i$到节点$j$的路径距离为$0$。如果$i ≠ j$且两点之间有边，则$dist[i][j] = weight(i, j)$，否则$dist[i][j]设为∞$（表示两点不直接相连）。
动态规划：通过三重循环逐步更新每对顶点之间的最短距离。外层循环选取一个中间顶点$k$，中间两层循环更新每一对顶点$i$和$j$之间的最短路径，判断是否通过$k$可以得到更短的路径。如果$dist[i][k] + dist[k][j] < dist[i][j]$，则更新$dist[i][j]$。公式为：
$$ dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j]) $$
时间复杂度：
Floyd-Warshall算法的时间复杂度为$O(V³)$，其中$V$是图中顶点的数量。三重嵌套循环的每一层都依赖于顶点的数量，因此该算法适合顶点较少的图。对于边多（稠密图）且顶点数量不多的情况，它是一个有效的算法。
void floydWarshall(int graph[V][V]) {
int dist[V][V]; // 存储最短路径
// 初始化距离矩阵，将其设为输入图的邻接矩阵
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// 三重循环：i是起点，j是终点，k是中间节点
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// 如果从i通过k到j的路径更短，则更新dist[i][j]
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}5.5 Maximum FLow Problem
最大流问题是网络流理论中的一个经典问题，旨在寻找在一个流网络（或称为容量网络）中，从源点到汇点的最大可能流量。这个问题可以应用于很多实际场景，比如交通网络、物流系统、通信网络等。
最大流问题的定义：
流网络：由顶点集和边集组成的有向图，其中每条边都有一个非负的容量，表示能通过该边的最大流量。这个网络中有一个特定的顶点被称为源点（source），另一个顶点称为汇点（sink）。
流量：从源点到汇点传输的流称为流量。流量需要遵守以下两个条件：
容量限制：每条边上的流量不能超过该边的容量。
流量守恒：除了源点和汇点，其他顶点的流入流量与流出流量相等。
本章只讲解Ford-Fulkerson算法，有余力可以再了解一下Edmonds-Karp算法和Push-Relabel算法。
5.5.1 Ford-Fulkerson Algorithm
福特-福尔克森算法的核心思想是利用增广路径（Augmenting Path）来增加网络中的流量。增广路径是指在残余网络（Residual Network）中，从源点到汇点的一条路径，且路径上的每条边都有剩余容量（Residual Capacity）大于零。算法通过反复寻找这样的路径，并沿路径增加流量，直到没有增广路径为止。
初始状态：
如图所示，所有边的初始流量都为 0。我们的目标是找到从源点 S 到汇点 T 的最大流。
第一次迭代：
- a. 找一条增广路径，例如：S -> A -> C -> T
- b. 这条路径的瓶颈容量是 5（A 到 C 的边）
- c. 更新流量：
$$
\begin{aligned}
S \to A: &\ 0/10 \rightarrow 5/10 \\
A \to C: &\ 0/5 \rightarrow 5/5 \\
C \to T: &\ 0/9 \rightarrow 5/9
\end{aligned}
$$
第二次迭代：
- a. 找另一条增广路径，例如：S -> B -> D -> T
- b. 这条路径的瓶颈容量是 6（D 到 T 的边）
- c. 更新流量：
$$
\begin{aligned}
S \to B: &\ 0/8 \rightarrow 6/8 \\
B \to D: &\ 0/7 \rightarrow 6/7 \\
D \to T: &\ 0/6 \rightarrow 6/6
\end{aligned}
$$
第三次迭代：
- a. 找下一条增广路径，例如：S -> A -> D -> T
- b. 这条路径的瓶颈容量是 3（A 到 D 的边）
- c. 更新流量：
$$
\begin{aligned}
S \to A: &\ 5/10 \rightarrow 8/10 \\
A \to D: &\ 0/3 \rightarrow 3/3 \\
D \to T: &\ 6/6 \text{（已满，无法增加）}
\end{aligned}
$$
算法终止：
此时，我们无法找到从 S 到 T 的更多增广路径。所有通向 T 的边都已经满了：
- $C \to T: 5/9$
- $D \to T: 6/6$
计算最大流：
最大流等于从源点出发的所有流量之和：
$$
8\ (\text{S} \to \text{A}) + 6\ (\text{S} \to \text{B}) = 14
$$
也等于进入汇点的所有流量之和：
$$
5\ (\text{C} \to \text{T}) + 6\ (\text{D} \to \text{T}) = 11
$$
最终结果：
- 最大流值为 14
- S -> A -> C -> T 路径上流量为 5
- S -> B -> D -> T 路径上流量为 6
- S -> A -> D -> T 路径上流量为 3
Ford-Fulkerson 算法的核心思想是不断寻找增广路径并增加流量，直到无法找到更多的增广路径为止。每次找到增广路径后，我们都会更新网络中的流量，直到达到最大流。
function FordFulkerson(Graph G, Node source, Node sink):
// 初始化残余图
ResidualGraph Gf = CreateResidualGraph(G)
// 初始化最大流为0
maxFlow = 0
while true:
// 在残余图中寻找增广路径
Path augmentingPath = FindAugmentingPath(Gf, source, sink)
// 如果没有找到增广路径，算法终止
if augmentingPath is empty:
break
// 找到增广路径上的最小残余容量
minResidualCapacity = FindMinResidualCapacity(augmentingPath)
// 更新残余图
UpdateResidualGraph(Gf, augmentingPath, minResidualCapacity)
// 增加最大流
maxFlow = maxFlow + minResidualCapacity
return maxFlow
function FindAugmentingPath(ResidualGraph Gf, Node source, Node sink):
// 使用DFS或BFS寻找从source到sink的路径
// 返回找到的路径，如果没有路径则返回空
function FindMinResidualCapacity(Path augmentingPath):
// 遍历路径，找到最小的残余容量
// 返回最小残余容量
function UpdateResidualGraph(ResidualGraph Gf, Path augmentingPath, int minResidualCapacity):
for each edge (u, v) in augmentingPath:
// 减少正向边的残余容量
Gf[u][v] = Gf[u][v] - minResidualCapacity
// 增加反向边的残余容量
Gf[v][u] = Gf[v][u] + minResidualCapacity
function CreateResidualGraph(Graph G):
// 创建一个与原图结构相同的残余图
// 初始化残余容量等于原图的容量
// 为每条边添加一条初始容量为0的反向边
// 返回创建的残余图6. Greedy Algorithm
贪心算法是一种算法设计范式，其核心思想是：在解决问题时，总是做出在当前状态下看起来最优的选择，即局部最优解，希望通过一系列这样的选择能够最终得到全局最优解。这个算法理解起来非常直观，但是合理性证明的话需要严格的数学证明。本章着重讲解最经典的最大子序和问题（Maximum Subarray） 和合并区间问题（Merge Intervals）
6.1 Maximum Subarray
这道问题可以直接上Leetcode 53题练习。
问题描述是：Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
解决这个问题的贪心算法也叫Kadane算法：算法从左到右遍历一次数组，在每一步，它都计算当前位置结束的子数组的最大和（Current Sum）同时，它保持追踪全局的最大和（Max Sum）。最终，Max Sum的最后一个值就是整个问题的解。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = INT_MIN;
int curSum = 0;
for(auto x : nums){
curSum += x;
if(curSum < x) curSum = x; // 贪心地取子数组最大值
if(curSum > maxSum) maxSum = curSum; // 不断更新结果
}
return maxSum;
}
};6.2 Merge Intervals
这道问题可以直接上Leetcode 56题练习。
题目描述：Given an array of intervals where $\text{intervals}[i] = [\text{start}_i, \text{end}_i]$, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
解决这道题的思路是：先排序让所有相邻的区间尽可能重合在一起(以开端最小优先，其次结尾最小次之)，然后一次遍历贪心地选择局部最优解。
class Solution {
public:
// 重载cmp函数，让区间的排列以开端最小优先，其次结尾最小优先
static bool cmp(vector<int>& a, vector<int>& b){
if(a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> result;
result.push_back(intervals[0]);
// 贪心地选择是否合并区间
for(int i = 1; i < intervals.size(); i++){
// 若不重合，则加入结果数组
if(intervals[i][0] > result.back()[1]) result.push_back(intervals[i]);
// 若重合，则合并区间并贪心的选择区间结尾
else result.back()[1] = max(result.back()[1], intervals[i][1]);
}
return result;
}
};7. Dynamic Programming
动态规划（Dynamic Programming, DP） 是一种用于解决最优化问题的算法设计技巧。它通过将问题分解为更小的子问题，并记录其解来避免重复计算，从而提高算法的效率。本章主要讲解5个经典DP问题：斐波那契数列，背包问题，股票问题，最长公共子序列，以及序列比对问题。
7.1 Fibonacci Sequence
形如：$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….$的数列称之为斐波那契数，我们可以很轻易地得到递归式：$dp[n] = dp[n-1] + dp[n-2]$,然后我们再对递归式子进行初始化：$dp[0] = 1, dp[1] = 1$, 我们就可以利用递归式求得所有的斐波那契数。
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
vector<int> dp(N + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
};7.2 Knapsack Problem
关于背包问题有三种：0-1背包，完全背包，多重背包。应对修考我认为掌握0-1背包问题就足够了。关于0-1背包的问题描述是：
- 一组物品，每个物品都有一个重量和一个价值。
- 一个背包，具有固定的容量。
给定$n$个物品，每个物品$i$具有重量$w[i]$和价值$v[i]$，还有一个背包的最大容量$W$。目标是选择物品的组合，使得在不超过背包容量的情况下，背包中的物品总价值最大。
1.定义状态： $dp[i][j]$表示在考虑前$i$个物品，且背包容量为$j$时的最大价值。
2.状态转移方程： 对于每个物品$i$，有两个选择：
- 不放入背包：此时最大价值为$dp[i-1][j]$。
- 放入背包：此时最大价值为$dp[i-1][j - w[i]] + v[i]$，前提是当前物品的重量不超过背包容量 $j >= w[i]$。
因此，状态转移方程为：
$$
dp[i][j] = \begin{cases}
dp[i-1][j] & \text{if } j < w[i] \\
\max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]) & \text{if } j \geq w[i]
\end{cases}
$$
3.边界条件：
- 当没有物品可选时，最大价值为$0$，即 $(dp[0][j] = 0)$。
- 当背包容量为$0$时，最大价值也为$0$，即 $(dp[i][0] = 0)$。
4.计算顺序：
先遍历物品再遍历背包更容易理解，从 $(i = 1)$到 $(n)$，对于每个物品，再从 $(j = 0)$到$(W)$计算。当然也可以先遍历背包再遍历物品，这里不过多赘述。
5.返回结果： 最终的最大价值为 $(dp[n][W])$。
假设有以下物品和背包容量：
- 物品 1：重量 = 2，价值 = 3
- 物品 2：重量 = 3，价值 = 4
- 物品 3：重量 = 4，价值 = 5
- 物品 4：重量 = 5，价值 = 6
背包容量为 5。
遍历的核心代码：
for(int i = 0; i < w.size(); i++) { // 遍历物品
for(int j = 0; j <= W; j++) { // 遍历背包容量
if (j < w[i]) dp[i][j] = dp[i - 1][j]; // 装不下的情况
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); // 装下的情况
}
}7.3 Stock Problem
股票问题有很多种，这里介绍一种，参考Leetcode 122题。题目描述是：
You are given an integer array $prices$ where $prices[i]$ is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.
Example 1:
- Input: prices = [7,1,5,3,6,4]
- Output: 7
- Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); vector<vector<int>> dp(n, vector<int>(2, 0)); dp[0][0] = -prices[0]; // have the stock on the day 0; dp[0][1] = 0; // no stock on the day 0; for(int i = 1; i < prices.size(); i++){ dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return dp[n - 1][1]; // no stock on the day n - 1 } };
初始状态：
dp[0][0] = -prices[0]：表示在第$0$天买入股票后的利润，利润为负的股票价格。dp[0][1] = 0：表示在第$0$天没有持有股票，利润为$0$。
状态转移：
对于第$i$天，持有股票的状态
dp[i][0]，有两种可能：
- 前一天已经持有股票，保持不动：
dp[i-1][0]。 - 前一天没有持有股票，但今天买入：
dp[i-1][1] - prices[i]（买入股票，减去当天股票的价格）。
取两者的最大值：dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])。
对于第$i$天，不持有股票的状态
dp[i][1]，也有两种可能：
- 前一天已经不持有股票，保持不动：
dp[i-1][1]。 - 前一天持有股票，但今天卖出：
dp[i-1][0] + prices[i]（卖出股票，得到当前股票的价格）。
取两者的最大值：dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])。
最终结果： 返回 dp[n-1][1]，表示最后一天不持有股票的最大利润。
7.4 Longest Common Subsequence
最长公共子序列（LCS） 也是修考的一个常考点，具体参考：Leetcode 1143
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, “ace” is a subsequence of “abcde”. A common subsequence of two strings is a subsequence that is common to both strings.
Example 1:
- Input: text1 = “abcde”, text2 = “ace”
- Output: 3
- Explanation: The longest common subsequence is “ace” and its length is 3.
定义状态：
$$
dp[i][j] \text{ 表示在考虑前 } i \text{ 个字符的 } \text{text1} \text{ 和前 } j \text{ 个字符的 } \text{text2} \text{ 时的最长公共子序列的长度。}
$$
状态转移方程：
对于每个字符对text1[i-1] 和text2[j-1]，有两种情况：
- 如果
'text1[i-1] == text2[j-1]'，说明这两个字符相同，最长公共子序列可以延长 1，此时'dp[i][j] = dp[i-1][j-1] + 1'。 - 如果
'text1[i-1] != text2[j-1]'，则取决于之前的子问题结果，最长公共子序列为：- 不包括当前字符：
'dp[i][j] = max(dp[i][j-1], dp[i-1][j])'。
- 不包括当前字符：
边界条件：
- 当
'i = 0'或'j = 0'时，即有一个字符串为空，最长公共子序列长度为 0，所以初始化时'dp[0][j] = 0'和'dp[i][0] = 0'。
计算顺序：
从 'i = 1' 到 'n'，对于每个字符，再从 'j = 1' 到 'm' 计算 'dp[i][j]'，逐步构建整个表。
返回结果：
最终结果为 'dp[n][m]'，即考虑所有字符的最长公共子序列的长度。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
return dp[n][m];
}
};7.5 Sequence Alignment
序列比对（Sequence Alignment） 是生物信息学中的一个核心问题，用于比较两个或多个生物序列（如DNA、RNA或蛋白质）的相似性。其目的是通过对比序列中的元素（碱基或氨基酸）找出它们之间的最优匹配方式，进而揭示它们的进化关系、功能相似性或结构上的保守性。
7.5.1 Needleman–Wunsch algorithm
Needleman-Wunsch算法是用于进行全局序列比对的经典算法，特别适用于对比两个生物序列（如DNA、RNA或蛋白质）时，将它们的整个序列进行对齐。它采用动态规划的思想来寻找两个序列的最优对齐方式。
Needleman-Wunsch算法步骤：
定义状态：
设有两个序列 A 和 B，长度分别为 n 和 m。
创建一个大小为 (n+1) x (m+1) 的二维矩阵 dp，其中 dp[i][j] 表示序列 A 的前 i 个字符与序列 B 的前 j 个字符的最优对齐得分。
罚分机制：
- 匹配：当
A[i-1] == B[j-1]时，表示两个字符相同，得分为match score。 - 不匹配：当
A[i-1] != B[j-1]时，表示两个字符不同，得分为mismatch penalty。 - Gap：当在序列
A或B中插入一个字符时，得分为gap penalty。
初始化：
- 第一行和第一列表示序列与空序列的比对。比对空序列时，每个字符都需要插入或删除，因此使用缺口罚分（gap penalty）。
- 初始化
dp[0][0] = 0，代表两个空序列的得分为 0。 - 初始化第一行：
dp[0][j] = j * gap penalty，表示序列B的前j个字符与空序列的比对得分。 - 初始化第一列：
dp[i][0] = i * gap penalty，表示序列A的前i个字符与空序列的比对得分。
状态转移方程：对于矩阵中的每个 dp[i][j]，有三种可能的情况：
- 匹配：如果
A[i-1] == B[j-1]，即两个字符相同，则可以匹配，得分为dp[i-1][j-1] + match score。 - 不匹配：如果
A[i-1] != B[j-1]，则可以进行替换，得分为dp[i-1][j-1] + mismatch penalty。 - 插入/删除（Gap）：在序列
A或B中插入一个字符，得分为dp[i][j-1] + gap penalty或dp[i-1][j] + gap penalty。
取这三种操作中的最大值更新 dp[i][j]，即：
$$
dp[i][j] = \max\left(dp[i-1][j-1] + \text{(match/mismatch score)}, dp[i-1][j] + \text{gap penalty}, dp[i][j-1] + \text{gap penalty}\right)
$$
回溯：填完矩阵后，从右下角 dp[n][m] 开始回溯，找出最优路径，从而得到序列 A 和 B 的最优全局对齐方案。
int n = A.size();
int m = B.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
// 初始化：处理空序列的情况
for(int i = 1; i <= n; i++) dp[i][0] = i * gap_penalty; // 第一列，表示A的前i个字符和空序列的比对
for(int j = 1; j <= m; j++) dp[0][j] = j * gap_penalty; // 第一行，表示B的前j个字符和空序列的比对
// 填充 dp 表
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
// 1. 匹配或不匹配的情况
if(A[i-1] == B[j-1]) {
// 如果当前字符相等，则进行匹配，加上 match_score
int match = dp[i-1][j-1] + match_score;
} else {
// 如果当前字符不相等，则进行替换，加上 mismatch_penalty
int mismatch = dp[i-1][j-1] + mismatch_penalty;
}
// 2. 插入的情况
int insert = dp[i][j-1] + gap_penalty; // 在序列 A 中插入 gap
// 3. 删除的情况
int del = dp[i-1][j] + gap_penalty; // 在序列 B 中插入 gap
// 取三种操作的最大值来更新 dp[i][j]
dp[i][j] = max({dp[i-1][j-1] + (A[i-1] == B[j-1] ? match_score : mismatch_penalty), insert, del});
}
}
// 最终结果是 dp[n][m]，表示A和B的最优全局比对得分8. P/NP problem
P/NP问题 是计算机科学中的一个核心难题，涉及确定哪些问题可以在合理的时间内（多项式时间）被解决，和哪些问题的解可以在合理的时间内被验证。它是理论计算机科学和数学中最著名、最重要的未解决问题之一。
P类问题
P类问题（Polynomial time）指的是那些可以在多项式时间内被解决的问题。也就是说，给定一个问题实例，使用某种算法可以在输入规模为 $n$ 时，用 $n^k$（其中 $k$ 是一个常数）次运算步骤就可以得到结果。
例如，常见的排序算法（如快速排序）和图论中的最短路径算法（如Dijkstra算法）都是 P类问题。它们的时间复杂度是多项式级别的。
直观理解：如果一个问题属于P类，那么它是“容易”解决的，因为我们可以用有效的算法在合理的时间内求解。
NP类问题
NP类问题（Nondeterministic Polynomial time）是指那些解可以在多项式时间内被验证的问题，尽管可能没有已知的多项式时间算法来找到这个解。
也就是说，如果我们猜测出一个解，可以在多项式时间内检查这个解是否正确。但是，要找到这个解可能会很难，甚至没有已知的多项式时间算法来求解。
经典的NP问题 包括旅行商问题（TSP）、背包问题和布尔可满足性问题（SAT）。这些问题的特点是验证解很容易，但找到最优解可能非常耗时。
P与NP的关系
P是否属于NP？
P类问题显然也是NP类问题。如果我们能够在多项式时间内求解一个问题，那我们一定也能在多项式时间内验证这个解。
因此可以得出结论：P是NP的一个子集，即 $P \subseteq NP$。
P与NP的区别
- 关键在于我们还不确定 P类问题 和 NP类问题 是否是同一个集合。这就是 P vs NP 问题的核心所在：
- 如果 $P = NP$，那么所有能在多项式时间内验证的解也可以在多项式时间内求解。
- 如果 $P \neq NP$，那么有一些问题能在多项式时间内验证解，但没有已知的多项式时间算法来求解它们。
- 关键在于我们还不确定 P类问题 和 NP类问题 是否是同一个集合。这就是 P vs NP 问题的核心所在：
NP完全问题（NP-Complete）
NP完全问题（NP-Complete, NPC）是NP类问题中的一个特殊子集，它们有两个重要的特性：
- 它们本身是NP类问题。
- 任何一个NP类问题都可以通过多项式时间的归约（转换）转换为这个NP完全问题。
重要性：如果你能找到一个NP完全问题的多项式时间解法，那么所有的NP问题都可以在多项式时间内解决。因此，NP完全问题是NP类问题中的“最难问题”。
典型的NP完全问题：
- 旅行商问题（TSP）：寻找一条经过每个城市恰好一次且路径最短的旅行路线。
- 3-SAT问题：判断一个布尔公式是否有解。
- 顶点覆盖问题：在一个图中找到最小的顶点集合，使得每条边至少有一个顶点被覆盖。
P vs NP问题
P vs NP问题是指：P是否等于NP？
如果 P = NP，意味着所有NP问题都有多项式时间的求解算法。这将意味着大量的难问题（如密码学中的问题）可以被快速解决。
如果 P ≠ NP，那么一些问题的解可以快速验证，但无法快速求解。
目前，这个问题尚未解决，它是 “千禧年大奖问题” 之一，美国克雷数学研究所为解决这个问题悬赏 100万美元。
总结
- P类问题：可以在多项式时间内求解。
- NP类问题：可以在多项式时间内验证解，但不一定能在多项式时间内求解。
- P vs NP问题：我们不知道所有可以快速验证的解是否也可以快速求解，即是否 $P = NP$。
9.偷偷说
本文应该囊括了修考绝大部分的考点了，当然还有双指针和滑动窗口，哈希之类的算法技巧我觉得就不用大费周章地写下来了。做修考题我认为最重要的是阅读伪代码的能力！希望这篇文章可以帮助到修考受验生们。完结撒花🎉
偷偷目前兼任私塾班主任，如果需要1对1辅导，请联系：LifeGoesOn_Rio