Z 字形变换（Zigzag Conversion）

Z 字形变换

题目描述

https://leetcode.cn/problems/zigzag-conversion/

将一个给定字符串 s 根据给定的行数 numRows，以从上往下、从左到右进行 Z 字形排列，之后逐行读取产生新的字符串。

解题思路

核心观察

Z 字形变换的周期为 t = 2 * numRows - 2。字符按周期向下移动，遇到第一行或最后一行时反向移动到右上。

算法步骤

1. 处理边界情况：numRows == 1 或 numRows >= len(s)
2. 用列表数组存储每行的字符
3. 遍历字符串，根据周期位置决定当前行号
4. 按行拼接所有字符

代码实现

import sys
from itertools import chain

s = sys.stdin.readline().strip()
numRows = int(sys.stdin.readline().strip())

if numRows == 1 or numRows >= len(s):
    print(s)
    exit()

mat = [[] for _ in range(numRows)]
t = numRows * 2 - 2
x = 0
for i, ch in enumerate(s):
    mat[x].append(ch)
    if i % t < numRows - 1:
        x += 1
    else:
        x -= 1

print(''.join(chain(*mat)))

代码解析

• mat：numRows 个列表，分别存储每行的字符
• t：Z 字形周期 = 2 * numRows - 2
• x：当前行号，周期前半段向下移动（x += 1），后半段向上移动（x -= 1）
• ''.join(chain(*mat))：将二维列表展平后拼接成字符串

时间复杂度

• 遍历字符串：O(n)
• 拼接结果：O(n)
• 总计：O(n)