# LeetCode如何解决Z字形变换问题 ## 目录 1. [问题描述](#问题描述) 2. [直观解法分析](#直观解法分析) 3. [优化解法思路](#优化解法思路) 4. [代码实现与解析](#代码实现与解析) 5. [复杂度分析](#复杂度分析) 6. [边界条件处理](#边界条件处理) 7. [实际应用场景](#实际应用场景) 8. [总结与扩展](#总结与扩展) ## 问题描述 <a id="问题描述"></a> Z字形变换（Zigzag Conversion）是LeetCode第6题，题目要求将给定字符串按照指定行数进行Z字形排列后，按行读取得到新字符串。 **示例：** 输入: s = “PAYPALISHIRING”, numRows = 3 输出: “PAHNAPLSIIGYIR”
排列形状： P A H N A P L S I I G Y I R
## 直观解法分析 <a id="直观解法分析"></a> ### 模拟法 1. **构建二维矩阵**：创建`numRows x n`的矩阵模拟Z字形过程 2. **填充规则**： - 向下填充：行号递增，列号不变 - 斜向上填充：行号递减，列号递增 3. **遍历方向标记**：使用布尔变量控制方向切换 **时间复杂度**：O(n²) **空间复杂度**：O(n²) ### 存在的问题 - 大量空间存储空白字符 - 不必要的矩阵遍历 ## 优化解法思路 <a id="优化解法思路"></a> ### 行追踪法（推荐） 关键观察：每个字符最终属于特定行，无需存储完整矩阵 **算法步骤：** 1. 创建`numRows`个字符串数组 2. 维护当前行和方向标志 3. 遍历字符时： - 到达首行或末行时反转方向 - 将字符放入对应行字符串 **优势：** - 空间优化至O(n) - 单次遍历完成 ## 代码实现与解析 <a id="代码实现与解析"></a> ### Python实现 ```python def convert(s: str, numRows: int) -> str: if numRows == 1 or numRows >= len(s): return s rows = [""] * numRows cur_row = 0 going_down = False for char in s: rows[cur_row] += char if cur_row == 0 or cur_row == numRows - 1: going_down = not going_down cur_row += 1 if going_down else -1 return "".join(rows) class Solution { public String convert(String s, int numRows) { if (numRows == 1) return s; List<StringBuilder> rows = new ArrayList<>(); for (int i = 0; i < Math.min(numRows, s.length()); i++) rows.add(new StringBuilder()); int curRow = 0; boolean goingDown = false; for (char c : s.toCharArray()) { rows.get(curRow).append(c); if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown; curRow += goingDown ? 1 : -1; } StringBuilder ret = new StringBuilder(); for (StringBuilder row : rows) ret.append(row); return ret.toString(); } } if numRows == 1: return s Math.min(numRows, s.length()) | 输入 | numRows | 输出 |
|---|---|---|
| “A” | 1 | “A” |
| “AB” | 3 | “AB” |
| ”” | 5 | ”” |
最后更新：2023年10月
作者：LeetCode解题专家
标签：字符串处理、算法优化、LeetCode “`
这篇文章提供了完整的解决方案框架，包含： 1. 多语言代码实现 2. 复杂度分析 3. 边界情况处理 4. 实际应用场景 5. 扩展思考方向
可根据需要调整代码示例或增加更多可视化说明（如添加ASCII示意图）。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
