常用技巧/方法
查询方法find() count()
容器 | find() 返回值 | count() 返回值 | 时间复杂度 | 适用场景 |
---|---|---|---|---|
std::set | 迭代器(或 end() ) | 0 或 1 | O(log n) | 有序去重集合 |
std::map | 迭代器(或 end() ) | 0 或 1 | O(log n) | 有序键值对 |
std::unordered_set | 迭代器(或 end() ) | 0 或 1 | 平均 O(1) | 快速哈希查找 |
std::vector | 迭代器(或 end() ) | 出现次数 | O(n) | 线性搜索 |
std::multiset | 第一个匹配的迭代器 | 出现次数 | O(log n) | 允许重复的有序集合 |
- vector 是顺序容器,存储方式为连续内存,未内置快速查找算法。
- set/map 是关联容器,基于红黑树(或哈希表)实现,天然支持高效查找(O(log n) 或 O(1)),因此提供了.find() 成员方法。
也就是说,vector使用find方法:
std::vector v = {1, 2, 3};
auto it = std::find(v.begin(), v.end(), 2); // 全局函数
set等关联容器使用find方法:
std::set s = {1, 2, 3};
auto it = s.find(2); // O(log n),利用红黑树特性
count方法与find方法同理
std::accumulate()求和函数
原型:
// 基本形式,使用 operator+ 进行累加
template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init);
// 带自定义二元运算的版本
template<class InputIt, class T, class BinaryOperation>
T accumulate(InputIt first, InputIt last, T init, BinaryOperation op);
从迭代器 first
到 last
遍历,初始值为 init
,默认使用加法(即 operator+
)将每个元素与累加值结合。如果提供了自定义的 op
,则用该运算符进行操作。
#include <iostream>
#include <vector>
#include <numeric> // std::accumulate
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 使用 std::accumulate 计算总和,初始值为 0
int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
std::cout << "总和为: " << sum << std::endl; // 输出 15
return 0;
}
位运算
整数通常以二进制形式存储。位运算就是对这些二进制位逐位进行操作,可以实现高效且底层的数值处理。
按位与(&)
对应位都为 1 时结果才为 1,否则为 0。
示例:
- 二进制:
0101 & 0011 = 0001
- 十进制:
5 & 3 = 1
按位或(|)
对应位只要有一个为 1,结果即为 1。
示例:
- 二进制:
0101 | 0011 = 0111
- 十进制:
5 | 3 = 7
按位异或(^)
对应位相同为 0,不同为 1。
示例:
- 二进制:
0101 ^ 0011 = 0110
- 十进制:
5 ^ 3 = 6
按位取反(~)
将每一位取反(0 变 1,1 变 0)。需要注意的是,取反操作符在有符号整数上通常会返回一个负值,这是因为 C++ 使用补码来表示负数。
示例:
- ~5 的结果在 32 位系统下通常为
-6
(因为 ~5 = -(5+1))。
左移运算符(<<)
将二进制位向左移动指定的位数,右侧补零。左移相当于乘以 2 的指定次幂。
示例:
5 << 1
将 5(二进制 0101)左移一位变为 1010,即十进制的 10。
右移运算符(>>)
将二进制位向右移动指定的位数。对于无符号数,左侧补 0;对于有符号数,不同编译器可能执行算术右移(保留符号位)或逻辑右移。
示例:
5 >> 1
将 5(二进制 0101)右移一位变为 0010,即十进制的 2。
深度搜索的C++代码实现
不重点探讨深搜算法,而注重探讨深搜算法用C++代码的实现方式
这是一个遍历矩形所有节点的代码
int n, m; // 矩形的行数和列数
vector<vector<bool>> visited; // 记录每个单元格是否已被访问
// DFS 递归函数,(x, y) 为当前访问的单元格坐标
void dfs(int x, int y) {
// 1. 边界检查:如果超出矩形范围则返回
if (x < 0 || x >= n || y < 0 || y >= m)
return;
// 2. 如果当前单元格已经访问过,则直接返回
if (visited[x][y])
return;
// 3. 标记当前单元格为已访问
visited[x][y] = true;
// 4. 在此可以对当前单元格进行处理,这里简单输出坐标
cout << "(" << x << ", " << y << ") ";
// 5. 递归访问当前单元格的相邻单元格(上下左右)
dfs(x - 1, y); // 向上
dfs(x + 1, y); // 向下
dfs(x, y - 1); // 向左
dfs(x, y + 1); // 向右
}
似乎,DFS只需要下面这三步:
递归终止条件:当节点或坐标超出范围或已经被访问时立即返回。
状态标记:确保遍历不会重复进入已处理的部分。
递归调用:对所有可能的下一步进行递归探索。
如果要记录DFS的路径,得加两步:
在递归开始时将当前节点/坐标添加到路径记录中;
在递归结束(即返回上层调用)前将当前元素从路径中移除(回溯操作);
int n, m; // 网格的行数和列数
vector<vector<bool>> visited; // 记录每个格子是否已访问
vector<pair<int, int>> path; // 当前 DFS 路径,记录 (x, y) 坐标
// DFS 递归函数,(x, y) 为当前访问的格子坐标
void dfs(int x, int y) {
// 1. 边界检查:如果超出网格范围,返回
if (x < 0 || x >= n || y < 0 || y >= m)
return;
// 2. 如果该格子已访问,返回
if (visited[x][y])
return;
// 3. 标记格子已访问,添加到路径记录中
visited[x][y] = true;
path.push_back({x, y});
// 4. 处理当前路径:此处输出当前路径
cout << "当前路径: ";
for (auto &p : path)
cout << "(" << p.first << "," << p.second << ") ";
cout << endl;
// 5. 对四个方向进行递归调用(上、下、左、右)
dfs(x - 1, y); // 向上
dfs(x + 1, y); // 向下
dfs(x, y - 1); // 向左
dfs(x, y + 1); // 向右
// 6. 回溯:移除当前格子,恢复状态
path.pop_back();
}
在DFS中如何管理 visited 数组(已访问数组),该作为全局变量还是作为DFS的一个参数传入?
将 visited 作为全局变量(或外部变量):
遍历整个图或树:当你只需要遍历每个节点一次,目的是防止重复访问(如查找连通分量、检测环路等),整个搜索过程中所有递归调用共享同一状态,这时将 visited 声明在函数外部或作为全局变量是非常自然且高效的。
状态唯一性:你希望整个图的访问状态是统一的,也就是说,一旦一个节点被访问过,就在所有后续递归中保持已访问状态,不需要针对每个路径分开记录。
简化参数传递:如果不需要在递归过程中回退“访问”的状态,这样设计能够减少参数传递,并使代码更简洁。
将 visited 作为递归函数的参数
需要维护局部状态或回溯:在一些问题中(如求解迷宫、全路径搜索、组合问题等),你希望每个递归调用都能独立决定“此时此刻”的访问状态,递归返回后能够回退已做的状态修改。传入 visited 参数可以让你在每条路径中独立管理访问记录,并在返回前“撤销”访问标记。
函数纯粹性和可重入性:如果你希望 DFS 函数成为一个纯函数,即输出仅依赖于输入参数而不是全局状态,那么把 visited 作为参数传入是更好的选择。这样可以减少副作用,方便调试和单元测试。
多条路径分叉独立性:当有多个可能路径并行搜索时,某个节点在不同的路径上其“访问状态”可能不同,此时不能使用唯一的全局 visited,而应在每个递归调用中传递独立的或经过适当修改的 visited 副本。
这里的“每个递归调用都能独立决定“此时此刻”的访问状态,递归返回后能够回退已做的状态修改”比较难以理解,举个例子:
void dfs(int i, int j, vector<vector<bool>> &visited, vector<pair<int,int>> &path) {
// 检查边界
if (i < 0 || i >= rows || j < 0 || j >= cols)
return;
// 如果已访问或当前位置不可通行(0),直接返回
if (visited[i][j] || grid[i][j] == 0)
return;
// 标记访问并加入路径
visited[i][j] = true;
path.push_back({i, j});
// 到达终点则输出当前路径
if (i == rows - 1 && j == cols - 1) {
cout << "找到路径:";
for (auto &p : path) {
cout << "(" << p.first << "," << p.second << ") ";
}
cout << endl;
} else {
// 定义四个方向移动的偏移量:下、上、右、左
int di[4] = {1, -1, 0, 0};
int dj[4] = {0, 0, 1, -1};
for (int k = 0; k < 4; k++) {
dfs(i + di[k], j + dj[k], visited, path);
}
}
// 回溯:撤销当前访问状态和路径记录
path.pop_back();
visited[i][j] = false;
}
总而言之:大多数情况是要考虑该DFS是否需要寻找探索所有可能的情况,当问题只需一次遍历时,使用全局 visited
数组更简单直接;而在需要探索所有可能情况并回溯的场景下,传递 visited
作为参数更为灵活。