第 07 周把字符串、链表、矩阵、背包、拓扑排序和滑动窗口都串了一遍。多数题的难点不在算法名,而在“要维护哪个量”和“哪种压缩会破坏状态依赖”。

字符串与链表:拼接一次,覆盖所有旋转

旋转字符串判断 B 能不能由 A 旋转若干位得到。长度不同直接 false;长度相同时,任何旋转结果都是 A + A 中一段长度为 n 的子串,反过来,A + A 中出现的长度为 n 的子串一定对应某个旋转。

#include <string>
using namespace std;
 
class Solution
{
public:
    bool solve(string A, string B)
    {
        if (A.size() != B.size()) return false;
        return (A + A).find(B) != string::npos;
    }
};

find 返回下标,找不到时返回 string::npos。直接写 != -1 也能得到相同结果,因为 -1 会被转换成 size_t 的最大值,但用 npos 更明确。逐次旋转再比较是 O(n²),A + A 把“所有旋转”一次性铺开;std::string::find 最坏是 O(n·m),n 很大时可以换 KMP。

合并 k 个已排序链表要求把 k 条升序链表并成一条升序链表,节点总数 N、k 条链。每个链表当前只暴露头节点,用小根堆取 k 个头里的最小值,取出后把它的后继入堆。

#include <queue>
#include <vector>
using namespace std;
 
struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
class Solution
{
    struct Cmp
    {
        bool operator()(ListNode* a, ListNode* b) const { return a->val > b->val; }
    };
 
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
        for (ListNode* h : lists)
            if (h) heap.push(h);
 
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (!heap.empty())
        {
            ListNode* t = heap.top();
            heap.pop();
            tail = tail->next = t;
            if (t->next) heap.push(t->next);
        }
        return dummy.next;
    }
};

堆里最多 k 个节点,每次操作 O(log k),总时间 O(N log k)。逐个合并两条链的写法是 O(Nk),k 大时会慢;把所有节点一次性压进堆是 O(N log N),也没有利用“每条链已经有序”。

dummy 只是栈上的哨兵,返回值是 dummy.next,真正的链表节点都在原链表里,不会被销毁。

前缀信息:前 x 个里的第二大值,和最大差值

天使果冻给 n 个果冻的美味度,q 次询问前 x 个果冻中第二大值;若最大值出现两次以上,第二大值就等于最大值。2 ≤ x ≤ n。

扫描时维护前缀最大值 mx[i] 与前缀第二大值 second[i]:

#include <iostream>
using namespace std;
 
const int N = 1e5 + 10;
int a[N], mx[N], second[N];
 
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
 
    mx[1] = a[1];
    second[1] = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (a[i] >= mx[i - 1]) { mx[i] = a[i]; second[i] = mx[i - 1]; }
        else if (a[i] >= second[i - 1]) { mx[i] = mx[i - 1]; second[i] = a[i]; }
        else { mx[i] = mx[i - 1]; second[i] = second[i - 1]; }
    }
 
    int q;
    cin >> q;
    while (q--)
    {
        int x;
        cin >> x;
        cout << second[x] << '\n';
    }
    return 0;
}

a[i] >= mx[i-1] 时,旧的(或并列的)最大值退成第二大值——这一支同时处理了“新值更大”和“新值追平最大值”两种情况。q 次询问 O(1) 回答,总时间 O(n + q)。

课件的 C++ 版在这里跑偏了:它读入 (名字, 分数),按 pair<int, string> 排序后输出所有名字。那是一道“按分数排序输出人名”的题,和“前缀第二大值”不是同一个问题;同一处给出的 Java 版才是本题解法。照 C++ 那段提交,样例都过不了。

最大差值求数组中 a[j] - a[i] 的最大值,要求 i < j。扫描到 j 时,只需要知道 j 之前的最小值。

#include <algorithm>
#include <vector>
using namespace std;
 
class Solution
{
public:
    int getDis(vector<int>& a, int n)
    {
        int ret = 0, mn = a[0];
        for (int i = 1; i < n; ++i)
        {
            ret = max(ret, a[i] - mn);   // 先用之前的最小值
            mn = min(mn, a[i]);          // 再更新最小值
        }
        return ret;
    }
};

顺序反过来也能得到 ≥ 0 的结果,但“先用后更新”更贴合“i < j”的定义。时间 O(n),空间 O(1)。两重循环是 O(n²),n 到 1e5 时超时。

矩阵与棋盘:只记操作的奇偶

dd 爱旋转给 n × n 矩阵,两种操作:1 是顺时针旋转 180°,2 是关于行镜像(上下翻转)。q 次操作后输出矩阵,n ≤ 1000、q ≤ 10^5。

180° 旋转等于“上下翻转 + 左右翻转”,所以每个操作只影响两个奇偶标记:操作 1 让行、列翻转次数都加一,操作 2 只让行翻转次数加一。最后按奇偶执行两次整体翻转即可。

#include <algorithm>
#include <iostream>
using namespace std;
 
const int N = 1010;
int n, g[N][N];
 
void flipRow()
{
    for (int i = 0; i < n / 2; ++i)
        for (int j = 0; j < n; ++j)
            swap(g[i][j], g[n - 1 - i][j]);
}
 
void flipCol()
{
    for (int j = 0; j < n / 2; ++j)
        for (int i = 0; i < n; ++i)
            swap(g[i][j], g[i][n - 1 - j]);
}
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> g[i][j];
 
    int q, x, row = 0, col = 0;
    cin >> q;
    while (q--)
    {
        cin >> x;
        if (x == 1) { ++row; ++col; }
        else ++row;
    }
 
    if (row % 2) flipRow();
    if (col % 2) flipCol();
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j) cout << g[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

每次操作都真的搬矩阵是 O(q·n²),1e5 × 1e6 直接超时。翻转只做一次 O(n²),q 只用来累加计数。行翻转和列翻转作用在不同的下标轴上,顺序可以交换。

题面里 2×2 的例子:第 2 种操作“关于行镜像”把 [1 2; 3 4] 变成 [3 4; 1 2];第 1 种操作是 180°,两个方向都要翻

棋子翻转在 4 × 4 棋盘上,每次以 (x, y) 为中心翻转上下左右四个棋子(不翻中心),坐标从 1 开始。

#include <vector>
using namespace std;
 
class Solution
{
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
 
public:
    vector<vector<int>> flipChess(vector<vector<int>>& A, vector<vector<int>>& f)
    {
        for (auto& v : f)
        {
            int a = v[0] - 1, b = v[1] - 1;   // 转成 0 开始
            for (int k = 0; k < 4; ++k)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < 4 && y >= 0 && y < 4)
                    A[x][y] ^= 1;             // 0/1 翻转等价于异或 1
            }
        }
        return A;
    }
};

棋盘只有 4 × 4,直接改原矩阵即可。翻转 0/1 用 ^= 1 比写 if 分支干净;坐标先减一是最容易漏的一步。操作数最多 1e5,但每个操作只碰 4 个格子,总时间 O(操作数)。

题面里的 4×4 棋盘:灰色格子标出了被翻转过的位置(多次操作取并集),中心 (x,y) 本身不变;图里给出的是翻转前后的两组棋盘

背包三题:同余、完全平方、最少硬币

小红取数从数组中选若干个,要求和是 k 的倍数且和最大。按余数做状态:dp[i][r] 表示前 i 个数里选出的和模 k 为 r 时的最大和。

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
 
const int N = 1010;
int n, k;
LL a[N], dp[N][N];
 
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
 
    memset(dp, -0x3f, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int r = 0; r < k; ++r)
        {
            int from = (int)((r - a[i] % k + k) % k);
            dp[i][r] = max(dp[i - 1][r], dp[i - 1][from] + a[i]);
        }
 
    cout << (dp[n][0] > 0 ? dp[n][0] : -1) << '\n';
    return 0;
}

不选第 i 个,余数不变;选第 i 个,前 i-1 个的余数必须是 (r - a[i]) mod k。这个余数不是 r - 1,而是任意一个位置,所以不能原地压成一维:把 dp[i] 写回同一张表后,dp[from] 可能已经被第 i 个数更新过,同一个数会被重复选。

课件说“这道题不能用空间优化”,这句话只说对了一半。不能做的是原地一维;用 prev[k] 和 cur[k] 两行滚动,空间仍能从 O(nk) 降到 O(k)。时间 O(nk)。

memset(dp, -0x3f, sizeof dp) 会把每个字节写成 0xC1,64 位整数变成约 -4.56 × 10^18;再加一个不超过 1e9 的 a[i] 不会下溢,也不会被误当成可行解。

最少的完全平方数给 n,求至少几个完全平方数之和等于 n。这是完全背包:物品是 1、4、9 等完全平方数,每个物品可以用多次。

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
 
const int N = 10010;
int dp[N];
 
int main()
{
    int n;
    cin >> n;
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i * i <= n; ++i)
        for (int j = i * i; j <= n; ++j)
            dp[j] = min(dp[j], dp[j - i * i] + 1);
    cout << dp[n] << '\n';
    return 0;
}

容量 j 从小到大遍历,dp[j - i*i] 可能已经用过当前这个平方数,所以允许重复使用——这正是完全背包和 01 背包的差别。时间 O(n√n),空间 O(n)。

兑换零钱给 n 种面值和目标 aim,求最少硬币数,凑不出输出 -1。转移与上一题一样,只是物品价值换成面值。

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
 
const int N = 10010, M = 5010;
int n, aim, a[N], dp[M];
 
int main()
{
    cin >> n >> aim;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = a[i]; j <= aim; ++j)
            dp[j] = min(dp[j], dp[j - a[i]] + 1);
 
    cout << (dp[aim] >= 0x3f3f3f3f ? -1 : dp[aim]) << '\n';
    return 0;
}

不可达位置保持 0x3f3f3f3f:INF + 1 比 INF 大,min 不会把它变小,所以判断“是否还是 INF”是安全的。面值大于 aim 时内层循环不执行,不影响结果。

记忆化与序列 DP:滑雪、合唱队形、宵暗的妖怪

滑雪在 n × m 的高度矩阵上,每次可以走向上下左右中比当前低的位置,求最长滑行长度。和“矩阵最长递增路径”是同一个模板,把比较方向反过来。

#include <algorithm>
#include <iostream>
using namespace std;
 
const int N = 110;
int n, m, a[N][N], dp[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
int dfs(int i, int j)
{
    if (dp[i][j]) return dp[i][j];
    int len = 1;
    for (int k = 0; k < 4; ++k)
    {
        int x = i + dx[k], y = j + dy[k];
        if (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] < a[i][j])
            len = max(len, 1 + dfs(x, y));
    }
    return dp[i][j] = len;
}
 
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
 
    int ret = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            ret = max(ret, dfs(i, j));
    cout << ret << '\n';
    return 0;
}

dp 初值为 0,合法的长度至少是 1,所以 0 可以当“没算过”的标记,不需要 memset(-1)。高度严格递减保证无环,不需要访问标记。每个格子只算一次,时间 O(nm),空间 O(nm)。

合唱队形从 n 个人里删掉尽量少的人,使剩下的人身高先严格上升、再严格下降。对每个位置求“以 i 结尾的最长上升子序列” f[i] 和“以 i 开头的最长下降子序列” g[i],两者在峰顶拼接。

#include <algorithm>
#include <iostream>
using namespace std;
 
const int N = 1010;
int n, a[N], f[N], g[N];
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
 
    for (int i = 1; i <= n; ++i)
    {
        f[i] = 1;
        for (int j = 1; j < i; ++j)
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
    }
    for (int i = n; i >= 1; --i)
    {
        g[i] = 1;
        for (int j = i + 1; j <= n; ++j)
            if (a[i] > a[j]) g[i] = max(g[i], g[j] + 1);
    }
 
    int keep = 0;
    for (int i = 1; i <= n; ++i) keep = max(keep, f[i] + g[i] - 1);
    cout << n - keep << '\n';
    return 0;
}

峰顶被 f 和 g 各算了一次,所以减一。n ≤ 1000,O(n²) 足够;如果要 O(n log n),需要用树状数组或二分维护两个方向的 LIS。

宵暗的妖怪每次可以吃掉连续的三段黑暗,获得中间那段的数值,求最大总收获。选中以 i 为右端的三段 [i-2, i-1, i],收益是 a[i-1];这三段被吃掉后,下一个可选的三段必须结束在 i-3 或更早。

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
 
const int N = 1e5 + 10;
int n;
LL a[N], dp[N];
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
 
    for (int i = 3; i <= n; ++i)                 // dp[i]:前 i 段的最大收益
        dp[i] = max(dp[i - 1], dp[i - 3] + a[i - 1]);
 
    cout << dp[n] << '\n';
    return 0;
}

dp[i-1] 表示不以 i 结尾,dp[i-3] + a[i-1] 表示选了 [i-2, i-1, i]。相邻两个三段不能重叠,所以回退三格而不是两格。题意保证 n ≥ 3,循环从 3 开始没有越界问题。时间 O(n),空间 O(n),也可以滚成三个变量。

堆、哈希与层序:哈夫曼、众数字符、过桥

字符编码统计字符串里每个字符的频次,求哈夫曼编码后的总长度。每次取两个最小频次合并,合并值累加,放回堆里。

#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
 
int main()
{
    string s;
    while (cin >> s)                 // 多组输入
    {
        int cnt[300] = {0};
        for (char c : s) ++cnt[c];
 
        priority_queue<long long, vector<long long>, greater<long long>> heap;
        for (int i = 0; i < 300; ++i)
            if (cnt[i]) heap.push(cnt[i]);
 
        long long ret = 0;
        while (heap.size() > 1)
        {
            long long a = heap.top(); heap.pop();
            long long b = heap.top(); heap.pop();
            ret += a + b;
            heap.push(a + b);
        }
        cout << ret << '\n';
    }
    return 0;
}

每个频次被累加的次数就是它在哈夫曼树里的深度,所有合并值之和等于带权路径长度。k 种字符时 O(k log k)。只有一种字符时循环不执行,输出 0。

**神奇的字母(二)**读入若干单词直到 EOF,求出现次数最多的字母。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    int cnt[26] = {0}, best = 0;
    char ans = 0;
    string s;
    while (cin >> s)
        for (char c : s)
        {
            int v = ++cnt[c - 'a'];
            if (v > best) { best = v; ans = c; }
        }
    cout << ans << '\n';
    return 0;
}

cin >> s 会跳过空白,所以单词之间的空格和换行不影响统计。只有严格大于才更新,出现并列时保留最先达到该次数的字符;题目若保证众数唯一,这个细节就用不上。时间 O(总字符数)。

过桥有 n 个浮块,站在 i 号时最远可以跳到 i + a[i];a[i] 为负时目标可能小于 i,题面规定小于 1 就落到 1 号。求从 1 号到 n 号的最少步数,走不到输出 -1。

按层扩展:第 k 步能到达的是一段连续区间 [1, right]。遍历当前层 [left, right] 的每个浮块,取 max(i + a[i]) 作为下一层的右端。

#include <algorithm>
#include <iostream>
using namespace std;
 
const int N = 2010;
int n, a[N];
 
int bfs()
{
    int left = 1, right = 1, steps = 0;
    while (left <= right)
    {
        ++steps;
        int nr = right;
        for (int i = left; i <= right; ++i)
        {
            nr = max(nr, i + a[i]);
            if (nr >= n) return steps;
        }
        left = right + 1;
        right = nr;
    }
    return -1;
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cout << bfs() << '\n';
    return 0;
}

从 [left, right] 出发,可达位置的并集是 [1, max(i + a[i])],所以下一层从 right + 1 开始。nr 初值设为 right,保证区间不会倒退。每层遍历一次,总时间 O(n),空间 O(1)。

枚举与图:字母串、拓扑排序、双窗口计数

游游的字母串每次可以把一个字母改成相邻字母(z 与 a 相邻),求把所有字符改成同一个字母的最小总代价。枚举目标字母 ch,每个字符的代价是环上的最短距离 min(|x - ch|, 26 - |x - ch|)。

#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    int ret = 1e9;
    for (char ch = 'a'; ch <= 'z'; ++ch)
    {
        int sum = 0;
        for (char c : s)
        {
            int d = abs(c - ch);
            sum += min(d, 26 - d);
        }
        ret = min(ret, sum);
    }
    cout << ret << '\n';
    return 0;
}

字母表是环,a 到 z 的距离既可以走 25 步也可以绕 1 步,必须取 min(d, 26 - d)。只枚举 26 个目标,时间 O(26n)。

**体育课测验(二)**给项目依赖 groups[i] = {a, b},表示做 a 之前必须先做 b,求任意一个合法顺序;有环则返回空数组。

依赖 b → a 建边,入度为 0 的项目先入队,BFS 逐个删边。最后检查输出长度是否等于 n。

#include <queue>
#include <vector>
using namespace std;
 
class Solution
{
public:
    vector<int> findOrder(int n, vector<vector<int>>& groups)
    {
        vector<vector<int>> e(n);
        vector<int> in(n);
        for (auto& v : groups)
        {
            int a = v[0], b = v[1];
            e[b].push_back(a);   // b -> a:先做 b,才能做 a
            ++in[a];
        }
 
        queue<int> q;
        for (int i = 0; i < n; ++i)
            if (in[i] == 0) q.push(i);
 
        vector<int> ret;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            ret.push_back(u);
            for (int v : e[u])
                if (--in[v] == 0) q.push(v);
        }
        return (int)ret.size() == n ? ret : vector<int>{};
    }
};

边的方向是最容易反的地方:groups[i][0] 是“想做”的项目,groups[i][1] 是它的前置,所以边从前置指向目标。若有环,环上的节点入度永远降不到 0,队列提前为空,长度检查会拦住。时间 O(n + 边数)。

小红的子串统计字符种类数在 [l, r] 之间的子串个数,n ≤ 2 × 10^5,l、r ≤ 26。

把“种类数 ≤ x”的方案数记作 count(x),答案是 count(r) - count(l-1)。count(x) 用滑动窗口:右端加入新字符,种类超过 x 时左端右移。

#include <iostream>
#include <string>
using namespace std;
typedef long long LL;
 
int n, l, r;
string s;
 
// 字符种类数不超过 x 的子串个数
LL countAtMost(int x)
{
    if (x == 0) return 0;
    int cnt[26] = {0}, kinds = 0, left = 0;
    LL ret = 0;
    for (int right = 0; right < n; ++right)
    {
        if (cnt[s[right] - 'a']++ == 0) ++kinds;
        while (kinds > x)
        {
            if (cnt[s[left] - 'a']-- == 1) --kinds;
            ++left;
        }
        ret += right - left + 1;   // 以 right 结尾的合法起点数
    }
    return ret;
}
 
int main()
{
    cin >> n >> l >> r >> s;
    cout << countAtMost(r) - countAtMost(l - 1) << '\n';
    return 0;
}

当窗口 [left, right] 是满足种类 ≤ x 的最左窗口时,任何以 right 结尾、起点在 [left, right] 的子串都合法,共 right - left + 1 个。两次窗口都是 O(n),总时间 O(n),空间是 26 个计数。题面保证 l ≥ 1,l - 1 ≥ 0,countAtMost(0) 返回 0 即可。