EnlightenCode

Z 字形变换 ​

这题的名字听起来有点抽象，但本质上是一个字符串重排问题：给你一个字符串 s 和一个行数 numRows，让你按照「Z 字形」写在纸上，再按行读出来，返回新的字符串。

numRows 是一行一行往下写，写到最后一行后折返往上写，如此之字形往复。最后你不是按「走的路径」读，而是按行从上到下读。

有几个容易踩坑的点：

  • Z 字形只是一个中间的写法，最终输出是「每一行拼起来」，不是按路径顺序
  • numRows = 1 的时候，其实没有 Z 字形，结果就是原字符串
  • 如果 numRows >= s.length，每个字符一行，也等价于原字符串

用样例感受一下题意：

text
s = "PAYPALISHIRING", numRows = 3

按 Z 字形写：
P   A   H   N
A P L S I I G
Y   I   R

按行读：PAHNAPLSIIGYIR

如果是 numRows = 4：

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

结果：PINALSIGYAHRPI

第一个下意识想法：直接「画矩阵」 ​

一般人第一次看到都会想：我要不要开一个二维数组，把字符一个个「走路径」填进去，最后按行读出来？

伪代码大概是：

  1. 估算出矩阵需要多少列
  2. 开一个 numRows x numCols 的二维数组，先用空字符填满
  3. 从左上角开始，模拟「往下再往上」的走法，把 s 的字符按顺序放进去
  4. 最后按行把非空字符拼起来

这确实能做出来，但有几个问题：

  • 你得先算「要多少列」——这本身就不太直观
  • 矩阵里会有很多空格，空间利用率很低
  • 实现会有不少边界判断，代码又长又不好读

整体上，这个思路更多是在「照着图画」，而不是抓住本质结构。

换个视角：我真的需要矩阵吗？ ​

仔细看题目，其实真正需要的是：

每一行最终长成什么样，然后把所有行拼起来。

中间是不是矩阵不重要，只要我能知道「某个字符属于哪一行」就够了。

这就引出了一个更自然的想法：

  • 我维护 numRows 个字符串（或者数组），分别对应「第 0 行、第 1 行...」
  • 遍历原字符串 s，顺着 Z 字形的路径走
  • 每拿到一个字符，就直接丢到当前行对应的那一条字符串里
  • 最后把所有行拼接起来

你可以把它想象成「按照 Z 字形顺序，往多个桶里扔字符」：

text
行0: P   A   H   N   ->  "PAHN"
行1: A P L S I I G   ->  "APLSIIG"
行2: Y   I   R       ->  "YIR"

最后: "PAHN" + "APLSIIG" + "YIR"

那问题就变成了：

遍历字符串的时候，如何知道「当前应该往第几行写」，以及「什么时候往下走 / 往上走」？

把「走 Z 字形」抽象成一个状态机 ​

我们来直接模拟那条「Z 字形路径」：

  • 一开始在第 0 行，方向是「往下」
  • 每读取一个字符：
    • 先把它追加到当前行
    • 再根据当前方向，curRow++ 或 curRow--
    • 如果走到第 0 行或最后一行，就反转方向

伪代码的状态大概是：

  • curRow：当前在哪一行
  • goingDown：当前是不是在往下走（到底后会往上走）
  • rows[]：每一行已经累积的字符串

如果你手动模拟 s = "PAYPALISHIRING", numRows = 3，状态会像这样变化：

text
初始: curRow = 0, goingDown = false

P: 行0 <- 'P'   -> rows[0] = "P"
   现在在第0行，掉头往下: goingDown = true, curRow = 1

A: 行1 <- 'A'   -> rows[1] = "A"
   往下: curRow = 2

Y: 行2 <- 'Y'   -> rows[2] = "Y"
   到底了，掉头往上: goingDown = false, curRow = 1

P: 行1 <- 'P'   -> rows[1] = "AP"
   往上: curRow = 0

A: 行0 <- 'A'   -> rows[0] = "PA"
   到顶了，掉头往下...
...

这样一来，我们完全不用管列数，甚至不用真的画出矩阵，只要维护「当前行」和「方向」即可。

代码实现（每一行都有“存在理由”） ​

javascript
var convert = function(s, numRows) {
    // 特殊情况：只有一行时，没有 Z 字形，直接返回原字符串
    // 或者行数 >= 字符长度时，每个字符一行，读出来也等于原串
    if (numRows === 1 || numRows >= s.length) {
        return s
    }

    // 用数组来存每一行的字符串，后面 join 即可
    // 为什么不用一个巨大的二维数组？
    // 因为我们根本不关心列，只关心“这一行的字符顺序”
    const rows = new Array(numRows).fill('').map(() => '')

    let curRow = 0        // 当前在哪一行
    let goingDown = false // 当前是否在“往下走”

    // 遍历原字符串中的每个字符
    for (const ch of s) {
        // 把字符拼到当前行后面
        rows[curRow] += ch

        // 如果走到顶部或底部，就反转方向
        if (curRow === 0 || curRow === numRows - 1) {
            goingDown = !goingDown
        }

        // 根据方向决定下一步走向哪一行
        curRow += goingDown ? 1 : -1
    }

    // 最后按行拼接
    return rows.join('')
}

可以自己拿前面的例子手动跑一下，对比一下 rows 在每一步的变化，会更有感觉。

进阶视角：周期 & 按公式算下标（可选思路） ​

如果你对规律再敏感一点，会发现 Z 字形其实是有「周期」的。

假设 numRows = r，那么一整个「下去 + 上来」的周期长度是：

text
cycleLen = 2 * r - 2

比如 r = 3 时：

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

cycleLen = 4
下标:     0 1 2 3 4 5 6 7 8 9 ...
行0:      0       4       8   ...
行1:        1   3   5   7   ...
行2:          2       6       ...

你会发现：

  • 第一行和最后一行：每次跳 cycleLen
  • 中间的行：在一个周期内会出现两次，对应的下标可以按公式算出来

基于这个规律，我们可以不用模拟走路径，而是按行、按周期直接算出每个位置的下标。这会让代码稍微「数学一点」，但本质复杂度还是 O(n)。

在面试场景下，一般用「模拟走路径 + rows 数组」就足够了，思路更直观、实现也更安全。

这题到底在考什么？ ​

表面上看，这题在考「字符串重排」或者「模拟 Z 字形」，但更底层的考点是：

  1. 能不能从“画图”抽象到“状态机”
    一开始你可能会画出一个二维矩阵，仔细想想就会发现其实只需要知道「当前在哪一行」「当前方向是什么」，这就是一个很小的状态机。

  2. 对「模式」的敏感度
    看到 Z 字形，其实就是一个「下去 + 上来」的周期运动。抽象出来之后，写代码就只是实现这个模式。

  3. 边界条件的处理意识

    • numRows = 1 或 numRows >= s.length 这些 corner case 如果不先 return，很容易在循环里出 bug
    • 顶部 / 底部反转方向，是这道题的关键边界

下次遇到类似题目，只要看到：

  • 把元素「绕着某条路径」放到不同的桶里，最后再按桶合并
  • 路径有明显的「往下 / 往上」「往左 / 往右」周期性模式

就可以优先考虑：

  • 直接维护「若干行（桶）」而不是完整矩阵
  • 用一个 curIndex + direction 的小状态机来模拟路径

而不是上来就去构造一个二维数组，把图画得很「原始」。这种从「画图」到「抽象状态」的过程，其实就是很多模拟题背后的共性。