【力扣算法09】之 6. N 字形变换 python

全栈若城

发布于 2024-02-29 19:13:42

1910

问题描述

将一个给定字符串 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

思路分析

给定一个字符串 s 和一个整数 numRows，要求按照 Z 字形排列将字符串重新排序，并返回重新排序后的字符串。首先，根据 numRows 的值判断边界情况。如果 numRows 为 1，则直接返回原字符串 s。然后，创建 numRows 个字符串，用于保存每一行的字符。接下来，遍历字符串 s 中的每个字符，并根据规律将字符放入对应的行中。

规律1：前 numRows 个字符依次放入每一行中。规律2：之后的 numRows-2 行，字符依次逆序放入每一行中，即从倒数第二行开始往上逐行放置字符。规律3：重复规律1和规律2，直到遍历完字符串 s 中的所有字符。最后，将每一行的字符拼接起来，得到最终结果。

代码分析

首先，在代码中定义了一个 Solution 类，用于实现字符串变换的方法。
在 convert 方法中，接受两个参数 s 和 numRows，并返回变换后的字符串。
方法开始处判断 numRows 是否为 1，如果是则直接返回原字符串 s。
创建一个列表 rows，长度为 numRows，用于保存每一行的字符。这里使用了列表推导式来创建初始化的空字符串列表。
定义两个变量 curRow 和 goingDown，分别用于追踪当前字符应该放在哪一行和字符行进的方向。
遍历字符串 s 中的每一个字符。
- 将当前字符添加到对应的行 rows[curRow] 中。
- 如果当前行 curRow 为首行或末行，则改变字符行进的方向，即 goingDown 取反。
- 根据字符行进的方向更新当前行 curRow 的值。
遍历完成后，利用 .join() 方法将每一行的字符拼接起来，并返回最终结果。

完整代码

class Solution(object):
    def convert(self, s, numRows):
        if numRows == 1:
            return s
        
        rows = [''] * min(numRows, len(s))  # 创建 numRows 个空字符串，用于保存每一行的字符
        curRow = 0   # 当前字符所在的行
        goingDown = False   # 字符行进的方向，初始为 False 表示向上
        
        for c in s:
            rows[curRow] += c   # 将当前字符添加到对应的行中
            
            # 根据规律1和规律2更新 curRow 和 goingDown 的值
            if curRow == 0 or curRow == numRows - 1:
                goingDown = not goingDown
            curRow += 1 if goingDown else -1
        
        return ''.join(rows)   # 将每一行的字符拼接起来，返回最终结果

详细分析

class Solution(object):

定义一个名为 Solution 的类，用于实现字符串变换的方法。

    def convert(self, s, numRows):
        if numRows == 1:
            return s

定义 convert 方法，接收两个参数：字符串 s 和整数 numRows。如果 numRows 的值为 1，即只有一行，直接返回原始字符串 s。

        rows = [''] * min(numRows, len(s))
        curRow = 0
        goingDown = False

创建长度为 numRows 的空字符串列表 rows，使用列表推导式生成。curRow 用于追踪当前字符应该放在哪一行，初始值为 0。goingDown 用于表示字符行进的方向，初始值为 False，表示向上。

        for c in s:
            rows[curRow] += c

遍历字符串 s 中的每一个字符，将当前字符 c 添加到对应行 rows[curRow] 中的末尾。

            if curRow == 0 or curRow == numRows - 1:
                goingDown = not goingDown

如果当前行 curRow 为首行或末行，则改变字符行进的方向，即 goingDown 取反。

            curRow += 1 if goingDown else -1

根据字符行进的方向来更新当前行 curRow。如果 goingDown 为 True，则 curRow 自增 1，否则自减 1。

        return ''.join(rows)

遍历完成后，使用 .join() 方法将列表 rows 中的每一行字符拼接起来，返回最终的结果字符串。

运行效果截图

调用示例

solution = Solution()
s = "PAYPALISHIRING"
numRows = 3

s1 = "PAYPALISHIRING"
numRows1 = 4

s2 = "A"
numRows2 = 1
print(solution.convert(s, numRows))
print(solution.convert(s1, numRows1))
print(solution.convert(s2, numRows2))