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