Z 字形变换

关键就两个状态:当前行 cur 和 方向 step(+1 往下 / −1 往上)。碰到顶行或底行就掉头。盯住下面格子里字母怎么走位。

空格子 · 3 行 × 7 列：先摆好 3 行的空格子(列数够用就行)。指针停在 第 0 行,方向往下,准备填第一个字母 P。

填 P · 第 0 行：把 P 放进 (行0, 列0)。现在在顶行,方向是往下 +1,下一格去第 1 行。

填 A · 第 1 行：竖着往下,A 放进 (行1, 列0)。还没到底,继续往下。

填 Y · 第 2 行(到底!)：Y 放进 (行2, 列0)——到最后一行了!方向要掉头变成往上 −1,而且斜着走时列要 +1。

填 P · 斜着往上：掉头往上!P 走到 (行1, 列1)——行号减 1、列号加 1,这就是 Z 字的斜笔。

填 A · 回到顶行：A 走到 (行0, 列2)——又撞到顶行了!方向再掉头变回往下 +1,接下来又是竖着走。

填 L · 往下：竖着往下,L 放进 (行1, 列2)。注意列号不变——竖着走时同一列往下叠。

填 I · 第 2 行(到底)：I 放进 (行2, 列2),又到底了。掉头往上,下一步斜着走、列再 +1。

填 S · 斜着往上：斜笔!S 走到 (行1, 列3)。行减 1、列加 1。

填 H · 回到顶行：H 走到 (行0, 列4),撞顶,再次掉头往下。Z 字就是这样一上一下来回织。

填 I · 往下：竖着往下,I 放进 (行1, 列4)。

填 R · 第 2 行(到底)：R 放进 (行2, 列4),到底,掉头往上。

填 I · 斜着往上：斜笔,I 走到 (行1, 列5)。还剩两个字母 N、G。

填 N · 回到顶行：N 走到 (行0, 列6),撞顶,掉头往下。

填 G · 最后一个：最后一个 G 往下放进 (行1, 列6)。14 个字母全部按 Z 字填完了!下面开始一行一行读出来。

Z 字织好 · 准备逐行读：退一步看整张图:字母的轨迹正是一笔一笔的 Z 字(竖下→斜上→竖下…)。原串顺序已经被打散到各行,接下来从上到下逐行读出来就是答案。

读第 0 行：从第 0 行从左到右收字母:P、A、H、N → 拿到 "PAHN"。空格子直接跳过。

读第 1 行：再读第 1 行:A、P、L、S、I、I、G → 接上变成 "PAHN" + "APLSIIG"。中间行字母最多,因为斜笔都落在这。

读第 2 行 · 拼完：最后读第 2 行:Y、I、R → 全拼起来 PAHN + APLSIIG + YIR = PAHNAPLSIIGYIR,正是答案!

省内存的写法:不存格子,只存 numRows 个行串。指针在行间来回走,字母追加到对应行串,走到顶/底就翻转方向。

雷区实演 · numRows = 1：若 numRows=1,所有字母都挤在同一行,顶行就是底行、方向永远翻不过来。所以必须开头特判,直接原样返回 s(ABCDEF→ABCDEF)。

边界三连：先想一行(特判)、行数比字符还多(排成一竖列)、最小串三种,代码就稳了。

面试追问：把「按行追加省空间」「O(n)」「方向翻转怎么定行号」讲清楚,是这题面试的得分点。