Python面试宝典第17题：Z字形变换

题目

        将一个给定字符串 s 根据给定的行数numRows ，以从上往下、从左到右进行Z字形排列。比如：输入字符串为"PAYPALISHIRING"，行数为3时，排列如下。最后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

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

        示例 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"

模拟生成法

        模拟生成法通过直接模拟Z字形路径的构建过程来求解，其基本思路为：创建一个二维数组来存储每行的字符，根据Z字形的移动规律填充字符。对于每一列，从上到下再从下到上交替填充字符，直到所有字符都被放置。最后，将二维数组的内容依次连接成一个字符串。使用模拟生成法求解本题的主要步骤如下。

        1、初始化。创建一个二维列表，大小为numRows行，用于存储Z字形排列的每个字符。同时，初始化行索引 row为0，方向变量goingDown为True表示当前正向下移动，False表示向上移动。

        2、遍历字符串。对于输入字符串 s 中的每个字符，根据当前的行索引row将字符放入二维列表的对应位置。

        3、更新行索引和方向。根据当前的移动方向更新行索引，如果到达第一行或最后一行，则改变移动方向。

        4、构造结果字符串。最后，遍历二维列表，将所有字符按顺序连接成一个字符串并返回。

        根据上面的算法步骤，我们可以得出下面的示例代码。

def zigzag_conversion_by_simulation(s: str, numRows: int) -> str:if numRows == 1 or numRows >= len(s):# 特殊情况处理：只有一行，或行数大于等于字符串长度时，直接返回原字符串return s# 初始化二维列表rows = [''] * numRowsrow = 0goingDown = Truefor char in s:# 在当前行添加字符rows[row] += charif goingDown:# 增加行索引row += 1# 到达最后一行，准备向上if row == numRows - 1:goingDown = Falseelse:# 减少行索引row -= 1# 回到第一行，准备向下if row == 0:goingDown = Truereturn ''.join(rows)print(zigzag_conversion_by_simulation('PAYPALISHIRING', 3))
print(zigzag_conversion_by_simulation('PAYPALISHIRING', 4))
print(zigzag_conversion_by_simulation('A', 1))

一次遍历法

        通过观察Z字形排列的规律，可以发现字符串中的字符实际上是以一定的周期性“跳跃”到下一行或上一行。我们可以直接通过计算确定每个字符应该落在哪一行，而不需要实际创建二维数组。使用一次遍历法求解本题的主要步骤如下。

        1、计算周期。首先，识别Z字形排列的周期性。对于每一组完整的“向下-向上”往返，涉及2*numRows - 2个字符。另外，还需考虑边界情况，即当行数为1或字符串长度不足以形成完整周期的场景。

        2、遍历并直接构建结果。通过计算当前字符在Z字形中的实际行位置，直接在结果字符串中构建输出。利用数学公式确定字符应落在哪一行，依据当前字符索引和Z字形的行数动态调整。

def zigzag_conversion_by_traversal(s: str, numRows: int) -> str:if numRows == 1 or numRows >= len(s):# 特殊情况处理：只有一行，或行数大于等于字符串长度时，直接返回原字符串return sresult = [''] * numRowsn = len(s)# 完整周期字符数cycle = 2 * numRows - 2for i in range(n):# 计算当前字符在Z字形中的行位置，在每个周期内，字符在前numRows-1行是递增，之后是递减row_index = i % cycle if i % cycle < numRows else cycle - i % cycle# 将字符添加到对应行result[row_index] += s[i]# 将结果列表中的字符串合并为一个字符串return ''.join(result)print(zigzag_conversion_by_traversal('PAYPALISHIRING', 3))
print(zigzag_conversion_by_traversal('PAYPALISHIRING', 4))
print(zigzag_conversion_by_traversal('A', 1))

总结

        模拟生成法的时间复杂度为O(n)，其中n是输入字符串的长度。空间复杂度为O(numRows * m)，其中m是字符串s中最长行的字符数。最坏情况下，如果numRows较大且字符串分布均匀，可能需要较大的空间来存储二维数组。模拟生成法直接反映了Z字形的实际构建过程，逻辑清晰，实现直观，易于理解和编码。缺点在于空间效率较低，当numRows很大时，可能会占用较多的空间。

        一次遍历法的时间复杂度也为O(n)，空间复杂度为O(numRows)，只需一个大小为numRows的列表来暂存每行的字符。相比模拟法，空间需求更低，特别是当字符串很长而numRows较小时。缺点在于实现相对抽象，理解其背后的数学逻辑可能需要更多的思考。