C++ 练习册第 11 章算法思想入门

📝 本章练习：40 题（A 识别 / B 理解 / C 改错 / D 写程序）。先自己做完再看答案——A、B 档不翻书做，C、D 档必须真的编译运行。

11.1 双指针

A1识别判断题：在“有序数组里找两个数，使和等于 target”这类问题中，用相向双指针（左端+右端往中间走）可以把复杂度从 O(n^2) 降到 O(n)。

答：______________

✅ 查看答案与解析

答案　对

解析：因为数组有序：和太大就右指针左移，和太小就左指针右移，每个指针最多走 n 步。

B1理解选择题：相向双指针判断回文时，两指针相遇（或交错）后应该怎么做？

继续走

结束判断，返回 true

返回 false

重新开始

答：______________

✅ 查看答案与解析

答案　B

解析：所有字符都对称匹配，说明是回文，返回 true。

C1应用改错题：下面两数之和双指针实现有一处边界/方向错误。

// nums 已升序，找和为 target 的两个下标
int l = 0, r = (int)nums.size() - 1;
while (l < r) {
    int s = nums[l] + nums[r];
    if (s == target) { return {l, r}; }
    else if (s < target) { --r; }   // 错误：和太小应该让左指针右移
    else { ++l; }
}

✅ 查看答案与解析

答案　和太小 → ++l（左指针右移让和变大）；和太大 → --r。改：

解析：左指针右移和变大，右指针左移和变小——方向搞反就是死循环或漏解。

    if (s < target) { ++l; }
    else { --r; }

D1创造写程序：读入升序数组和一个 target，用相向双指针输出两个和为 target 的下标（保证存在一组解）。

提示：while (l < r)：和等于 target 直接输出；小于则 ++l；大于则 --r。

✅ 查看答案与解析

答案　参考答案：

解析：双指针利用有序性，一趟 O(n) 搞定。

#include <iostream>
#include <vector>
int main() {
    int n, target;
    std::cin >> n >> target;
    std::vector<int> nums(n);
    for (int i = 0; i < n; ++i) { std::cin >> nums[i]; }
    int l = 0, r = n - 1;
    while (l < r) {
        int s = nums[l] + nums[r];
        if (s == target) { std::cout << l << ' ' << r << '\n'; return 0; }
        if (s < target) { ++l; } else { --r; }
    }
    return 0;
}

11.2 滑动窗口

A1识别判断题：滑动窗口专门解决“连续子区间”问题，右端扩张、左端收缩，复杂度 O(n)。

答：______________

✅ 查看答案与解析

答案　对

解析：每个元素最多被右指针加入一次、被左指针移出一次，所以是 O(n)。

B1理解选择题：求“和无超过 target 的最短连续子数组”适合用什么？

暴力三重循环

滑动窗口（右端扩张，和超了左端收缩）

排序

深度优先搜索

答：______________

✅ 查看答案与解析

答案　B

解析：连续区间 + 窗口单调扩张收缩 = 滑动窗口的典型场景。

C1应用改错题：下面滑动窗口求“和无超过 target 的最短长度”，收缩方向写反了。

int l = 0, sum = 0, ans = n + 1;
for (int r = 0; r < n; ++r) {
    sum += a[r];
    while (sum > target && l <= r) {
        ans = std::min(ans, r - l + 1);
        sum -= a[l];
        ++l;
    }
}
// 问题：ans 在收缩时才更新，最短窗口可能没被记录

✅ 查看答案与解析

答案　合法窗口（sum <= target）出现时就更新答案，收缩是为了继续找更短的：

解析：先收缩到合法，再记录长度；收缩与更新顺序错了就会漏解。

while (sum > target && l <= r) { sum -= a[l]; ++l; }
if (sum <= target) { ans = std::min(ans, r - l + 1); }

D1创造写程序：给一个字符串，用滑动窗口输出“最长无重复字符子串”的长度。

提示：用数组 cnt[256] 记录窗口内字符出现次数；出现重复就收缩左指针。

✅ 查看答案与解析

答案　参考答案：

解析：窗口内字符不重复时，随时更新答案；有重复就左指针收缩到不重复为止。

#include <iostream>
#include <string>
#include <vector>
int main() {
    std::string s;
    std::cin >> s;
    std::vector<int> cnt(256, 0);
    int l = 0, ans = 0;
    for (int r = 0; r < (int)s.size(); ++r) {
        ++cnt[(unsigned char)s[r]];
        while (cnt[(unsigned char)s[r]] > 1) {   // 出现重复，收缩
            --cnt[(unsigned char)s[l]];
            ++l;
        }
        ans = std::max(ans, r - l + 1);
    }
    std::cout << ans << '\n';
    return 0;
}

11.3 哈希表

A1识别判断题：unordered_map 的查找是平均 O(1)（哈希），而 map 是 O(log n)（红黑树）。

答：______________

✅ 查看答案与解析

答案　对

解析：unordered_map 底层哈希表，平均 O(1)；map 底层红黑树，保证 O(log n)。

B1理解选择题：用哈希做“两数之和”的核心思路是？

双重循环暴力比较

遍历时查“target - 当前数”是否已出现过

先排序再取首尾

用 map 存所有数的平方

答：______________

✅ 查看答案与解析

答案　B

解析：边遍历边把数存进哈希表，对每个数查它的“补数”在不在表里——一趟 O(n)。

C1应用改错题：下面用 unordered_map 统计字符频率，但查询写法会误插入脏数据。

std::unordered_map<char, int> freq;
std::string s = "abca";
for (char c : s) { ++freq[c]; }
if (freq['z'] > 0) { std::cout << "z exists\n"; }   // 误插入了 {z:0}！

✅ 查看答案与解析

答案　if (freq.count('z') > 0) { std::cout << "z exists\n"; }

解析：operator[] 查询不存在的键会插入默认值；判断存在用 count/find。统计频率时 ++freq[c] 本身是安全的。

D1创造写程序：读入若干整数，用 unordered_map 统计每个数出现次数，输出出现次数最多的数。

提示：遍历时维护 maxCnt 和答案变量。

✅ 查看答案与解析

答案　参考答案：

解析：哈希计数一趟 O(n)；维护最大值时顺手记下对应的数。

#include <iostream>
#include <unordered_map>
int main() {
    int n;
    std::cin >> n;
    std::unordered_map<int, int> freq;
    int best = 0, bestCnt = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        int c = ++freq[x];
        if (c > bestCnt) { bestCnt = c; best = x; }
    }
    std::cout << best << '\n';
    return 0;
}

11.4 前缀和

A1识别判断题：前缀和预处理 O(n)，之后每次区间求和都是 O(1)。

答：______________

✅ 查看答案与解析

答案　对

解析：把“每次都重算”变成“一次算好、相减即得”，这是用空间换时间。

B1理解选择题：pre[r+1] - pre[l] 求的是数组的哪一段的和？

a[0..r] 的和

a[l..r] 的和

a[l+1..r+1] 的和

a[l..r] 的个数

答：______________

✅ 查看答案与解析

答案　B

解析：pre[i] = a[0]+...+a[i-1]（前 i 个）。所以 pre[r+1]-pre[l] = a[l]+...+a[r]。

C1应用改错题：下面前缀和构建有下标错位。

std::vector<long long> pre(n, 0);   // 长度应该是 n+1
for (int i = 0; i < n; ++i) { pre[i + 1] = pre[i] + a[i]; }  // 越界写！

✅ 查看答案与解析

答案　std::vector<long long> pre(n + 1, 0);

解析：pre 需要 n+1 个位置（pre[0]=0 到 pre[n]）。长度写 n 就会越界。

for (int i = 0; i < n; ++i) { pre[i + 1] = pre[i] + a[i]; }

D1创造写程序：读入 n 个数，再读 q 组询问 (l, r)，每次输出 a[l..r] 的和（下标从 0 开始）。

提示：先建 pre[n+1]，每组询问输出 pre[r+1] - pre[l]。

✅ 查看答案与解析

答案　参考答案：

解析：区间和 = pre[r+1] - pre[l]，记得用 long long 防溢出。

#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        pre[i + 1] = pre[i] + a[i];
    }
    int q;
    std::cin >> q;
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << pre[r + 1] - pre[l] << '\n';
    }
    return 0;
}

11.5 二分查找

A1识别判断题：二分查找要求数据有序（或答案具有单调性）。

答：______________

✅ 查看答案与解析

答案　对

解析：只有单调才能根据中间值决定向左还是向右。

B1理解选择题：写 mid = left + (right - left) / 2 而不是 mid = (left + right) / 2，是为了？

代码更短

避免 left + right 溢出

让 mid 偏右

没有区别，纯习惯

答：______________

✅ 查看答案与解析

答案　B

解析：left + right 可能溢出 int；先减后加不会。

C1应用改错题：下面二分求“第一个 >= x 的下标”，左边界更新写错会死循环或答案错误。

int l = 0, r = n;   // 注意 r 初始为 n（开区间）
while (l < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] >= x) { l = mid; }   // 错误：满足条件应该收缩右边界
    else { r = mid + 1; }
}

✅ 查看答案与解析

答案　满足条件时 mid 可能是答案，右边界收到 mid：

解析：“找第一个 >= x”模板：a[mid] >= x 说明答案在 [l, mid]，令 r = mid；否则答案在 (mid, r)，令 l = mid + 1。

    if (a[mid] >= x) { r = mid; }
    else { l = mid + 1; }

D1创造写程序：在升序数组里用二分找“第一个 >= x 的元素下标”，没有则输出 -1。

提示：标准模板 while (l < r) + r = mid / l = mid + 1。

✅ 查看答案与解析

答案　参考答案：

解析：这个模板就是 std::lower_bound 的手写版，务必背熟。

#include <iostream>
#include <vector>
int main() {
    int n, x;
    std::cin >> n >> x;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) { std::cin >> a[i]; }
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) { r = mid; } else { l = mid + 1; }
    }
    if (l < n) { std::cout << l << '\n'; } else { std::cout << -1 << '\n'; }
    return 0;
}

11.6 深度优先搜索 DFS

A1识别判断题：DFS 在图/网格上搜索时必须标记已访问，否则会死循环。

答：______________

✅ 查看答案与解析

答案　对

解析：不标记的话，A→B→A→B…永远走不完。标记后每个点只访问一次。

B1理解选择题：下面哪个是 DFS 的典型特征？

用队列逐层扩展

一条路走到底，走不通再回头（递归+回溯）

每次取当前最优

随机跳转

答：______________

✅ 查看答案与解析

答案　B

解析：DFS 深度优先：一条路走到底，撞墙回溯。BFS 才用队列逐层扩展。

C1应用改错题：下面 DFS 缺少终止条件，会无限递归。

void dfs(int x) {
    dfs(x + 1);   // 永远不返回，栈溢出
}

✅ 查看答案与解析

答案　加终止条件：

解析：递归必须有个“到底了”的出口，否则无限递归栈溢出。

void dfs(int x) {
    if (x > 10) { return; }   // 边界
    dfs(x + 1);
}

D1创造写程序：给定 n×m 的 0/1 网格（1 是陆地），用 DFS 统计有多少个“连通块”（上下左右相连的 1 算一个块）。

提示：四方向数组 dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1}；每遇到一个未访问的 1 就 DFS 把它所在的块全部标记。

✅ 查看答案与解析

答案　参考答案：

解析：模板：外层循环找入口 → DFS 标记整块 → 块数 +1。边界检查（nx/ny 是否越界）不能少。

#include <iostream>
#include <vector>
int n, m;
std::vector<std::vector<int>> grid;
std::vector<std::vector<char>> vis;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void dfs(int x, int y) {
    vis[x][y] = 1;
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m
            && !vis[nx][ny] && grid[nx][ny] == 1) {
            dfs(nx, ny);
        }
    }
}
int main() {
    std::cin >> n >> m;
    grid.assign(n, std::vector<int>(m));
    vis.assign(n, std::vector<char>(m, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) { std::cin >> grid[i][j]; }
    }
    int blocks = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 1 && !vis[i][j]) {
                ++blocks;
                dfs(i, j);
            }
        }
    }
    std::cout << blocks << '\n';
    return 0;
}

11.7 广度优先搜索 BFS

A1识别判断题：BFS 用队列实现，从起点一层层向外扩展，天然适合求无权图最短路径。

答：______________

✅ 查看答案与解析

答案　对

解析：先到的层数一定更短，第一次访问到某点的步数就是最短步数。

B1理解选择题：下面哪句关于 BFS 标记的说法正确？

出队时标记也可以，只要别重复入队

入队时标记，防止同一个点被重复加入队列

不需要标记

只在终点标记

答：______________

✅ 查看答案与解析

答案　B

解析：入队即标记是最稳的写法：否则同一个点可能被多个邻居重复入队，复杂度失控。

C1应用改错题：下面 BFS 出队后才标记，同一节点会被重复入队。

while (!q.empty()) {
    int u = q.front(); q.pop();
    vis[u] = 1;            // 太晚！u 可能已被多个邻居入队
    for (int v : adj[u]) {
        if (!vis[v]) { q.push(v); }
    }
}

✅ 查看答案与解析

答案　入队时标记：

解析：入队即标记是 BFS 的铁律，防止重复入队和重复计算。

vis[u] = 1;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (!vis[v]) { vis[v] = 1; q.push(v); }
    }
}

D1创造写程序：n×m 迷宫（0 可走 1 是墙），从 (0,0) 到 (n-1,m-1)，输出最少步数（走不到输出 -1）。

提示：dist 数组记录步数；四个方向扩展；越界、墙、已访问都跳过。

✅ 查看答案与解析

答案　参考答案：

解析：dist 数组同时充当“步数记录 + 访问标记”；入队即标记保证每个格子只进队一次。

#include <iostream>
#include <queue>
#include <vector>
int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> maze(n);
    for (int i = 0; i < n; ++i) { std::cin >> maze[i]; }
    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};
    std::vector<std::vector<int>> dist(n, std::vector<int>(m, -1));
    std::queue<std::pair<int, int>> q;
    dist[0][0] = 0;
    q.push({0, 0});
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == n - 1 && y == m - 1) { break; }
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && dist[nx][ny] == -1 && maze[nx][ny] == '0') {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    std::cout << dist[n - 1][m - 1] << '\n';
    return 0;
}

11.8 回溯

A1识别判断题：回溯搜索在递归返回时必须“撤销上一步的选择”，否则状态被污染。

答：______________

✅ 查看答案与解析

答案　对

解析：递归返回后要把标记和临时结果恢复原样，兄弟分支才能从干净状态继续。

B1理解选择题：求 1..n 的全排列，适合用什么方法？

贪心

回溯（DFS + 标记 + 撤销）

前缀和

双指针

答：______________

✅ 查看答案与解析

答案　B

解析：全排列 = 枚举所有顺序，回溯是最自然的写法。

C1应用改错题：下面的全排列回溯漏了“撤销”，结果重复且状态错误。

void dfs(int depth) {
    if (depth == n) { print(path); return; }
    for (int i = 1; i <= n; ++i) {
        if (used[i]) { continue; }
        used[i] = true;
        path[depth] = i;
        dfs(depth + 1);
        // 缺少：used[i] = false;  ← 撤销
    }
}

✅ 查看答案与解析

答案　递归后补上撤销：

解析：“选 - 递归 - 撤销”三步缺一不可，撤销是回溯的灵魂。

        dfs(depth + 1);
        used[i] = false;   // 恢复现场

D1创造写程序：读入 n（≤8），输出 1..n 的所有全排列（每行一个排列，空格分隔）。

提示：used 数组标记 + path 数组存当前排列 + 递归深度做终止条件。

✅ 查看答案与解析

答案　参考答案：

解析：模板：终止条件（depth == n）→ 循环选数 → 标记 + 递归 + 撤销。n ≤ 8 时全排列 40320 个，可接受。

#include <iostream>
#include <vector>
int n;
std::vector<int> path;
std::vector<char> used;
void dfs(int depth) {
    if (depth == n) {
        for (int i = 0; i < n; ++i) { std::cout << path[i] << ' '; }
        std::cout << '\n';
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (used[i]) { continue; }
        used[i] = 1;
        path[depth] = i;
        dfs(depth + 1);
        used[i] = 0;   // 撤销
    }
}
int main() {
    std::cin >> n;
    path.resize(n);
    used.assign(n + 1, 0);
    dfs(0);
    return 0;
}

11.9 贪心

A1识别判断题：贪心算法每一步选当前最优，但结果不一定全局最优，需要验证或证明。

答：______________

✅ 查看答案与解析

答案　对

解析：比如“每步选最短的边”不一定得到最小生成树（要 Prim/Kruskal 那种特定的贪心才成立）。贪心必须配对正确的选择策略。

B1理解选择题：经典“区间调度”——选最多的互不重叠区间，正确的贪心策略是？

每次选最短的区间

每次选开始最早的

按结束时间排序，依次选结束最早且不冲突的

随便选

答：______________

✅ 查看答案与解析

答案　C

解析：结束得越早，给后面留的空间越多——这是可证明最优的经典贪心。

C1应用改错题：下面区间调度的贪心没有先排序，结果不对。

// 输入区间 (l, r)，求最多不重叠区间数
int cnt = 0, lastEnd = -1;
for (auto& seg : segs) {   // 缺少：按结束时间排序
    if (seg.l >= lastEnd) { ++cnt; lastEnd = seg.r; }
}

✅ 查看答案与解析

答案　先排序再贪心：

解析：贪心策略依赖有序输入；不排序就贪心等于瞎选。

std::sort(segs.begin(), segs.end(),
          [](auto& a, auto& b) { return a.r < b.r; });   // 按结束时间升序

D1创造写程序：读入 n 个区间 (l, r)，按结束时间排序后贪心，输出最多能选多少个互不重叠的区间。

提示：sort 按 r 升序；选当前结束最早且 l >= lastEnd 的。

✅ 查看答案与解析

答案　参考答案：

解析：先按结束时间排序，再贪心选不冲突的——结束最早给后面留最多空间。

#include <algorithm>
#include <iostream>
#include <vector>
struct Seg { int l, r; };
int main() {
    int n;
    std::cin >> n;
    std::vector<Seg> segs(n);
    for (int i = 0; i < n; ++i) { std::cin >> segs[i].l >> segs[i].r; }
    std::sort(segs.begin(), segs.end(),
              [](const Seg& a, const Seg& b) { return a.r < b.r; });
    int cnt = 0, lastEnd = -1;
    for (const auto& s : segs) {
        if (s.l >= lastEnd) { ++cnt; lastEnd = s.r; }
    }
    std::cout << cnt << '\n';
    return 0;
}

11.10 动态规划入门

A1识别判断题：动态规划三要素是：状态定义、转移方程、初始值（边界条件）。

答：______________

✅ 查看答案与解析

答案　对

解析：缺任何一个都推不出来：状态代表什么、怎么从小的推到大的、最小的那个值是多少。

B1理解选择题：爬楼梯（一次上 1 或 2 阶），到第 n 阶的方法数 f(n) 满足什么关系？

f(n) = f(n-1) + f(n-2)

f(n) = f(n-1) * f(n-2)

f(n) = n!

f(n) = 2n

答：______________

✅ 查看答案与解析

答案　A

解析：最后一步要么从 n-1 上一阶、要么从 n-2 上两阶，所以 f(n) = f(n-1) + f(n-2)，初始 f(1)=1, f(2)=2。

C1应用改错题：下面爬楼梯的递推缺初始值，结果全错。

int ways(int n) {
    std::vector<int> f(n + 1);
    for (int i = 3; i <= n; ++i) {
        f[i] = f[i - 1] + f[i - 2];   // f[1]、f[2] 还是 0！
    }
    return f[n];
}

✅ 查看答案与解析

答案　先设初始值：

解析：转移方程只负责“从小到大推”，最小几个状态的值必须手动给对。

    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= n; ++i) { f[i] = f[i - 1] + f[i - 2]; }

D1创造写程序：读入 n（≤90），输出爬楼梯方法数（一次 1 或 2 阶）。注意答案可能很大，用 long long。

提示：f[1]=1, f[2]=2, f[i]=f[i-1]+f[i-2]。

✅ 查看答案与解析

答案　参考答案：

解析：这就是 DP 的最小可运行模型：初始值 + 转移方程 + 目标状态。n=90 时结果超 int，必须 long long。

#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    if (n <= 2) { std::cout << n << '\n'; return 0; }
    std::vector<long long> f(n + 1);
    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= n; ++i) { f[i] = f[i - 1] + f[i - 2]; }
    std::cout << f[n] << '\n';
    return 0;
}

📚 相关概念：编译与链接 · STL · map / set · 迭代器

← 第 10 章回到练习册目录 →