1 中文题目

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING"行数为 3 时，排列如下：

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

之后需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
说明：

示例 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\le s.length\le 1000$
• s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成
• $1\le numRows\le 1000$

---

2 求解思路

2.1 基础解法：模拟法

思路
使用多个数组模拟Z字形走位，按照向下和向上两个方向交替移动，在首行和末行时改变移动方向。 模拟的规则：从上到下填充字符时，行号增加；从下到上填充字符时，行号减少；在第一行时向下移动；在最后一行时向上移动。

步骤1: 初始化

• 创建numRows个空数组，每个数组对应一行
• 初始化当前行号和移动方向

步骤2: 遍历字符

• 将每个字符放入对应行的数组中
• 根据当前位置更新移动方向
• 更新当前行号

步骤3: 合并结果

• 将所有行的字符合并成最终字符串

Python代码

python">class Solution:def convert(self, s: str, numRows: int) -> str:"""Z字形变换的模拟法实现Args:s: 输入字符串numRows: 指定的行数Returns:按Z字形变换后的字符串示例:输入: s = "PAYPALISHIRING", numRows = 3过程: P   A   H   NA P L S I I GY   I   R输出: "PAHNAPLSIIGYIR""""# 特殊情况处理：当行数为1或字符串长度小于行数时if numRows == 1 or numRows >= len(s):return s# 初始化numRows个空字符串数组，用于存储每行的字符rows = [[] for _ in range(numRows)]# 当前行号（表示当前字符应该放在第几行）curr_row = 0# 移动方向（1表示向下，-1表示向上）step = 1# 遍历字符串中的每个字符for char in s:# 将当前字符添加到对应行rows[curr_row].append(char)# 在首行或末行时需要改变移动方向if curr_row == 0:  # 当前在第一行step = 1  # 改为向下移动elif curr_row == numRows - 1:  # 当前在最后一行step = -1  # 改为向上移动# 更新当前行号curr_row += step# 合并所有行的字符形成最终结果# 先将每一行的字符数组合并成字符串，再将所有行的字符串连接return ''.join(''.join(row) for row in rows)

时空复杂度分析

• 时间复杂度：$O(n)$
  • 遍历字符串一次：$O(n)$，其中$n$为字符串长度
  • 合并结果时再次遍历：$O(n)$

总体时间复杂度：$O(n)$

• 空间复杂度：$O(n)$
  • $rows$数组：$O(numRows)$个数组。虽然使用了$numRows$个数组，但所有数组中存储的字符总数仍然是$n$
  • 其他变量：$O(1)$

总体空间复杂度：$O(n)$

---

2.2 优化解法：数学规律法

思路

蓝框中表示一个周期，蓝框中的字符数即为周期长度。

周期长度 = 2 * numRows - 2

• 向下移动需要 numRows 步
• 向上移动需要 numRows - 2 步（不包括首尾行）
• 总步数 cycle= numRows + (numRows - 2) = 2 * numRows - 2

位置的规律：

• 首行(i=0)和末行(i=numRows-1)：
  • 字符位置：k * cycle ，其中k为周期序号(0, 1, 2, …)
• 中间行：（中间的行，每一行一个周期内只有2个字符）
  • 第一个字符位置：k * cycle + i
  • 第二个字符位置：k * cycle + (cycle - i)
• 末行(i=numRows-1)：
  • 字符位置：k * cycle + i，其中k为周期序号(0, 1, 2, …)

示例：

对于 numRows = 4 的情况，设周期序号为k：

python">第0行(i=0)：
- 字符位置：6k     (k=0,1,2,...)
- 实际位置：0, 6, 12, ...第1行(i=1)：
- 第一个字符位置：6k + 1   (k=0,1,2,...)
- 第二个字符位置：6k + 5   (k=0,1,2,...)
- 实际位置：1, 5, 7, 11, 13, ...第2行(i=2)：
- 第一个字符位置：6k + 2   (k=0,1,2,...)
- 第二个字符位置：6k + 4   (k=0,1,2,...)
- 实际位置：2, 4, 8, 10, 14, ...第3行(i=3)：
- 字符位置：6k + 3     (k=0,1,2,...)
- 实际位置：3, 9, 15, ...

python代码

python">class Solution:def convert(self, s: str, numRows: int) -> str:"""使用数学方法实现Z字形变换核心思想：1. 找出Z字形排列的周期规律2. 通过数学公式直接计算每个字符在结果中的位置参数说明：s: 输入字符串numRows: Z字形的行数示例分析：对于 numRows = 4 的情况：周期 = 2 * numRows - 2 = 6P     I    NA   L S  I GY A   H RP     I规律分析：第0行: 0,     6,     12    -> 间隔6 (周期)第1行: 1,   5,7,   11,13   -> 间隔4,2,4,2第2行: 2, 4, 8,10, 14      -> 间隔2,4,2,4第3行: 3,     9,     15    -> 间隔6 (周期)"""# 特殊情况处理if numRows == 1 or numRows >= len(s):return s# 计算周期长度cycle = 2 * numRows - 2# 存储结果result = []# 遍历每一行for i in range(numRows):# 遍历每个周期的起始位置for j in range(0, len(s), cycle):# 添加当前周期的第一个字符（如果存在）if j + i < len(s):result.append(s[j + i])# 对于中间行（非首尾行），添加当前周期的第二个字符（如果存在）if i != 0 and i != numRows - 1:  # 不是首行也不是末行# 计算当前周期中第二个字符的位置second_pos = j + cycle - iif second_pos < len(s):result.append(s[second_pos])# 合并所有字符return ''.join(result)

时空复杂度分析

• 时间复杂度
  • 外层循环：遍历每一行O(numRows)
  • 内层循环：每行处理约 n/cycle个字符

总的字符处理数量仍然是 n，因此总时间复杂度为 O(n)

• 空间复杂度
  • 结果数组：存储所有字符，O(n)
  • 其他变量：O(1)

总空间复杂度：O(n)

---

2.3 最优解法：字符串拼接法

思路
把Z字形看作是在若干行之间来回移动的过程，记录每一行的字符，最后拼接起来。具体实现步骤

• 初始化
  • 创建numRows个空字符串，每个字符串对应一行
  • 设置当前行号curRow = 0
  • 设置移动方向step = 1（1表示向下，-1表示向上）
• 遍历原字符串
  • 把当前字符添加到当前行对应的字符串中
  • 根据当前位置更新移动方向：
    • 到达第一行(curRow = 0)时，向下移动(step = 1)
    • 到达最后一行(curRow = numRows-1)时，向上移动(step = -1)
  • 更新当前行号：curRow += step
• 合并结果
  • 将所有行的字符串按从上到下的顺序拼接起来

示例
以字符串 “PAYPALISHIRING” 和 numRows = 4 为例：

python">初始状态：
row[0] = ""
row[1] = ""
row[2] = ""
row[3] = ""逐字符处理：
P: 放入第0行，向下移动
row[0] = "P"
row[1] = ""
row[2] = ""
row[3] = ""A: 放入第1行，继续向下
row[0] = "P"
row[1] = "A"
row[2] = ""
row[3] = ""Y: 放入第2行，继续向下
row[0] = "P"
row[1] = "A"
row[2] = "Y"
row[3] = ""P: 放入第3行，改为向上移动
row[0] = "P"
row[1] = "A"
row[2] = "Y"
row[3] = "P"A: 放入第2行，继续向上
row[0] = "P"
row[1] = "A"
row[2] = "YA"
row[3] = "P"...以此类推

python代码

python">class Solution:def convert(self, s: str, numRows: int) -> str:"""使用字符串拼接法实现Z字形变换核心思想：1. 创建numRows个字符串，分别对应每一行2. 遍历原字符串，将每个字符追加到对应行的字符串中3. 设置方向标志，在到达边界时改变方向4. 最后将所有行的字符串拼接起来参数说明：s: 输入字符串numRows: Z字形的行数返回值：返回Z字形变换后的字符串"""# 特殊情况处理if numRows == 1 or numRows >= len(s):return s# 初始化每一行的字符串rows = [''] * numRows# 当前行号cur_row = 0# 移动方向，1表示向下，-1表示向上step = 1# 遍历每个字符for c in s:# 将当前字符添加到对应行rows[cur_row] += c# 在首行时向下移动if cur_row == 0:step = 1# 在末行时向上移动elif cur_row == numRows - 1:step = -1# 更新当前行号cur_row += step# 合并所有行的字符串return ''.join(rows)

时空复杂度分析

• 时间复杂度：O(n)
  • 遍历字符串一次：O(n)
  • 字符串拼接操作：O(1)
  • 最后合并所有行：O(n)
• 空间复杂度：O(n)
  • rows数组：存储n个字符，O(n)
  • 其他变量：O(1)

---

3 题目总结

题目难度：中等
数据结构： 字符串
应用算法： 数学规律