---
title: "用题型拆解复盘 LeetCode 第522场周赛：从拨号模拟到矩阵快速幂 - Angryecho"
description: "第522场力扣周赛正值 2026 年国庆假期。题解作者 tiankonguse 在 2026年10月4日 更新的公开题解里，把四道题分别归到模拟、枚举、递归 DP 与矩阵快速幂，并给出可直接对照的思路与代码。[1] 下面按「先定题型 → 再落状态/枚举 → 最后用复杂度自检」的顺序整理，方便周赛后复盘或补题。"
canonical_url: "https://www.angryecho.com/c/LCshua_ti/p/P2TBBomQ11MCELhlIJtIo"
meta:
  "og:description": "第522场力扣周赛正值 2026 年国庆假期。题解作者 tiankonguse 在 2026年10月4日 更新的公开题解里，把四道题分别归到模拟、枚举、递归 DP 与矩阵快速幂，并给出可直接对照的思路与代码。[1] 下面按「先定题型 → 再落状态/枚举 → 最后用复杂度自检」的顺序整理，方便周赛后复盘或补题。"
  "og:image": "https://www.angryecho.com/_og/d/c_Post%2Ctitle_~5ZCQ5qe9572R%2Cdescription_~5ZCQ5qe95LiA5LiL77yM5bCx5LiK5ZCQ5qe9572R44CC%2CpostId_P2TBBomQ11MCELhlIJtIo%2Crevision_~MjAyNi0xMC0yN1QwMjo1Nzo0OS4yMjMzNTBa%2Cp_Ii9jL0xDc2h1YV90aS9wL1AyVEJCb21RMTFNQ0VMaGxJSnRJbyI%2Cs_Ls9JTXAFCnpUqqc9.png"
  "og:image:height": "630"
  "og:image:type": image/png
  "og:image:width": "1200"
  "og:title": "用题型拆解复盘 LeetCode 第522场周赛：从拨号模拟到矩阵快速幂"
---

> Index of every page on this site: [llms.txt](https://www.angryecho.com/llms.txt)

# **用题型拆解复盘 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]

```cpp
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](https://github.tiankonguse.com/blog/2026/10/04/leetcode-contest-522.html)，tiankonguse，2026年10月4日。

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

排序方式 :

### **成为第一条评论！**

Nobody's responded to this post yet. Add your thoughts and get the conversation going.

```json
{"@context":"https://schema.org","@graph":[{"@id":"https://www.angryecho.com/c/LCshua_ti/p/P2TBBomQ11MCELhlIJtIo#post","@type":"DiscussionForumPosting","commentCount":0,"dateModified":"2026-10-27T02:57:49.223Z","datePublished":"2026-10-04T04:00:00.000Z","description":"第522场力扣周赛正值 2026 年国庆假期。题解作者 tiankonguse 在 2026年10月4日 更新的公开题解里，把四道题分别归到模拟、枚举、递归 DP 与矩阵快速幂，并给出可直接对照的思路与代码。[1] 下面按「先定题型 → 再落状态/枚举 → 最后用复杂度自检」的顺序整理，方便周赛后复盘或补题。","headline":"用题型拆解复盘 LeetCode 第522场周赛：从拨号模拟到矩阵快速幂","isPartOf":"https://www.angryecho.com/c/LCshua_ti","mainEntityOfPage":"https://www.angryecho.com/c/LCshua_ti/p/P2TBBomQ11MCELhlIJtIo","text":"第522场力扣周赛正值 2026 年国庆假期。题解作者 tiankonguse 在 2026年10月4日 更新的公开题解里，把四道题分别归到模拟、枚举、递归 DP 与矩阵快速幂，并给出可直接对照的思路与代码。[1]\n\n下面按「先定题型 → 再落状态/枚举 → 最后用复杂度自检」的顺序整理，方便周赛后复盘或补题。\n\n准备工作\n\n\n\n\n\n平台：LeetCode 周赛题库中第522场四题。\n\n\n\n语言：下文示例为 C++，换 Python/Java 时保留同一状态定义即可。\n\n\n\n建议先自己写一版，再对照题解差异。\n\n操作步骤\n\n1、A 题「拨号的最少旋转次数 I」：环形距离模拟\n\n做什么：拨号盘 0–9 环形排列，指针从 0 出发，按字符串 s 依次拨号；每次只能转到相邻数字，求最少旋转次数。\n\n为什么：从前一数字到下一数字只有顺时针、逆时针两条路，代价分别是 |v-pre| 与 10-|v-pre|，取较小值累加即可，属于标准环形最短路。\n\n怎么确认：对样例手算「从 0 到首字符」与「相邻两字符」是否与 min(dis,10-dis) 一致；复杂度应为 O(n)。[1]\n\nint minRotations(string s) {\n  int ans = 0, pre = 0;\n  for (auto c : s) {\n    int v = c - '0';\n    int dis = abs(v - pre);\n    ans += min(dis, 10 - dis);\n    pre = v;\n  }\n  return ans;\n}\n\n2、B 题「拨号的最少旋转次数 II」：枚举一次后缀反转\n\n做什么：拨号前至多反转一次后缀 s[k..n-1]，求最优 k（含不反转）下的最少旋转次数。\n\n为什么：反转后路径可拆成三段——前缀 0..k-1 的拨号、从 k-1 跳到末位、再沿反转后的后缀逆向拨回。前后缀代价可预处理，枚举 k 即 O(n)。[1]\n\n怎么确认：k=0（整串反转）与「不反转」两种边界答案是否被枚举覆盖；预处理后缀数组 suf[i] 表示后缀内部相邻转移代价之和。\n\n3、C 题「一次删除后的最大交替子数组和」：左右递归 DP\n\n做什么：最多删一个元素后，选连续子数组，使「偶下标和 − 奇下标和」（子数组内重新编号）最大。\n\n为什么：交替和由子数组内位置奇偶决定符号。定义 DfsLeft(i,o) 为以 i 结尾、位置奇偶为 o 的最大交替和；DfsRight(i,o) 为以 i 开头的对称状态。不删除时直接取左右 DP 极值；删除下标 i 时拼 DfsLeft(i-1,li)+DfsRight(i+1,1-li)。[1]\n\n怎么确认：记忆化每个 (o,i) 只算一次，总复杂度 O(n)；空删与「删端点」应被「不删除」情形覆盖，无需重复统计。\n\n4、D 题「统计好字符串数目」：斐波那契 + 矩阵快速幂\n\n做什么：长度为 n（可大到 10^15）的 a/b 串，满足「同字符连续块长度皆为奇数」的好串个数，模 10^9+7。\n\n为什么：好串等价于每个相同字符块长度为奇数。看末块长度：为 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\n怎么确认：小 n 暴力枚举与递推一致；矩阵幂后取对应项再模运算。\n\n注意事项\n\n\n\n\n\n第三题递推写法状态边界更绕，周赛现场优先记忆化搜索。\n\n\n\n第四题先证明「块长皆奇」再套模板，比硬推组合公式更稳。\n\n\n\n代码以题解原文为准，提交前按题目约束核对类型与取模。\n\n\n\n说明：步骤与代码整理自 tiankonguse 2026年10月4日 公开题解，用于复盘学习；以 LeetCode 题目描述与本人提交结果为准。\n\n来源\n\n\n\n[1] leetcode 周赛 522，tiankonguse，2026年10月4日。\n\n#LeetCode #周赛 #题解 #动态规划 #矩阵快速幂","url":"https://www.angryecho.com/c/LCshua_ti/p/P2TBBomQ11MCELhlIJtIo","author":{"@type":"Person","name":"用户124308","url":"https://www.angryecho.com/u/8vGfMahv"},"interactionStatistic":[{"@type":"InteractionCounter","interactionType":"https://schema.org/LikeAction","userInteractionCount":0},{"@type":"InteractionCounter","interactionType":"https://schema.org/DislikeAction","userInteractionCount":0},{"@type":"InteractionCounter","interactionType":"https://schema.org/ViewAction","userInteractionCount":0},{"@type":"InteractionCounter","interactionType":"https://schema.org/ShareAction","userInteractionCount":0}]}]}
```

## Sitemap

See the full [sitemap](https://www.angryecho.com/sitemap.md) for all pages.