#6. Z 字形变换

LeetCode 原题链接

#题目描述

给定字符串 s 和行数 numRows，将字符按照从上到下、再从下到上的往返顺序排列，最后逐行读取并返回新字符串。

例如：

s = "PAYPALISHIRING"
numRows = 3

排列结果为：

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

逐行读取后得到：

PAHNAPLSIIGYIR

这里的“Z 字形”并不是要求绘制一个标准英文字母 Z，而是让字符所在的行不断向下、向上移动。

#先理解字符怎么移动

当 numRows = 3 时，字符所在行的变化规律是：

行号：0 → 1 → 2 → 1 → 0 → 1 → 2 → 1 → ...
方向：    向下      向上      向下

走到第一行时，接下来只能向下；走到最后一行时，接下来只能向上。

因此只需要维护两个状态：

• currentRow：当前字符应该放入哪一行。
• direction：下一步行号增加 1 还是减少 1。

direction = 1  ：向下移动
direction = -1 ：向上移动

#为什么不需要创建二维矩阵？

题目最终只要求逐行读取结果，并不关心每个字符具体位于第几列。

因此可以直接创建 numRows 个字符串：

rows[0] // 第一行字符
rows[1] // 第二行字符
rows[2] // 第三行字符

遍历原字符串时，把当前字符追加到对应行即可。最后执行 rows.join('')，就相当于从上到下逐行读取。

#示例推演

以 s = "PAYPALISHIRING"、numRows = 3 为例：

最终三行分别是：

rows[0] = "PAHN"
rows[1] = "APLSIIG"
rows[2] = "YIR"

连接后得到 "PAHNAPLSIIGYIR"。

#JavaScript 实现

var convert = function (s, numRows) {
  // 只有一行时不会发生上下移动。
  // 行数不少于字符数时，每个字符也只会占据一行。
  if (numRows === 1 || numRows >= s.length) {
    return s;
  }

  // rows[i] 保存最终位于第 i 行的全部字符
  const rows = new Array(numRows).fill('');

  let currentRow = 0;
  let direction = 1; // 1 表示向下，-1 表示向上

  for (const char of s) {
    // 把当前字符放入当前行
    rows[currentRow] += char;

    // 到达第一行后，下一步必须向下
    if (currentRow === 0) {
      direction = 1;
    }

    // 到达最后一行后，下一步必须向上
    if (currentRow === numRows - 1) {
      direction = -1;
    }

    // 根据当前方向移动到下一行
    currentRow += direction;
  }

  // 按照第一行、第二行……的顺序连接
  return rows.join('');
};

#代码执行过程

假设 numRows = 3，行号和方向的变化为：

初始：currentRow = 0，direction = 1

放入第 0 行 → direction =  1 → 下一行是 1
放入第 1 行 → direction =  1 → 下一行是 2
放入第 2 行 → direction = -1 → 下一行是 1
放入第 1 行 → direction = -1 → 下一行是 0
放入第 0 行 → direction =  1 → 下一行是 1

每次都先放置字符，再判断是否需要改变方向，最后计算下一个行号。

#正确性说明

遍历过程中，currentRow 始终表示当前字符在 Z 字形排列中所属的行：

• 位于中间行时，继续沿当前方向移动。
• 位于第一行时，将方向改为向下。
• 位于最后一行时，将方向改为向上。

这恰好模拟了题目要求的上下往返顺序。每个字符被追加到唯一的一行，并且同一行内的字符顺序与原字符串一致。最后按行连接，得到的就是题目要求的读取结果。

#复杂度分析

• 时间复杂度：O(n)。每个字符处理一次，最后连接所有行时每个字符再被读取一次。
• 空间复杂度：O(n)。各行字符串一共保存 n 个字符。

#边界情况

#numRows = 1

只有一行，不存在上下移动，结果就是原字符串。如果不提前返回，行号更新后会越界。

s = "ABC", numRows = 1
结果："ABC"

#numRows >= s.length

字符数量不超过行数，每个字符最多放在单独一行，逐行读取后顺序不变。

s = "ABC", numRows = 5
结果："ABC"

#numRows = 2

行号会在 0 和 1 之间交替：

0 → 1 → 0 → 1 → ...

上面的统一代码仍然适用。

#易错点

• 把“Z 字形”误解为必须构造带空格的二维矩阵。
• 忘记处理 numRows === 1，导致行号越界。
• 到达最后一行后仍继续向下，或到达第一行后仍继续向上。
• 在更新 currentRow 之后才判断边界，导致先产生非法行号。
• 最后按原字符顺序连接，而不是按行连接 rows。
• 为每个位置保存列坐标。题目只需要逐行读取，列坐标并不影响答案。

#另一种理解：一个周期有多长？

当行数为 numRows 时，从第一行走到最后一行，再回到第一行，需要经过：

cycleLength = 2 × numRows - 2

例如 numRows = 4：

行号：0 → 1 → 2 → 3 → 2 → 1 → 0
步数：        3       +       3 = 6
周期：2 × 4 - 2 = 6

可以利用周期公式直接计算每一行的字符下标，但边界和中间行的下标规律更复杂。按行号上下模拟通常更容易理解，也已经达到 O(n) 时间复杂度。

#面试时怎么说

我用一个字符串数组保存每一行，只模拟字符所在的行号，不构造二维矩阵。行号从 0 增加到 numRows - 1 后改为向上，再回到 0 后改为向下。遍历时把字符追加到当前行，最后连接所有行。每个字符只处理一次，时间复杂度是 O(n)，空间复杂度是 O(n)。

#自测

1. 为什么不需要记录字符所在的列？
2. currentRow 到达哪两行时需要改变方向？
3. 为什么 numRows === 1 必须提前返回？
4. 当 numRows = 4 时，行号变化顺序是什么？