leetcode如何解决Z字形变换问题

# 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)

Java实现

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();
    }
}

关键点解析

1. 方向切换逻辑：通过布尔变量控制行号增减
2. 特殊处理单行情况：直接返回原字符串
3. 字符串拼接优化：避免频繁字符串操作

复杂度分析

时间复杂度

• 最优情况：O(n) （单次遍历）
• 每个字符仅处理一次

空间复杂度

• 存储开销：O(n) （存储结果字符串）
• 额外行存储空间与行数相关

边界条件处理

特殊用例处理

1. 单行情况：

   
   if numRows == 1:
      return s
   

2. 字符串短于行数：

   
   Math.min(numRows, s.length())
   

3. 空字符串输入：直接返回空串

测试用例验证

实际应用场景

密码学应用

• 古典密码中的栅栏密码（Rail Fence Cipher）
• 数据加密的预处理步骤

文本显示优化

• 大屏幕文字排版
• 有限高度下的长文本展示

数据压缩

• 特定模式下的数据重组
• 传输前的数据格式转换

总结与扩展

核心收获

1. 模式识别：发现Z字形遍历的数学规律
2. 空间优化：避免不必要的数据存储
3. 方向控制：状态标记简化逻辑

相似题目

1. 螺旋矩阵（方向控制应用）
2. 对角线遍历（类似方向切换）

进阶思考

• 如何实现反向转换（给定Z字形输出恢复原字符串）？
• 三维Z字形变换如何处理？

最后更新：2023年10月
作者：LeetCode解题专家
标签：字符串处理、算法优化、LeetCode “`

这篇文章提供了完整的解决方案框架，包含： 1. 多语言代码实现 2. 复杂度分析 3. 边界情况处理 4. 实际应用场景 5. 扩展思考方向

可根据需要调整代码示例或增加更多可视化说明（如添加ASCII示意图）。