常用技巧/方法

查询方法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 作为参数更为灵活。