一、题目描述
题目链接：LeetCode 6. Z 字形变换
题目要求
将字符串s按指定行数numRows排成Z 字形（先从上到下，再从右到左斜向上），然后从左到右逐行读取，输出新字符串。
示例演示
- 输入：
s = "PAYPALISHIRING", numRows = 3 - Z 字形排列：
plaintext
P A H N A P L S I I G Y I R- 输出：
"PAHNAPLSIIGYIR"
二、解题思路：Z 字的 “周期” 与 “方向”
要解决这道题，首先得搞懂 Z 字形的排列规律：
1. 周期规律
Z 字形的每一个 “完整折回” 是一个周期，周期长度为：t=2×numRows−2（比如numRows=3时，周期t=4：向下 3 个字符 + 斜向上 2 个字符）
2. 方向切换
在一个周期内，字符的移动方向分两种：
- 前
numRows-1个字符：垂直向下（行 + 1）； - 后
numRows-2个字符：斜向上（行 - 1，列 + 1）。
3. 核心解题步骤
我们用模拟矩阵法实现（直观易懂）：
- 处理特殊情况（行数为 1 / 行数≥字符串长度）；
- 计算周期和矩阵的行列数；
- 模拟 Z 字路径，将字符填充到矩阵中；
- 逐行读取矩阵，拼接成结果字符串。
三、图解过程（以示例 1 为例）
以s="PAYPALISHIRING", numRows=3为例：
步骤 1：计算周期和矩阵大小
- 周期
t=2×3-2=4； - 字符串长度
n=14，总周期数为(14+4-1)/4=4（向上取整）； - 矩阵列数
c=4×(3-1)=8（每个周期占 2 列）。
步骤 2：填充矩阵
遍历字符串，按方向填充字符：
- 第 1 个字符
P：坐标 (0,0)，向下移动→行 + 1； - 第 2 个字符
A：坐标 (1,0)，向下移动→行 + 1； - 第 3 个字符
Y：坐标 (2,0)，进入周期后半段→斜向上（行 - 1，列 + 1）； - 第 4 个字符
P：坐标 (1,1)，斜向上→行 - 1，列 + 1； - 以此类推，直到填充完所有字符。
步骤 3：逐行读取
矩阵填充完成后，逐行拼接非空字符：
- 第 0 行：
P A H N→ 拼接为PAHN； - 第 1 行：
A P L S I I G→ 拼接为APLSIIG； - 第 2 行：
Y I R→ 拼接为YIR； - 最终结果：
PAHNAPLSIIGYIR。
四、代码细节说明
特殊情况处理：当行数为 1 时，Z 字就是原字符串；当行数≥字符串长度时，无法形成 Z 字，直接返回原串。
矩阵大小计算：
- 周期
t：Z 字每 “一折” 的字符数； - 列数
c：通过 “向上取整” 计算总周期数，再乘以每个周期的列数r-1。
- 周期
方向控制：用
i % t判断当前字符在周期中的位置：i%t < r-1：周期前半段，向下移动（行 + 1）；- 否则：周期后半段，斜向上移动（行 - 1，列 + 1）。
五、复杂度分析
- 时间复杂度：O(r×c)填充矩阵和拼接结果的时间，
r是行数，c是列数，均与字符串长度呈线性关系。 - 空间复杂度：O(r×c)存储矩阵的空间，可优化为O(n)（直接按行存储字符，无需完整矩阵）。
六、优化思路（空间 O (n)）
如果想优化空间，可放弃完整矩阵构建，直接按行存储字符：
- 定义行数对应的字符串数组，遍历原字符串时直接将字符追加到对应行；
- 到达行首 / 行尾时切换移动方向，避免矩阵的空间浪费；
- 最终将各行字符串拼接即可得到结果，空间复杂度可降至O(n)。
