C++做题笔记

常用技巧/方法

查询方法find() count()

容器find() 返回值count() 返回值时间复杂度适用场景
std::set迭代器(或 end()01O(log n)有序去重集合
std::map迭代器(或 end()01O(log n)有序键值对
std::unordered_set迭代器(或 end()01平均 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);

从迭代器 firstlast 遍历,初始值为 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 作为参数更为灵活。

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇