《数据结构》C++ 代码笔记
数据结构 | 时间复杂度 | 空间复杂度 | |||||||
---|---|---|---|---|---|---|---|---|---|
情况 | 平均 | 最坏 | 最坏 | ||||||
访问 | 搜索 | 添加 | 删除 | 访问 | 搜索 | 添加 | 删除 | ||
向量 | |||||||||
列表 | |||||||||
栈/队列* | N/A | N/A | |||||||
二叉搜索树 | |||||||||
BBST | |||||||||
m 阶 B-树 | |||||||||
哈希表 | N/A | N/A |
警告
- 要求对 C++ STL 非常熟悉,否则的话请频繁查阅 CppReference.
- 个人学习笔记,自己比较熟悉的点可能没写,内容零散组织且可能有误,仅供参考。
计算模型、数据结构与算法
计算模型(Computational Model)是用于描述计算过程和计算能力的数学模型。 它定义了可以执行的操作、如何执行这些操作以及这些操作的规则。 计算模型是理解计算机科学和算法理论的基础,它帮助我们理解不同类型的计算机系统能够解决哪些问题,以及它们解决问题的效率。 图灵机(Turing Machine)是一种抽象的计算模型,可以视为一个无限长的纸带上的 状态机 。 纸带被分割成连续的单元格,每个单元格可以存储一个符号。图灵机通过一个读写头在纸带上移动\读取或写入符号,并根据当前的状态和读取的符号决定下一步操作。
《自动机理论、语言与计算》中 Hopcroft & Ullman 给出的定义
具体来说,图灵机可以定义为一个七元组
是有限的状态集合,包括特殊的起始状态 和终止状态集 . 是纸带上可能出现的符号集合,包括一个特定的空白符号 . 是输入符号集合,不包括空白符号。 是转移函数,定义了图灵机的行为。对于当前状态和读取的符号,转移函数指定图灵机应该转移到的新状态,写入的符号,以及读写头的移动方向(左 或右 )。 形式上, .
图灵机开始计算时,纸带上的所有单元格初始标记为
计算机科学中一些人的基本观点:数据结构 + 算法 = 程序。
大部分非平凡的算法问题都可以通过将问题分解为更小的平凡子问题来解决。
解决重复子问题:迭代与递归
迭代(Iteration)与递归(Recursion)是程序设计中的两类基本手段,它们都是通过反复调用某个子过程来达到求解问题的目的。 为了能够看懂一些算法描述的伪代码(或实际的代码实现),我们需要能够充分理解这两种范式。通常它们之间可以互相转化, 我们以 LeetCode 509. Fibonacci Number (求斐波那契数列的第 n 项)为例,来比较迭代与递归的区别。
int fib(int n) {
if (n <= 1) return n;
vector<int> fib(n + 1, 0);
fib[0] = 0, fib[1] = 1;
for (int i = 2; i <= n; ++i) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int fib(int n) {
if (n <= 1) return n;
vector<int> memo(n + 1, -1);
memo[0] = 0, memo[1] = 1;
function<int(int)> fib_ = [&](int n) -> int {
if (memo[n] != -1) return memo[n];
return memo[n] = fib_(n - 1) + fib_(n - 2);
};
return fib_(n);
}
int fib(int n) {
if (n <= 1) return n;
int prev_one = 1, prev_two = 0;
for (int i = 2; i <= n; ++i) {
int cur = prev_one + prev_two;
prev_two = prev_one;
prev_one = cur;
}
return prev_one;
}
可视化:迭代实现(n=5)
可视化:递归实现(n=5),递归跟踪,会发现有很多重复计算
可视化:递归 + 记忆化实现(n=5),避免重复计算
可视化:动态规划实现(n=5),适合单次查询
渐进分析
时间复杂度
, 存在正常数 和 ,使得对于所有 ,有 . , 存在正常数 和 ,使得对于所有 ,有 . , 上述情况的交集,有 .
其中
通常考察
- 忽略常系数:
. - 高阶吸收低阶:
, 其中 .
常见时间复杂度请参考 Time complexity.
在分析并界定算法的时间复杂度时,迭代式算法往往体现为级数求和的形式, 递归式算法则更多地体现为递推方程的形式,更多细节请参考《具体数学》。 对于分而治之的递归程序,通常可采用主定理(Master Theorem)来分析其时间复杂度。
复杂度分析举例:斐波那契数列递归求解与黄金分割比
对于递归版本的斐波那契算法,每一次调用递归函数,都需要分别调用两次函数本身:
其中
如果采用近似的方式,认为
证明如下(不感兴趣的读者可跳过这一部分):
已知斐波那契序列中
构造
再由数学归纳法可证出
因此有
当
均摊分析
在使用均摊分析前须知道数据结构各种操作所可能发生的时间,并计算出最坏情况下的操作情况并加以平均,得到操作的平均耗费时间。 均摊分析只能确保最坏情况性能的每次操作耗费的平均时间,并不能确认平均情况性能。 在栈和队列的操作中,均摊分析是一种常见的分析方法,插入和删除的均摊复杂度均为
抽象数据类型
抽象数据类型(Abstract Data Type, ADT)是一种数学模型,它定义了一组数据和一组操作这些数据的操作,而不关心这些操作的具体实现。 C++ STL 中的数据结构通常以容器(Container)的形式提供, 最基础的学习方法是参考 CppReference 上的文档,了解容器的基本操作和性能特点。 学有余力的话,不妨尝试手搓一遍容器的实现。
数组(Array)与向量(Vector)
数组是一种线性数据结构,它是一组连续的内存空间,用于存储相同类型的数据。 在 C++ 中,std::array
是一种固定大小的数组, 而 std::vector
是一种动态大小的数组。
这里不演示 std::array
(或 NDArray ), 以 std::vector
为主要讨论对象:
#include <vector>
vector<int> nums = {1, 2, 3, 4, 5};
nums.push_back(6); // 在末尾插入元素,nums = {1, 2, 3, 4, 5, 6}
nums.pop_back(); // 删除末尾元素,nums = {1, 2, 3, 4, 5}
nums.insert(nums.begin() + 2, 7); // 插入元素, nums = {1, 2, 7, 3, 4, 5}
nums.erase(nums.begin() + 3); // 删除元素, nums = {1, 2, 7, 4, 5}
// 以下为迭代器(Iterator),需要通过 * 操作符解引用获取元素(要求位置合法)
nums.begin(); // 返回指向第一个元素的迭代器
nums.end(); // 返回指向尾元素的下一个位置的迭代器
nums.rbegin(); // 返回指向最后一个元素的逆向迭代器
nums.rend(); // 返回指向第一个元素的前一个位置的逆向迭代器
我假定后续出现的 STL 容器,读者已经对基本操作(如 CRUD 接口)很熟悉了。
遍历并操作向量(C++20 安利)
都使用现代 C++ 啦,不要只会写 for
循环啦!(本小节单独展示 C++ 20 的魅力)
#include <ranges> // C++20 引入 ranges,其中 views 是 C++20 新增的命名空间
auto seq = views::iota(1, 10); // 生成 [1, 10) 的整数序列视图
vector<int> nums(seq.begin(), seq.end()); // 用 seq 来构造 nums
for (auto &&num : nums); // C++11 写法, && 万能引用,此时 num 是左值引用
for (auto &&num : views::iota(1, 100)); // 遍历的是右值,此时 num 是右值引用
for (auto &&num : nums | views::reverse); // 反向遍历
for (auto &&num : nums | views::drop(2)); // 丢弃前两个元素
for (auto &&num : nums | views::take(2)); // 选取前两个元素
for (auto &&num : nums | views::filter( // 对视图的操作都是惰性(Lazy)的
[](int n) { return n % 2 == 0; })); // 筛选偶数,实际遍历时才执行
可以结合一些非常有帮助的 STL 算法使用:
std::for_each
:遍历并对每个元素执行操作。std::transform
:遍历并对每个元素执行操作,将结果存储到目标位置(可以是自身)。std::accumulate
:遍历并对每个元素执行累积操作(需要提供初值)。
C++ 20 中的 std::ranges
提供了更加现代化的迭代器和范围操作:
std::vector<int> nums = {1, 2, 3, 4, 5};
auto result = nums | std::views::transform([](int n) { return n * n; })
| std::views::filter([](int n) { return n > 10; });
更多算法请参考 Constrained algorithms (since C++20).
重叠向量的拷贝
这类问题在手搓 STL 容器时经常会遇到,参考 std::copy
和 std::copy_backward
的区别。
- 若目标向量的后缀与来源向量的前缀重叠,应使用
std::copy
从前向后拷贝。 - 若目标向量的前缀与来源向量的后缀重叠,应使用
std::copy_backward
从后向前拷贝。 - 否则可能出现重叠覆写的情况,即来源向量重叠部分的数据还未拷贝,就被提前覆写。
另一类问题是将数据拷贝到初始化的内存区域,这时可以使用 std::uninitialized_copy
.
如果是移动语义,对应有 std::move
/ std::move_backward
/ std::uninitialized_move
.
这些都牵扯到对内存的操作,需要特别小心,避免内存泄漏和悬空指针等问题。
骚玩法,使用 std::copy
与 std::ostream_iterator
将向量输出到标准输出:
copy( nums.begin(), nums.end(), ostream_iterator<int>(cout, " "));
copy(nums.rbegin(), nums.rend(), ostream_iterator<int>(cout, " "));
无序向量去重
LeetCode 26. Remove Duplicates from Sorted Array 是简化版的问题,即给定一个有序的向量,要求去除其中的重复元素。通常用双指针+懒删除法解决。 我们稍微提升些难度:给定一个无序的向量,要求去除其中的重复元素,保留原有的顺序。
template<typename T>
void removeDuplicates(vector<T>& nums) {
unordered_set<T> seen;
auto last = remove_if(nums.begin(), nums.end(), [&](const T& x) {
return !seen.insert(x).second;
});
nums.erase(last, nums.end());
}
template<typename T>
void removeDuplicates(vector<T>& nums) {
auto last = unique(nums.begin(), nums.end());
nums.erase(last, nums.end());
}
int removeDuplicates(vector<int>& nums) {
if (nums.empty()) return 0;
int slow = 0;
for (int fast = 1; fast < nums.size(); ++fast) {
if (nums[slow] != nums[fast]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
int removeDuplicates(vector<int>& nums) {
return distance(nums.begin(), unique(nums.begin(), nums.end()));
}
注意 std::remove_if
是一个算法,它并不会真正删除元素,而是将满足谓词逻辑的元素移动到向量的末尾,通常需要配合 std::vector::erase
来删除这些元素。 上例用到了哈希表数据结构(std::unordered_set
)来记录已经出现的元素, 其 insert
操作返回一个 pair<iterator, bool>
,分别表示插入位置和是否插入成功。 对于本题,如果新元素为重复元素,则 insert
操作会失败,返回 false
,此时 remove_if
就会将其移动到向量末尾。
如果还没有学习到哈希表,同样可以借助排序+记录原有位置的方法来解决这个问题。
template<typename T>
void removeDuplicates(vector<T>& nums) {
// 为了保留原有的顺序,需要记录原有的位置
vector<pair<T, int>> pairs;
for (int i = 0; i < nums.size(); ++i) {
pairs.emplace_back(nums[i], i);
}
// 转换成有序向量后,再去重
sort(pairs.begin(), pairs.end());
int slow = 0;
for (int fast = 1; fast < pairs.size(); ++fast) {
if (pairs[slow].first != pairs[fast].first) {
pairs[++slow] = pairs[fast];
}
}
pairs.resize(slow + 1);
// 恢复原有的顺序
sort(pairs.begin(), pairs.end(), [](
const pair<T, int>& a, const pair<T, int>& b) {
return a.second < b.second;
});
nums.clear();
std::transform(pairs.begin(), pairs.end(),
std::back_inserter(nums),
[](const auto& pair) { return pair.first; });
}
这给我们什么启发呢,对于一些问题,我们可以把它转化为可以处理的形式,然后再解决。 尽管这样做的复杂度可能会增加,但是这样的思路往往会让问题变得更加清晰。 想要设计更加高效的算法,可能要使用更加合适的数据结构,比如哈希表等。
测试:LeetCode 442. Find All Duplicates in an Array (向量中查找重复元素)
vector<int> findDuplicates(vector<int>& nums) {
vector<int> ans;
unordered_set<int> seen;
for (int num : nums) {
if (!seen.insert(num).second) ans.push_back(num);
}
return ans;
}
vector<int> findDuplicates(vector<int>& nums) {
vector<int> ans;
for (int i = 0; i < nums.size(); ++i) {
int idx = abs(nums[i]) - 1;
if (nums[idx] < 0) ans.push_back(idx + 1);
nums[idx] = -nums[idx];
}
return ans;
}
这题的常数空间解法是一个很巧妙的解法,利用了数组元素的范围是
这种做法的局限性也是显而易见的,即只能处理正整数的情况。
有序向量查找
顺序查找(Sequential search),也叫线性查找(Linear search),不做介绍。
二分查找
以 LeetCode 704. Binary Search 为例,介绍二分查找的实现。
int search(vector<int>& nums, int target) {
int fisrt = 0, last = nums.size();
while (first < last) {
int mid = first + (last - first) / 2;
if (target < nums[mid]) last = mid;
else if (target > nums[mid]) first = mid + 1;
else return mid; // 查找成功,返回索引
}
return -1; // 查找失败,返回-1
}
template<typename T>
int binSearch(const std::vector<T>& nums, T target, int first, int last) {
while (first < last) {
int mid = first + (last - first) / 2;
if (target < nums[mid]) last = mid;
else if (target > nums[mid]) first = mid + 1;
else return mid; // 查找成功,返回索引
}
return -1; // 查找失败,返回-1
}
template<typename T>
int binSearch(const std::vector<T>& nums, T target, int first, int last) {
while (first + 1 < last) {
int mid = first + (last - first) / 2;
(target < nums[mid]) ? last = mid : first = mid;
}
return (nums[first] == target) ? first : -1;
}
template<typename T>
int binSearch(const std::vector<T>& nums, T target, int first, int last) {
while (first < last) {
int mid = first + (last - first) / 2;
(target < nums[mid]) ? last = mid : first = mid + 1;
}
return first - 1;
} // 注意这个版本的返回值与 LeetCode 704 不同
struct Fib { // 仅供作为版本 A 的改进参考
int f, g;
Fib(int n) { f = 1; g = 0; while (g < n) next(); }
int get() { return g; }
int next() { g += f; f = g - f; return g; }
int prev() { f = g - f; g -= f; return g; }
};
int fibonacciSearch(vector<int> &nums, int target, int first, int last) {
Fib fib(last - first);
while (first <= last) { // 注意这里的 [first, last] 是闭区间版本
while ((last - first) < fib.get()) { fib.prev(); }
int pos = first + fib.get();
if (target < nums[pos]) last = pos - 1;
else if (target > nums[pos]) first = pos + 1;
else return pos;
}
return -1;
}
class Solution {
public:
int search(vector<int>& nums, int target) {
return fibonacciSearch(nums, target, 0, nums.size() - 1);
}};
版本 A 到版本 B
版本 A 仅仅是简单地改成了泛型版本,但我们对于二分查找的讨论并没有停止。
版本 A 虽然易于理解,但使用的比较分支过多,直接导致了查找长度的不均衡,在常数意义上影响到了平均查找长度。 如果目标元素在数组末尾,那么每次都需要进行两次比较,导致其查找长度会是最长的。解决这种不均衡有两种思路:
- 不使用二分查找,而使用 Fibonacci 查找进行划分,用区间长度来平衡查找长度。
- 减少分支的个数,将命中的情况也归入到一个分支中,这样平均性能会更好,即版本 B.
版本 B 的实现即使命中了目标元素,也会继续缩短区间查找,直到区间长度为 1.
版本 B 到版本 C
按照常见的语义约定,查找的返回结果要么为 bool
类型,表示是否找到,参考 std::binary_search
; 要么是使用迭代器作为返回值,表示找到的位置。对于二分查找,我们需要考虑不含目标元素、含有多个目标元素的情况, 假设此时要求要返回值不超过目标元素的最后一个元素(秩最大者)的位置,则为版本 C 的实现。
以后想要调用这个接口插入新元素并依旧保持有序,只需要:
int idx = binSearch(nums, target, 0, nums.size());
nums.insert(nums.begin() + idx + 1, target);
例如将这个应用于 LeetCode 704,只需要如下调用:
int search(vector<int>& nums, int target) {
int idx = binSearch(nums, target, 0, nums.size());
return (idx != -1 && nums[idx] == target) ? idx : -1;
}};
为什么约定返回 1.值不超过目标元素 2.最后一个(秩最大者)的位置?
这是结合了后续的插入操作,组成 insert(search(target) + 1)
形式来考虑的:
std::vector::insert
的接口是在指定位置插入元素,当前以及后续元素依次后移;- 为了保证有序性,需要将目标元素插入到第一个大于等于其值的位置;
- 但考虑到可能存在多个相同的元素,为了减少移动次数,选择最后一个元素的位置。
考虑如下情景, 1 222222(非常多个...)22222 3 为有序序列, 2 是待插入的目标元素,我们希望将其插入到 3 的前面, 如果只要求满足有序性而不考虑移动次数,那么我们可以选择第一个 2 的位置,但这样会导致后续的元素移动次数过多。
实际上在 STL 中,更常见的是使用 std::upper_bound
来查找插入位置, 其含义其实就是返回第一个大于目标元素的位置,等同于我们的版本 C 的结果 + 1.
auto pos = upper_bound(nums.begin(), nums.end(), target);
nums.insert(pos, target);
很多时候自己手写二分查找真的很容易混淆边界条件, 因此最好熟悉 std::lower_bound
和 std::upper_bound
的用法,它们分别返回第一个大于等于和第一个大于目标元素的位置。 以 LeetCode 34. Find First and Last Position of Element in Sorted Array 为例:
// Rank = 0 1 2 3 4 5 6 7 8
vector<int> nums = {1, 1, 1, 2, 2, 2, 3, 3, 3} // Ascending
lower_bound(nums.begin(), nums.end(), 2); // Rank = 3
upper_bound(nums.begin(), nums.end(), 2); // Rank = 6
upper_bound(nums.begin(), nums.end(), 2) - 1; // the last 2, Rank = 5
// Rank = 0 1 2 3 4 5 6 7 8
vector<int> nums = {3, 3, 3, 2, 2, 2, 1, 1, 1} // Descending
lower_bound(nums.begin(), nums.end(), 2, greater<int>()); // Rank = 3
upper_bound(nums.begin(), nums.end(), 2, greater<int>()); // Rank = 6
vector<int> searchRange(vector<int>& nums, int target) {
auto first = lower_bound(nums.begin(), nums.end(), target);
auto last = upper_bound(nums.begin(), nums.end(), target);
if (first == last) return {-1, -1};
return {
static_cast<int>(first - nums.begin()),
static_cast<int>(last - nums.begin() - 1)
};
}
static int binarySearchFirst(
vector<int>& nums, int target, int left, int right) {
int l = left, r = right;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
if (left <= r && nums[left] == target) return left;
return -1;
}
static int binarySearchLast(
vector<int>& nums, int target, int left, int right) {
int l = left, r = right;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) left = mid + 1;
else right = mid - 1;
}
if (right >= l && nums[right] == target) return right;
return -1;
}
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
return {binarySearchFirst(nums, target, left, right),
binarySearchLast(nums, target, left, right)};
}
};
但实际工程项目很多数据结构是自己撸的,所以也不要完全认为一切都能用 STL 解决。
插值查找
插值查找的思想是根据目标元素的值,按比例估算其在有序数组中的位置。
int interpolationSearch(vector<int>& nums, int target, int first, int last) {
while (first < last) {
int pivot = first + (last - first) * (target - nums[first]) /
(nums[last] - nums[first]);
if (nums[pivot] < target) first = pivot + 1;
else if (nums[pivot] > target) last = pivot - 1;
else return pivot;
}
return nums[first] == target ? first : -1;
}
位图(Bitset)
值得注意的是,由于历史原因 std::vector<bool>
是一个特化的 std::vector
,它并不是一个容器,而是一个动态的位集合(Bitset)。 如果大小在编译时就已知,建议使用 std::bitset
代替。 二者的接口略有不同,std::bitset
通常更加高效。
举例:LeetCode 204. Count Primes (统计小于 的质数个数)
可以使用 Eratosthenes 筛法(Sieve of Eratosthenes)来解决这个问题,
int countPrimes(int n) {
vector<bool> isPrime(n, true);
int count = 0;
for (int i = 2; i < n; ++i) {
if (isPrime[i]) {
++count;
if ((long long)i * i >= n) continue;
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
return count;
}
如果想要更高效的解法,需要用到 Min_25 筛等,偏 OI 向,不在目前的讨论范围内。
信息
通常在讲解完序列容器后,会讲解部分排序算法,我将它们统一整理在了后面。
LeetCode 练习精选
- LeetCode 493. Reverse Pairs
- LeetCode 565. Array Nesting
- LeetCode 442. Find All Duplicates in an Array
- LeetCode 166. Fraction to Recurring Decimal
列表(List)
- LeetCode 21. Merge Two Sorted Lists
- LeetCode 2. Add Two Numbers
- LeetCode 237. Delete Node in a Linked List
- LeetCode 203. Remove Linked List Elements
- LeetCode 19. Remove Nth Node From End of List
- LeetCode 24. Swap Nodes in Pairs
- LeetCode 206. Reverse Linked List
- LeetCode 92. Reverse Linked List II
- LeetCode 25. Reverse Nodes in k-Group
- LeetCode 61. Rotate List
- LeetCode 83. Remove Duplicates from Sorted List
- LeetCode 707. Design Linked List
- LeetCode 1206. Design Skiplist
栈(Stack)与队列(Queue)
双端队列(Deque)
单调栈(Monotonic Stack)
- LeetCode 739. Daily Temperatures
- LeetCode 496. Next Greater Element I
- LeetCode 503. Next Greater Element II
- LeetCode 84. Largest Rectangle in Histogram
循环队列(Circular Queue)
LeetCode 练习精选
- LeetCode 504. Base 7
- LeetCode 20. Valid Parentheses
- LeetCode 946. Validate Stack Sequences
- LeetCode 150. Evaluate Reverse Polish Notation
- LeetCode 224. Basic Calculator
- LeetCode 51. N-Queens
数据结构实现:
- LeetCode 155. Min Stack
- LeetCode 232. Implement Queue using Stacks
- LeetCode 225. Implement Stack using Queues
- LeetCode 622. Design Circular Queue
- LeetCode 641. Design Circular Deque
树(Tree)
二叉树(Binary Tree)
遍历:
- LeetCode 144. Binary Tree Preorder Traversal
- LeetCode 94. Binary Tree Inorder Traversal
- LeetCode 145. Binary Tree Postorder Traversal
- LeetCode 102. Binary Tree Level Order Traversal
- LeetCode 103. Binary Tree Zigzag Level Order Traversal
其它:
- LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal
- LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal
- LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal
- LeetCode 226. Invert Binary Tree
- LeetCode 617. Merge Two Binary Trees
- LeetCode 297. Serialize and Deserialize Binary Tree
- LeetCode 654. Maximum Binary Tree
- LeetCode 104. Maximum Depth of Binary Tree
- LeetCode 111. Minimum Depth of Binary Tree
- LeetCode 543. Diameter of Binary Tree
- LeetCode 222. Count Complete Tree Nodes
- LeetCode 236. Lowest Common Ancestor of a Binary Tree
- LeetCode 1483. Kth Ancestor of a Tree Node
- LeetCode 110. Balanced Binary Tree
- LeetCode 257. Binary Tree Paths
- LeetCode 112. Path Sum
- LeetCode 113. Path Sum II
N 叉树(N-ary Tree)
- LeetCode 589. N-ary Tree Preorder Traversal
- LeetCode 590. N-ary Tree Postorder Traversal
- LeetCode 429. N-ary Tree Level Order Traversal
- LeetCode 559. Maximum Depth of N-ary Tree
- LeetCode 428. Serialize and Deserialize N-ary Tree
- LeetCode 1506. Find Root of N-Ary Tree
二叉搜索树(Binary Search Tree)
- LeetCode 98. Validate Binary Search Tree
- LeetCode 783. Minimum Distance Between BST Nodes
- LeetCode 700. Search in a Binary Search Tree
- LeetCode 701. Insert into a Binary Search Tree
- LeetCode 450. Delete Node in a BST
- LeetCode 669. Trim a Binary Search Tree
- LeetCode 108. Convert Sorted Array to Binary Search Tree
- LeetCode 109. Convert Sorted List to Binary Search Tree
- LeetCode 1008. Construct Binary Search Tree from Preorder Traversal
- LeetCode 538. Convert BST to Greater Tree
- LeetCode 230. Kth Smallest Element in a BST
- LeetCode 235. Lowest Common Ancestor of a Binary Search Tree
- LeetCode 501. Find Mode in Binary Search Tree
- LeetCode 938. Range Sum of BST
- LeetCode 1382. Balance a Binary Search Tree
自平衡二叉搜索树(BBST)
TODO
哈希表(Hash Table)
- LeetCode 1. Two Sum
- LeetCode 609. Find Duplicate File in System
- LeetCode 138. Copy List with Random Pointer
- LeetCode 705. Design HashSet
- LeetCode 706. Design HashMap
堆(Heap)与优先队列(Priority Queue)
- LeetCode 215. Kth Largest Element in an Array
- LeetCode 703. Kth Largest Element in a Stream
- LeetCode 347. Top K Frequent Elements
- LeetCode 295. Find Median from Data Stream
- LeetCode 23. Merge k Sorted Lists
- LeetCode 373. Find K Pairs with Smallest Sums
- LeetCode 264. Ugly Number II
- LeetCode 313. Super Ugly Number
- LeetCode 378. Kth Smallest Element in a Sorted Matrix
- LeetCode 632. Smallest Range Covering Elements from K Lists
图(Graph)
最小生成树问题
最短路径问题
拓扑排序
连通性问题
二分图匹配
最大流问题
字符串(String)
模式匹配
常见排序算法(Sorting Algorithms)
以 LeetCode 912. Sort an Array 为例,但下面实现的算法是支持泛型的:
bubbleSort(nums.begin(), nums.end()); // 提供相应 RandomAccessIterator 即可
你需要了解 C++ STL 中各种迭代器(Iterator)的概念和使用方法, 待排序区间通常以 [first, last)
表示,由于采取了减治或分治策略,排序过程中将可能发生 first
和 last
迭代器失效, 即 first
不永远指向原序列的 begin()
位置,last
不永远指向 end()
.
RandomAccessIterator 和 BidirectionalIterator 的区别
简单来说就是前者保证了常数时间内的随机访问如 iter+=n
,后者仅仅支持双向访问如 iter++
和 iter--
. 这个在树形结构中对比很明显,比如红黑树,我们的算法依然可以适配,但迭代器的移动效率会有所下降。 可以参考 std::bidirectional_iterator
.
这样我们可以专注于算法的实现,而不用关心具体的数据类型,这也是泛型编程的魅力所在。
冒泡排序(Bubble Sort)
在
template<typename RandomAccessIterator>
void bubbleSort(RandomAccessIterator first, RandomAccessIterator last) {
for (; first < last; --last) {
for (auto cur = first; cur + 1 < last; ++cur) {
auto next = cur + 1;
if (*cur > *next) iter_swap(cur, next);
} // 单向地,将待排序区间的极大值冒泡到最右侧
}
}
template<typename RandomAccessIterator>
void bubbleSort(RandomAccessIterator first, RandomAccessIterator last) {
for (; first < last; --last) {
bool swapped = false; // 标记此轮是否发生交换
for (auto cur = first; cur + 1 < last; ++cur) {
auto next = cur + 1;
if (*cur > *next) {
iter_swap(cur, next);
swapped = true;
}
}
if (!swapped) break; // 如果没有发生交换,则说明已经有序
}
}
template<typename RandomAccessIterator>
void bubbleSort(RandomAccessIterator first, RandomAccessIterator last) {
while (first < last) {
auto lastSwap = first; // 记录最后一次交换的位置
for (auto cur = first; cur + 1 < last; ++cur) {
auto next = cur + 1;
if (*cur > *next) {
iter_swap(cur, next);
lastSwap = next;
}
}
last = lastSwap; // 充分利用每趟的交换信息
}
}
template<typename RandomAccessIterator>
void bubbleSort(RandomAccessIterator first, RandomAccessIterator last) {
while (first < last) {
// 从左向右冒泡,将最大值冒泡到右侧
auto lastSwap = first;
for (auto cur = first; cur + 1 < last; ++cur) {
auto next = cur + 1;
if (*cur > *next) {
iter_swap(cur, next);
lastSwap = next;
}
}
last = lastSwap;
// 从右向左冒泡,将最小值冒泡到左侧
auto firstSwap = last;
for (auto cur = last; cur > first; --cur) {
auto prev = cur - 1;
if (*prev > *cur) {
iter_swap(prev, cur);
firstSwap = prev;
}
}
first = firstSwap;
}
}
在冒泡的过程中,除了当前待排序区间的极值元素外,其它元素的交换操作可能是多余的。
选择排序(Selection Sort)
在
template<typename RandomAccessIterator>
void selectionSort(RandomAccessIterator first, RandomAccessIterator last) {
while (first < last) {
auto maxIter = first;
for (auto cur = first; cur < last; ++cur) {
if (*cur > *maxIter) maxIter = cur; // 不做交换,只记录最大值位置
}
iter_swap(maxIter, --last); // 交换最大值到待排序区间的末尾
}
}
template<typename RandomAccessIterator>
void selectionSort(RandomAccessIterator first, RandomAccessIterator last) {
while (first < last) {
auto maxIter = max_element(first, last); // 使用 STL 算法
iter_swap(maxIter, --last);
}
}
单次迭代后的始终态和冒泡排序是一样的,但选择排序的交换次数要少于冒泡排序。
插入排序(Insertion Sort)
在
template<typename RandomAccessIterator>
void insertionSort(RandomAccessIterator first, RandomAccessIterator last) {
for (auto cur = first + 1; cur != last; ++cur) { // [first, cur) 已排序
auto key = *cur;
auto pos = cur;
for (; pos != first && *(pos - 1) > key; --pos) { // 查找插入位置
*pos = *(pos - 1); // 移动元素(实际上是拷贝赋值)
}
*pos = key; // 插入元素(实际上是拷贝赋值)
}
}
template<typename RandomAccessIterator>
void insertionSort(RandomAccessIterator first, RandomAccessIterator last) {
for (auto cur = first + 1; cur != last; ++cur) { // [first, cur) 已排序
auto key = move(*cur);
auto pos = cur;
for (; pos != first && *(pos - 1) > key; --pos) { // 查找插入位置
*pos = move(*(pos - 1)); // 移动元素
}
*pos = move(key); // 插入元素
}
}
template<typename RandomAccessIterator>
void insertionSort(RandomAccessIterator first, RandomAccessIterator last) {
for (auto cur = first + 1; cur != last; ++cur) { // [first, cur) 已排序
auto key = move(*cur);
auto pos = upper_bound(first, cur, key); // 查找插入位置
rotate(pos, cur, cur + 1); // 移动 + 插入元素
}
}
如果是为了算法演示,可以假设元素都是基本类型,直接拷贝赋值即可。
归并排序(Merge Sort)
归并排序是一种分治算法,将待排序区间均分成两部分,分别归并排序后再合并。
练手:LeetCode 21. Merge Two Sorted Lists (合并两个有序链表)
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0), *tail = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
练手:LeetCode 88. Merge Sorted Array (合并两个有序数组)
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
move(nums2.begin(), nums2.end(), nums1.begin() + m);
inplace_merge(nums1.begin(), nums1.begin() + m, nums1.end());
}
template<typename RandomAccessIterator>
void mergeSort(RandomAccessIterator first, RandomAccessIterator last) {
if (last - first < 2) return;
auto mid = first + (last - first) / 2;
mergeSort(first, mid);
mergeSort(mid, last);
vector<typename RandomAccessIterator::value_type> tmp(last - first);
auto l = first, r = mid, t = tmp.begin();
while (l < mid && r < last) {
if (*l < *r) *t++ = move(*l++);
else *t++ = move(*r++);
}
t = move(l, mid, t); // [l, mid) 有剩余时
t = move(r, last, t); // [r, last) 有剩余时
move(tmp.begin(), tmp.end(), first);
}
template<typename RandomAccessIterator>
void mergeSort(RandomAccessIterator first, RandomAccessIterator last) {
if (last - first < 2) return;
auto mid = first + (last - first) / 2;
mergeSort(first, mid);
mergeSort(mid, last);
inplace_merge(first, mid, last);
}
template<typename RandomAccessIterator>
void mergeSort(RandomAccessIterator first, RandomAccessIterator last) {
auto n = last - first;
for (decltype(n) step = 1; step < n; step *= 2) {
for (auto begin = first; begin < last; begin += 2 * step) {
auto mid = min(begin + step, last);
auto end = min(begin + step * 2, last);
inplace_merge(begin, mid, end);
}
}
}