这个问题描述的是经典的“Z字形变换”（Zigzag Conversion）问题，常出现在ACM模式或LeetCode第6题。题目要求将一个字符串按Z字形（也称之为“锯齿形”或“之字形”）排布到指定行数（numRows）的容器中，然后**按行从上到下依次拼接各行字符，输出最终字符串**。注意：题目中“依次填充容器”即指按Z字形路径逐个填入字符；“按行输出结果”即把每行的字符（从左到右）连起来，再把所有行（从第0行到第numRows-1行）顺序拼接。 --- - **正确答案**：给定字符串 s 和整数 numRows，若 numRows == 1，直接返回 s；否则模拟Z字形填充过程（无需真正构造二维数组），用 numRows 个字符串列表（或StringBuilder数组）分别记录每行内容，通过方向变量控制行索引增减，遍历 s 中每个字符，将其追加到当前行，然后更新行号和方向。最后将所有行字符串拼接返回。 --- - **解答思路**： 1. 特殊情况处理：若 numRows ≤ 1，Z形退化为单列，无需变换，直接返回原串。 2. 初始化：创建长度为 numRows 的字符串列表（如 vector rows(numRows) 或 string[] rows），用于存储每行的字符。 3. 模拟Z字形走位： - 使用 curRow 表示当前行号（初始为 0）， - 使用 goDown 表示移动方向（true 表示向下，false 表示向上）。 - 遍历每个字符 c ∈ s： • 将 c 追加到 rows[curRow]； • 若到达底行（curRow == numRows-1）则转向向上（goDown = false）； • 若到达顶行（curRow == 0）则转向向下（goDown = true）； • 根据 goDown 更新 curRow：curRow += goDown ? 1 : -1。 4. 最终将 rows[0] + rows[1] + ... + rows[numRows-1] 拼接返回。该方法时间复杂度 O(n)，空间复杂度 O(n)，避免了二维数组的显式分配与遍历，高效且直观。 --- - **深度知识讲解**： ✅ **Z字形周期性本质**： Z字形填充具有严格周期性。完整一个Z周期（从顶行→底行→回到顶行前一行）共占用 (2 * numRows - 2) 个字符（当 numRows > 1）。例如 numRows=3 → 周期 = 4；numRows=4 → 周期 = 6。可用数学分组法：对每个下标 i，计算 pos = i % cycleLen， - 若 pos < numRows，则字符属于第 pos 行； - 否则属于第 (cycleLen - pos) 行（即向上折返段）。此方法可实现O(1)空间行映射（但需预分配行容器，总体仍O(n)空间）。 ✅ **底层数据结构选择分析**： - 使用 vector 或 string[]：支持O(1)行访问，append为均摊O(1)，总构建成本O(n)； - 若用 vector>：内存局部性略差，且需额外resize，不必要； - 不推荐用二维char数组+memset：C风格难维护，且numRows可能为0（需防御）。 ✅ **边界鲁棒性考点**： - numRows = 0？按题意应视为非法输入，但工业代码需断言或抛异常； - numRows = 1 → 周期公式 2*1-2 = 0，不可取模，故必须前置特判； - 空字符串 s = "" → 循环不执行，各rows为空，拼接后仍为""，自然满足。 ✅ **与“蛇形矩阵”区别**：此题是**一维字符串映射到Z形路径**，非二维网格填数；蛇形矩阵通常按行列边界转向，而Z形仅由行边界（0 和 numRows-1）触发转向，路径更简单。 --- - **C++ 代码实现（ACM模式标准写法，含输入输出）**： ``` #include #include #include using namespace std; string convert(string s, int numRows) { if (numRows <= 1) return s; vector rows(min(numRows, (int)s.size()), ""); int curRow = 0; bool goDown = false; for (char c : s) { rows[curRow] += c; if (curRow == 0 || curRow == numRows - 1) { goDown = !goDown; } curRow += goDown ? 1 : -1; } string res; for (string& row : rows) { res += row; } return res; } int main() { string s; int numRows; getline(cin, s); cin >> numRows; cout << convert(s, numRows) << endl; return 0; } ``` - **Python 简洁版（面试手写友好）**： ``` def convert(s: str, numRows: int) -> str: if numRows <= 1: return s rows = [''] * numRows cur_row = 0 go_down = False for c in s: rows[cur_row] += c if cur_row == 0 or cur_row == numRows - 1: go_down = not go_down cur_row += 1 if go_down else -1 return ''.join(rows) ``` - **测试用例验证**：输入：s = "PAYPALISHIRING", numRows = 3 Z形布局： P A H N A P L S I I G Y I R 按行读取 → "PAHNAPLSIIGYIR" 输出："PAHNAPLSIIGYIR" ✔ 输入：s = "A", numRows = 1 → 输出 "A" ✔ --- - **扩展知识点**： ▪ 可进一步优化为只用O(min(numRows, n))空间（已是最优）； ▪ 若要求**原地变换**（in-place），则仅当字符可随机访问且允许重排时可行，但本题输出顺序已非原序，无通用原地解； ▪ 工程中可加 early-return：若 s.length() <= numRows || numRows == 1，直接返回； ▪ Unicode 安全性：上述代码在C++中假设ASCII；若需支持UTF-8多字节字符，应先转为Unicode码点序列再处理（Python str默认Unicode，天然安全）。此题综合考察：边界分析能力、状态机建模（方向+位置）、周期性抽象、空间优化意识，是校招中识别候选人基本功的经典题型。

2027美少年实习生-后端java笔试

全站热榜

创作者周榜