用题型拆解复盘 LeetCode 第522场周赛：从拨号模拟到矩阵快速幂

第522场力扣周赛正值 2026 年国庆假期。题解作者 tiankonguse 在 2026年10月4日 更新的公开题解里，把四道题分别归到模拟、枚举、递归 DP 与矩阵快速幂，并给出可直接对照的思路与代码。[1]

下面按「先定题型 → 再落状态/枚举 → 最后用复杂度自检」的顺序整理，方便周赛后复盘或补题。

准备工作

• 平台：LeetCode 周赛题库中第522场四题。

• 语言：下文示例为 C++，换 Python/Java 时保留同一状态定义即可。

• 建议先自己写一版，再对照题解差异。

操作步骤

1、A 题「拨号的最少旋转次数 I」：环形距离模拟

做什么：拨号盘 0–9 环形排列，指针从 0 出发，按字符串 s 依次拨号；每次只能转到相邻数字，求最少旋转次数。

为什么：从前一数字到下一数字只有顺时针、逆时针两条路，代价分别是 |v-pre| 与 10-|v-pre|，取较小值累加即可，属于标准环形最短路。

怎么确认：对样例手算「从 0 到首字符」与「相邻两字符」是否与 min(dis,10-dis) 一致；复杂度应为 O(n)。[1]

int minRotations(string s) {
  int ans = 0, pre = 0;
  for (auto c : s) {
    int v = c - '0';
    int dis = abs(v - pre);
    ans += min(dis, 10 - dis);
    pre = v;
  }
  return ans;
}

2、B 题「拨号的最少旋转次数 II」：枚举一次后缀反转

做什么：拨号前至多反转一次后缀 s[k..n-1]，求最优 k（含不反转）下的最少旋转次数。

为什么：反转后路径可拆成三段——前缀 0..k-1 的拨号、从 k-1 跳到末位、再沿反转后的后缀逆向拨回。前后缀代价可预处理，枚举 k 即 O(n)。[1]

怎么确认：k=0（整串反转）与「不反转」两种边界答案是否被枚举覆盖；预处理后缀数组 suf[i] 表示后缀内部相邻转移代价之和。

3、C 题「一次删除后的最大交替子数组和」：左右递归 DP

做什么：最多删一个元素后，选连续子数组，使「偶下标和 − 奇下标和」（子数组内重新编号）最大。

为什么：交替和由子数组内位置奇偶决定符号。定义 DfsLeft(i,o) 为以 i 结尾、位置奇偶为 o 的最大交替和；DfsRight(i,o) 为以 i 开头的对称状态。不删除时直接取左右 DP 极值；删除下标 i 时拼 DfsLeft(i-1,li)+DfsRight(i+1,1-li)。[1]

怎么确认：记忆化每个 (o,i) 只算一次，总复杂度 O(n)；空删与「删端点」应被「不删除」情形覆盖，无需重复统计。

4、D 题「统计好字符串数目」：斐波那契 + 矩阵快速幂

做什么：长度为 n（可大到 10^15）的 a/b 串，满足「同字符连续块长度皆为奇数」的好串个数，模 10^9+7。

为什么：好串等价于每个相同字符块长度为奇数。看末块长度：为 1 则归到 f(n-1)，≥3 则删末两字符归到 f(n-2)，得 f(n)=f(n-1)+f(n-2)，初值 f(1)=f(2)=2。大 n 用 2×2 矩阵快速幂。[1]

怎么确认：小 n 暴力枚举与递推一致；矩阵幂后取对应项再模运算。

注意事项

• 第三题递推写法状态边界更绕，周赛现场优先记忆化搜索。

• 第四题先证明「块长皆奇」再套模板，比硬推组合公式更稳。

• 代码以题解原文为准，提交前按题目约束核对类型与取模。

说明：步骤与代码整理自 tiankonguse 2026年10月4日 公开题解，用于复盘学习；以 LeetCode 题目描述与本人提交结果为准。

来源

[1] leetcode 周赛 522，tiankonguse，2026年10月4日。

#LeetCode #周赛 #题解 #动态规划 #矩阵快速幂