Z 字形变换如何模拟？（LeetCode 6）

简化版

Z 字形变换可以按行模拟：准备 numRows 个 StringBuilder，用 row 表示当前行，用 dir 表示方向。字符依次放入当前行；到达第 0 行或最后一行时改变方向。最后把各行拼接起来。若 numRows == 1 或行数大于等于字符串长度，直接返回原串。

详细版

String convert(String s, int numRows) {
    if (numRows == 1 || numRows >= s.length()) return s;
    StringBuilder[] rows = new StringBuilder[numRows];
    for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
    int row = 0, dir = 1;
    for (char c : s.toCharArray()) {
        rows[row].append(c);
        if (row == 0) dir = 1;
        else if (row == numRows - 1) dir = -1;
        row += dir;
    }
    StringBuilder ans = new StringBuilder();
    for (StringBuilder r : rows) ans.append(r);
    return ans.toString();
}

字符写入路径是从上到下，再斜向上，再向下循环。
方向只在顶部和底部反转。
时间 O(n)，空间 O(n) 用于各行结果。

完整版教学

一、题目让你输出按行读取后的结果

Z 字形变换不是把图画出来返回，而是先把字符串按 Z 字路线写到多行，再按第一行、第二行、第三行的顺序读出。很多错误来自把“写入路径”和“读取顺序”混在一起。

例如 PAYPALISHIRING，numRows=3：

P   A   H   N
A P L S I I G
Y   I   R

按行读就是 PAHNAPLSIIGYIR。

二、按行模拟为什么最直观

真实二维矩阵会有大量空格，不需要保存。我们只关心每一行最终有哪些字符，所以可以为每一行维护一个 StringBuilder。字符走到哪一行，就追加到哪一行。

row: 0 -> 1 -> 2 -> 1 -> 0 -> 1 -> 2 ...

这条行号序列正是 Z 字路径的行变化。列位置不影响最终按行拼接，因此可以省略。

记忆钩子：Z 字变换只存“每行收到哪些字符”，不需要真的建满是空格的矩阵。

三、方向反转条件

方向 dir 表示下一步行号变化。向下时 dir=1，向上时 dir=-1。当走到顶部 row=0，下一步只能向下；当走到底部 row=numRows-1，下一步只能向上。

numRows=4 的行号周期：
0,1,2,3,2,1,0,1,2,3,2,1...

只要写对这两个反转点，就不需要单独处理竖线段和斜线段。

四、周期法也可以求解

除了模拟，还可以按行找规律。一个完整 Z 字周期长度是：

cycle = 2 * numRows - 2

对于第 r 行，字符位置通常包括 r + k*cycle；中间行还会有斜线位置 k*cycle + cycle - r。例如 numRows=4，周期为 6，第 1 行会取下标 1,5,7,11...。

行	位置规律
0	`k*cycle`
numRows-1	`numRows-1 + k*cycle`
中间行 r	`r+kcycle` 和 `kcycle+cycle-r`

周期法空间可少一些，但按行模拟更容易写对。

五、边界为什么要先处理 numRows=1

如果 numRows=1，Z 字路径没有向下向上，原串就是答案。若不提前返回，row==0 和 row==numRows-1 同时成立，方向逻辑会混乱，甚至数组越界。

另一个边界是 numRows >= s.length()，每个字符最多占一行，不会形成折返，按行读仍是原串。提前返回能简化逻辑。

六、复杂度与实现细节

按行模拟访问每个字符一次，最后拼接也访问每个字符一次，时间 O(n)。各行构建器合计保存 n 个字符，空间 O(n)。

实现时不要用字符串反复 +=，因为 Java 字符串不可变，反复拼接可能退化为 O(n²)。使用 StringBuilder 能保持线性复杂度。

七、常见误区与追问

误区：真的创建二维矩阵并填空格。 空格不参与输出，矩阵浪费空间且容易错列。
误区：忘记 numRows==1。 方向反转会失去意义，可能越界。
误区：把斜向上时列变化也编码进结果。 输出只按行拼接，列只用于图形展示，不必保存。
追问：周期长度为什么是 2*numRows-2？ 从顶到底走 numRows-1 步，再从底回顶走 numRows-1 步。
追问：能否 O(1) 额外空间？ 若不计输出，可以用周期法直接生成结果；但返回字符串本身仍需 O(n)。
追问：模拟法和周期法怎么选？ 面试优先模拟，易懂不易错；追求数学规律时再讲周期法。

八、加强记忆

Z 字形变换 = 行号上下折返。准备多行缓冲，字符按 0..numRows-1..0 的行号轨迹写入，到顶部向下，到底部向上，最后逐行拼接。边界 numRows==1 必须先返回，周期法的周期是 2*numRows-2。

简化版

详细版