LeetCode 6. Z 字形变换

题意与示例

完整题目见官方页面（链接在文末）。前几组基准用例和结果由一个独立的做法算出（不模拟来回走，而是用周期公式直接算出每一行包含哪些下标）。一共 10 组，覆盖：一行、行数等于或大于字符串长度、行数为 2 这种最简单的折返、含标点：

真实实测 · 本机执行输出

输入 ["PAYPALISHIRING",3]
输出 "PAHNAPLSIIGYIR"
输入 ["PAYPALISHIRING",4]
输出 "PINALSIGYAHRPI"
输入 ["A",1]
输出 "A"
输入 ["AB",1]
输出 "AB"
输入 ["AB",2]
输出 "AB"
输入 ["ABCD",2]
输出 "ACBD"

陷阱：只有一行时，行号无法"弹回"

行号往下走到最后一行（numRows - 1）就掉头向上，走回第 0 行再掉头向下。当 numRows = 1 时，第 0 行既是顶也是底，判断"到顶"和"到底"同时成立，写成 if ... elif ... 时只会执行第一个分支，行号就会越走越大，一直超出范围。下面是没有单独处理这种情况的写法的真实结果：

真实实测 · 本机执行输出

# 没有单独处理 numRows == 1 的写法
bad("AB", 1) -> 抛出 IndexError: list index out of range   solve -> "AB"
bad("ABCD", 2) -> "ACBD"   solve -> "ACBD"

numRows = 1 直接抛出 IndexError。这个输入在官方示例里就有，所以这个遗漏很容易被发现；而 numRows = 2 时不会出错，因为顶和底是不同的两行。处理方法是：numRows = 1 时直接返回原字符串（只有一行，读出来就是原样）。

逐字符落行：五种语言的实现

维护一个行号 r 和一个方向 step（+1 向下，-1 向上）：每读入一个字符，追加到第 r 行的末尾；如果 r 到了第 0 行就把 step 设为 +1，到了最后一行就设为 -1，然后 r += step。最后把各行依次拼接。时间和空间都是 O(n)。Python 用列表的列表，Java 用 StringBuilder 数组，Go 用 strings.Builder 切片，JavaScript 用数组，C++ 用 string 的数组，五种语言都是真实编译运行的。

Python · 解法代码def solve(s, num_rows): if num_rows == 1: # 只有一行时不存在"折返"，直接返回 return s rows = [[] for _ in range(num_rows)] r, step = 0, 1 for ch in s: rows[r].append(ch) if r == 0: step = 1 # 到顶了，向下 elif r == num_rows - 1: step = -1 # 到底了，向上 r += step return "".join("".join(row) for row in rows)

真实实测 · Python · 前几组用例的输出

$ python3 solution.py   # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON
["PAYPALISHIRING",3]  →  "PAHNAPLSIIGYIR"
["PAYPALISHIRING",4]  →  "PINALSIGYAHRPI"
["A",1]  →  "A"
["AB",1]  →  "AB"
["AB",2]  →  "AB"
["ABCD",2]  →  "ACBD"

Java · 解法代码class Solution { public String convert(String s, int numRows) { if (numRows == 1) return s; // 只有一行时不存在"折返" StringBuilder[] rows = new StringBuilder[numRows]; for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder(); int r = 0, step = 1; for (int i = 0; i < s.length(); i++) { rows[r].append(s.charAt(i)); if (r == 0) step = 1; // 到顶，向下 else if (r == numRows - 1) step = -1; // 到底，向上 r += step; } StringBuilder out = new StringBuilder(); for (StringBuilder row : rows) out.append(row); return out.toString(); } }

真实实测 · Java · 前几组用例的输出

$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl
["PAYPALISHIRING",3]  →  "PAHNAPLSIIGYIR"
["PAYPALISHIRING",4]  →  "PINALSIGYAHRPI"
["A",1]  →  "A"
["AB",1]  →  "AB"
["AB",2]  →  "AB"
["ABCD",2]  →  "ACBD"

Go · 解法代码func convert(s string, numRows int) string { if numRows == 1 { // 只有一行时不存在"折返" return s } rows := make([]strings.Builder, numRows) r, step := 0, 1 for i := 0; i < len(s); i++ { rows[r].WriteByte(s[i]) if r == 0 { step = 1 // 到顶，向下 } else if r == numRows-1 { step = -1 // 到底，向上 } r += step } var out strings.Builder for i := range rows { out.WriteString(rows[i].String()) } return out.String() }

真实实测 · Go · 前几组用例的输出

$ go build -o bin . && ./bin < cases.jsonl
["PAYPALISHIRING",3]  →  "PAHNAPLSIIGYIR"
["PAYPALISHIRING",4]  →  "PINALSIGYAHRPI"
["A",1]  →  "A"
["AB",1]  →  "AB"
["AB",2]  →  "AB"
["ABCD",2]  →  "ACBD"

JavaScript · 解法代码function convert(s, numRows) { if (numRows === 1) return s; // 只有一行时不存在"折返" const rows = Array.from({ length: numRows }, () => []); let r = 0, step = 1; for (const ch of s) { rows[r].push(ch); if (r === 0) step = 1; // 到顶，向下 else if (r === numRows - 1) step = -1; // 到底，向上 r += step; } return rows.map((row) => row.join('')).join(''); }

真实实测 · JavaScript · 前几组用例的输出

$ node run.js < cases.jsonl
["PAYPALISHIRING",3]  →  "PAHNAPLSIIGYIR"
["PAYPALISHIRING",4]  →  "PINALSIGYAHRPI"
["A",1]  →  "A"
["AB",1]  →  "AB"
["AB",2]  →  "AB"
["ABCD",2]  →  "ACBD"

C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { public: string convert(string s, int numRows) { if (numRows == 1) return s; // 只有一行时不存在"折返" vector<string> rows(numRows); int r = 0, step = 1; for (char ch : s) { rows[r] += ch; if (r == 0) step = 1; // 到顶，向下 else if (r == numRows - 1) step = -1; // 到底，向上 r += step; } string out; for (auto& row : rows) out += row; return out; } };

真实实测 · C++ · 前几组用例的输出

$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl
["PAYPALISHIRING",3]  →  "PAHNAPLSIIGYIR"
["PAYPALISHIRING",4]  →  "PINALSIGYAHRPI"
["A",1]  →  "A"
["AB",1]  →  "AB"
["AB",2]  →  "AB"
["ABCD",2]  →  "ACBD"

真实实测 · 本机执行输出

共 10 组用例（含边界），以暴力解的结果为基准逐组比对：
  Python      通过 10/10
  Java        通过 10/10
  Go          通过 10/10
  JavaScript  通过 10/10
  C++         通过 10/10

随机对拍

Python 版本另外和暴力解（周期公式）做了随机对拍：

真实实测 · 本机执行输出

随机对拍 10000 组（长度 1 到 40 的随机字符串（字母加逗号句号）、行数 1 到 9；行数经常大于字符串长度或恰好等于长度），solve 与 brute 的结果全部一致。

另外四种语言只在上面 10 组固定用例上验证过，其中包含行数为 1、行数大于字符串长度的用例，没有做大规模随机对拍。

分步演示：字符怎么落进各行

下面的演示用 s = "PAYPALISHIRING"、numRows = 3。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的字符串与 solve 的返回值一致。右侧的每一行会随着字符落入而增长，最后按行拼接就是答案。

Z 字形变换：s = "PAYPALISHIRING"，numRows = 3

正在放置的字符 / 当前所在行已经放置

参考与说明

官方题目页：LeetCode 6. Z 字形变换。本文只用自己的话概括了题意，完整约束以官方页面为准。
数据来自本机真实运行，五种语言的版本写在页脚。
没有覆盖：直接用周期公式（2 * (numRows - 1)）按行取下标的做法本文只用它做了核对基准，没有当作正式解法展开；字符串含多字节字符时，Go 和 C++ 按字节处理会拆开字符，本文按题目约束只考虑 ASCII。

下一题 · LeetCode 7

整数反转