[LeetCode]6. Z 字形变换(ZigZag Conversion)

题目描述

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时,排列如下:

L C I R
E T O E S I I G
E D H N

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);

示例 1:

输入: s = “LEETCODEISHIRING”, numRows = 3
输出: “LCIRETOESIIGEDHN”

示例 2:

输入: s = “LEETCODEISHIRING”, numRows = 4
输出: “LDREOEIIECIHNTSG”
解释:
L D R
E O E I I
E C I H N
T S G

解题思路

直接模拟该形状的生成过程,将每行的结果加入 list,最后遍历取出即可。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return s
length = min(numRows, len(s)) # 实际的行数
rows = [[] for _ in range(length)] # 用来存放每行的结果
cur_row = 0

# 显示当前的方向是向下还是向上;
# 初始化为向上(因为认为第一个数字是前面不存在的列传上来的,方便后面取相反的方向)
down = False

for char in s:
rows[cur_row].append(char)
if cur_row == 0 or cur_row == length - 1:
down = not down
cur_row = cur_row + 1 if down else cur_row - 1
res = []
for row in rows:
res += row
return "".join(res)

执行用时 : 124 ms
内存消耗 : 13.8 MB

参考

https://leetcode-cn.com/problems/zigzag-conversion/solution/z-zi-xing-bian-huan-by-leetcode