### 题目描述 将一个给定字符串 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 ``` **提示：** - 1 <= s.length <= 1000 - s 由英文字母（小写和大写）、',' 和 '.' 组成 - 1 <= numRows <= 1000 ### 题目解答 #### 思路1——模拟法 创建一个numRows行len(s)列的数组，将s依次按照z字形的走法填入相应的位置，然后按行遍历。 **算法复杂度** 设s的长度为m，行数为n 时间复杂度：需要m次将其放置到位置，然后遍历大小mn数组，得到最终结果。$$O(mn)$$ 空间复杂度：需要建立mn的数组，$$O(mn)$$ #### 思路2——行变化规律 最终的结果是按行遍历，我们可以发现z字形的走法，行的变化规律。从0——numRow-1——0...反复进行循环，我们可以根据行记录遍历的字符串，然后将每行的字符串拼接即可。 **算法复杂度** 设s的长度为m，行数为n 时间复杂度：需要m次遍历数组。$$O(m)$$ 空间复杂度：每行建立一个字符串记录该行的内容，$$O(n)$$ #### 代码实现 ```python class Solution: # 矩阵模拟法 def convert(self, s: str, numRows: int) -> str: if numRows==1: return s elif numRows==2: return s[0::2] + s[1::2] li = [[' '] * len(s) for _ in range(numRows)] point = 0 row = col = 0 while(point < len(s)): while(point < len(s) and row < numRows): li[row][col] = s[point] row = row + 1 point = point + 1 row = row - 1 while(point < len(s) and row > 1): row = row - 1 col = col + 1 li[row][col] = s[point] point = point + 1 row = row - 1 col = col + 1 res = "" for i in range(numRows): for j in range(len(s)): if li[i][j] != ' ': res += li[i][j] return res # 按行记录法 def convert(self, s: str, numRows: int) -> str: if numRows < 2: return s res = ["" for _ in range(numRows)] row = 0 flag = -1 for c in s: res[row] += c if row == numRows - 1 or row == 0: flag = -flag row += flag return "".join(res) ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复