Z 字形变换 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

将一个给定字符串 s 根据给定的行数 numRows，以从上往下、从左到右进行 Z 字形排列后，按行读取拼接成新字符串并返回。

示例 1

输入：s = "PAYPALISHIRING", numRows = 3

输出："PAHNAPLSIIGYIR"

示例 2

输入：s = "PAYPALISHIRING", numRows = 4

输出："PINALSIGYAHRPI"

💭 模拟答题者思考

1. 与其去推每个字符在 Z 形里的坐标公式，不如直接模拟「走 Z 字」的过程。

2. 一个指针在行号上下移动：到第 0 行就向下走，到最后一行就向上走。

3. 把每个字符按当前行号追加到对应行的缓冲区。

4. 最后把所有行拼起来即可。numRows == 1 时没有折返，直接返回原串。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`rows`	string[]	定义：每一行按顺序累积的字符维护：第 r 行拿到所有落在该行的字符更新：每个字符追加到 rows[当前行]
`r`	int	定义：当前字符应放的行号维护：在 0 和 numRows-1 之间来回更新：r += step
`step`	int	定义：行号移动方向（+1 向下 / -1 向上）维护：到顶或到底时翻转更新：r==0 时置 +1，r==numRows-1 时置 -1

⌨️ 落码步骤

1. 特判 numRows == 1 直接返回 s

2. 建 rows 数组，r = 0，step = 1

3. 遍历每个字符，追加到 rows[r]

4. 到边界翻转方向：r==0 → step=1，r==numRows-1 → step=-1；然后 r += step

5. 拼接所有行返回

💻 代码实现

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        rows = [''] * numRows   # 每一行累积的字符
        r = 0                   # 当前行号
        step = 1                # 方向：+1 向下，-1 向上
        for c in s:
            rows[r] += c
            if r == 0:
                step = 1
            elif r == numRows - 1:
                step = -1
            r += step
        return ''.join(rows)

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> rows(numRows);
        int r = 0, step = 1;
        for (char c : s) {
            rows[r] += c;
            if (r == 0) step = 1;
            else if (r == numRows - 1) step = -1;
            r += step;
        }
        string ans;
        for (auto& row : rows) ans += row;
        return ans;
    }
};
// 时间 O(n)，空间 O(n)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(n)

⚠️ 常见坑

❗ 必须特判 numRows == 1，否则 step 永远翻转不了会死循环/越界。

❗ 翻转方向的判断要在移动 r 之前做。

❗ 直接模拟比推坐标公式更不易错，代码更短。

🔍 必测边界 Case

Case 1：单行

s = "ABCD", numRows = 1 → "ABCD"

Case 2：行数大于长度

s = "AB", numRows = 5 → "AB"