6. Z 字形变换

题目描述

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = “PAYPALISHIRING”, numRows = 3
输出：“PAHNAPLSIIGYIR”

示例 2：

输入：s = “PAYPALISHIRING”, numRows = 4
输出：“PINALSIGYAHRPI”
解释：
P I N
A L S I G
Y A H R
P I

示例 3：

输入：s = “A”, numRows = 1
输出：“A”

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成
• 1 <= numRows <= 1000

解题思路

这道题要求将字符串按Z字形排列，然后按行读取。这是一个字符串处理的经典问题。

算法分析

这道题的核心思想是模拟Z字形排列过程，主要解法包括：

1. 模拟法：实际构建Z字形矩阵，然后按行读取
2. 方向控制法：使用方向变量控制字符放置的行数
3. 数学规律法：利用Z字形的数学规律直接计算字符位置

问题本质分析

Z字形排列过程详解

Z字形排列可视化

方向控制策略

数学规律法详解

各种解法对比

算法流程图

flowchart TDA[开始] --> B{numRows == 1?}B -->|是| C[直接返回原字符串]B -->|否| D{numRows >= len(s)?}D -->|是| CD -->|否| E[创建numRows个字符串构建器]E --> F[初始化currentRow=0, direction=1]F --> G[遍历字符串字符]G --> H[将字符添加到当前行]H --> I[更新行索引]I --> J{到达边界?}J -->|是| K[改变方向]J -->|否| L{还有字符?}K --> LL -->|是| GL -->|否| M[按行连接结果]M --> N[返回最终字符串]C --> O[结束]N --> O

边界情况处理

graph TDA[边界情况] --> B[numRows = 1]A --> C[numRows >= len(s)]A --> D[空字符串]A --> E[单字符字符串]B --> F[直接返回原字符串]C --> FD --> G[返回空字符串]E --> H[正常处理]F --> I[避免不必要的计算]G --> IH --> I

时间复杂度分析

空间复杂度分析

关键优化点

实际应用场景

测试用例设计

graph TDA[测试用例] --> B[基础功能]A --> C[边界情况]A --> D[性能测试]B --> E[多行Z字形]B --> F[单行情况]B --> G[不同字符串长度]C --> H[numRows = 1]C --> I[numRows >= len(s)]C --> J[空字符串]D --> K[最大长度字符串]D --> L[最大行数]E --> M[验证正确性]F --> MG --> MH --> MI --> MJ --> MK --> N[验证性能]L --> N

代码实现要点

1. 方向控制逻辑：

   • 使用direction变量控制行索引变化
   • 在边界处改变方向

2. 字符串构建器：

   • 使用strings.Builder提高效率
   • 避免频繁的字符串拼接

3. 边界条件处理：

   • numRows = 1时直接返回
   • numRows >= len(s)时直接返回

4. 行索引管理：

   • 当前行索引范围：0 到 numRows-1
   • 方向改变条件：到达顶部或底部

5. 结果构建：

   • 按行顺序连接所有行的内容
   • 使用strings.Builder提高效率

这个问题的关键在于理解Z字形的排列规律和掌握方向控制技巧，通过模拟Z字形的填充过程，实现字符串的重排和重组。

完整题解代码

package mainimport ("fmt""strings"
)// convert Z字形变换
// 时间复杂度: O(n)，其中n是字符串长度
// 空间复杂度: O(n)
func convert(s string, numRows int) string {if numRows == 1 || numRows >= len(s) {return s}// 创建numRows个字符串构建器rows := make([]strings.Builder, numRows)// 当前行索引和方向currentRow := 0direction := 1 // 1表示向下，-1表示向上// 遍历字符串，按Z字形填充for _, char := range s {// 将当前字符添加到当前行rows[currentRow].WriteByte(byte(char))// 更新行索引currentRow += direction// 如果到达边界，改变方向if currentRow == 0 || currentRow == numRows-1 {direction = -direction}}// 将所有行连接起来var result strings.Builderfor _, row := range rows {result.WriteString(row.String())}return result.String()
}// convertOptimized 优化版本，使用数学规律
// 时间复杂度: O(n)
// 空间复杂度: O(n)
func convertOptimized(s string, numRows int) string {if numRows == 1 || numRows >= len(s) {return s}var result strings.Buildern := len(s)// 第一行和最后一行的字符间隔cycleLen := 2*numRows - 2// 逐行构建结果for row := 0; row < numRows; row++ {for i := row; i < n; i += cycleLen {// 添加垂直方向的字符result.WriteByte(s[i])// 如果不是第一行和最后一行，还需要添加斜向的字符if row != 0 && row != numRows-1 {// 计算斜向字符的位置diagonalIndex := i + cycleLen - 2*rowif diagonalIndex < n {result.WriteByte(s[diagonalIndex])}}}}return result.String()
}// convertSimulation 模拟法：实际构建Z字形矩阵
// 时间复杂度: O(n)
// 空间复杂度: O(n*numRows)
func convertSimulation(s string, numRows int) string {if numRows == 1 || numRows >= len(s) {return s}// 创建Z字形矩阵matrix := make([][]byte, numRows)for i := range matrix {matrix[i] = make([]byte, 0)}currentRow := 0direction := 1// 填充矩阵for _, char := range s {matrix[currentRow] = append(matrix[currentRow], byte(char))currentRow += directionif currentRow == 0 || currentRow == numRows-1 {direction = -direction}}// 按行读取结果var result strings.Builderfor _, row := range matrix {result.Write(row)}return result.String()
}func main() {// 测试用例1s1 := "PAYPALISHIRING"numRows1 := 3result1 := convert(s1, numRows1)fmt.Printf("示例1: s = \"%s\", numRows = %d\n", s1, numRows1)fmt.Printf("输出: \"%s\"\n", result1)fmt.Printf("期望: \"PAHNAPLSIIGYIR\"\n")fmt.Printf("结果: %t\n", result1 == "PAHNAPLSIIGYIR")fmt.Println()// 测试用例2s2 := "PAYPALISHIRING"numRows2 := 4result2 := convert(s2, numRows2)fmt.Printf("示例2: s = \"%s\", numRows = %d\n", s2, numRows2)fmt.Printf("输出: \"%s\"\n", result2)fmt.Printf("期望: \"PINALSIGYAHRPI\"\n")fmt.Printf("结果: %t\n", result2 == "PINALSIGYAHRPI")fmt.Println()// 测试用例3s3 := "A"numRows3 := 1result3 := convert(s3, numRows3)fmt.Printf("示例3: s = \"%s\", numRows = %d\n", s3, numRows3)fmt.Printf("输出: \"%s\"\n", result3)fmt.Printf("期望: \"A\"\n")fmt.Printf("结果: %t\n", result3 == "A")fmt.Println()// 额外测试用例s4 := "AB"numRows4 := 1result4 := convert(s4, numRows4)fmt.Printf("额外测试: s = \"%s\", numRows = %d\n", s4, numRows4)fmt.Printf("输出: \"%s\"\n", result4)fmt.Printf("期望: \"AB\"\n")fmt.Printf("结果: %t\n", result4 == "AB")fmt.Println()// 测试优化版本fmt.Println("=== 优化版本测试 ===")result1Opt := convertOptimized(s1, numRows1)result2Opt := convertOptimized(s2, numRows2)fmt.Printf("优化版本示例1: %s\n", result1Opt)fmt.Printf("优化版本示例2: %s\n", result2Opt)fmt.Printf("结果一致: %t\n", result1Opt == result1 && result2Opt == result2)fmt.Println()// 测试模拟版本fmt.Println("=== 模拟版本测试 ===")result1Sim := convertSimulation(s1, numRows1)result2Sim := convertSimulation(s2, numRows2)fmt.Printf("模拟版本示例1: %s\n", result1Sim)fmt.Printf("模拟版本示例2: %s\n", result2Sim)fmt.Printf("结果一致: %t\n", result1Sim == result1 && result2Sim == result2)
}