如何用LeetCode实现Z字形变换

发布时间：2021-10-13 10:23:36 作者：iii
来源：亿速云阅读：136

# 如何用LeetCode实现Z字形变换

## 目录
1. [问题描述](#问题描述)
2. [直观理解Z字形变换](#直观理解z字形变换)
3. [模拟法解题思路](#模拟法解题思路)
4. [数学规律法优化](#数学规律法优化)
5. [代码实现与解析](#代码实现与解析)
6. [复杂度分析](#复杂度分析)
7. [边界条件与测试案例](#边界条件与测试案例)
8. [总结与扩展](#总结与扩展)

---

## 问题描述
LeetCode第6题"ZigZag Conversion"要求将给定字符串按Z字形（或称锯齿形）排列后，按行读取返回新字符串。例如：

输入：`s = "PAYPALISHIRING"`, `numRows = 3`  
输出：`"PAHNAPLSIIGYIR"`

排列形式：

P A H N A P L S I I G Y I R


## 直观理解Z字形变换
Z字形变换的本质是将字符串按特定规律二维排布：
1. 向下填充直到第`numRows`行
2. 向右上方斜向填充直到第1行
3. 重复这个过程直到字符串结束

关键观察点：
- 当`numRows = 1`时直接返回原字符串
- 每个完整"Z"周期包含`T = 2*numRows - 2`个字符
- 斜线部分字符位置可通过数学关系确定

## 模拟法解题思路
### 基本步骤
1. 创建`numRows`个字符串数组
2. 维护当前行指针和移动方向
3. 遍历字符串时按行分配字符
4. 到达边界时反转方向

### 算法伪代码

初始化 rows[min(numRows, len(s))] 当前行 curRow = 0 方向 goingDown = False

for 字符 in s: rows[curRow] += 字符 if curRow == 0 或 curRow == numRows - 1: 反转goingDown curRow += 1 if goingDown else -1 返回 rows 按序拼接


## 数学规律法优化
### 周期规律分析
对于第`i`行（0-based）：
- 垂直列字符索引：`k * T + i`
- 斜线字符索引：`(k + 1) * T - i`

其中`T = 2*numRows - 2`，`k`为周期编号

### 数学法优势
- 无需存储中间结果
- 直接计算每个字符位置
- 时间复杂度稳定O(n)

## 代码实现与解析
### Python模拟法实现
```python
def convert(s: str, numRows: int) -> str:
    if numRows == 1:
        return s
    
    rows = [""] * min(numRows, len(s))
    curRow = 0
    goingDown = False
    
    for c in s:
        rows[curRow] += c
        if curRow == 0 or curRow == numRows - 1:
            goingDown = not goingDown
        curRow += 1 if goingDown else -1
    
    return "".join(rows)

Java数学规律法实现

public String convert(String s, int numRows) {
    if (numRows == 1) return s;
    
    StringBuilder ret = new StringBuilder();
    int n = s.length();
    int cycleLen = 2 * numRows - 2;
    
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j + i < n; j += cycleLen) {
            ret.append(s.charAt(j + i));
            if (i != 0 && i != numRows - 1 && j + cycleLen - i < n) {
                ret.append(s.charAt(j + cycleLen - i));
            }
        }
    }
    return ret.toString();
}

复杂度分析

方法	时间复杂度	空间复杂度
模拟法	O(n)	O(n)
数学规律法	O(n)	O(n)

实际测试中： - 模拟法在大多数情况下更快（现代语言字符串操作优化） - 数学法在理论分析上更优

边界条件与测试案例

特殊案例

单行情况：
```
assert convert("ABC", 1) == "ABC"
```
行数大于字符串长度：
```
assert convert("AB", 5) == "AB"
```

完整周期测试：


assert convert("PAYPALISHIRING", 4) == "PINALSIGYAHRPI"

测试策略

验证空字符串输入
检查行数边界值（1和len(s))
随机字符串压力测试

总结与扩展

核心收获

理解问题本质比立即编码更重要
多种解法对比能深化算法理解
边界条件处理是算法鲁棒性的关键

扩展思考

如何修改算法实现反向Z变换？
如果要求输出二维矩阵形式该如何修改？
对于超长字符串如何优化内存使用？

类似题目

LeetCode 68. 文本左右对齐
LeetCode 159. 至多包含两个不同字符的最长子串
LeetCode 763. 划分字母区间

“算法不是魔法，而是对问题本质的深刻理解。” —— 匿名算法大师 “`

这篇文章通过Markdown格式系统性地讲解了Z字形变换问题的解决方案，包含： 1. 多角度解题思路 2. 完整代码实现 3. 复杂度分析 4. 测试案例设计 5. 扩展思考方向

总字数约2100字，可根据需要调整具体实现代码的详细程度或增加更多可视化示例。