LeetCode-6 Z字形变换

发表于 | 分类于 | 评论数： | 阅读次数：

题目：Z字形变换

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

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

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

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

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

1
string convert(string s, int numRows);

示例 1:

1
2
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

1
2
3
4
5
6
7
8
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

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

思路

这道题乍一看有点困惑，如果把字符串用下标写出来就会清晰一些：

1
2
3
4
5
line0: 1   5   9
line1: 2 4 6 8 
line2: 3   7 

out: 159246837

按Z字形(或者N字形)的方式重新排列字符串中的字符，最后按行的顺序重新组合起来。其实每行中的字符在字符串中的下标是有规律的，可以总结出数学规律来排列。

用程序实现的话，可以采用迭代法，这样就更直观，也不需要总结数学规律了：

  • 先初始化一个list rows，里面包含numRows个子list用来表示numRows个行
  • 初始化cur_row，用来表示当前的应插入的行数，初始化一个flag用于表示当前Z字形方向是向上还是向下
  • 从第0行开始，依次将字符插入到每一行的子list rows[cur_row]。
  • 当cur_row等于0或者等于numRows-1时，说明到达了第一行或者最后一行，需更改方向
    • 正向时：cur_row += 1
    • 反向时：cur_row += -1

PS:对于numRows=1的情况，需做单独处理，直接返回字符串即可。

实现：

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
        rows = []
        for i in range(numRows):
            rows.append([])
        flag = False
        cur_row = 0
        for char in s:
            rows[cur_row].append(char)
            if cur_row == 0 or cur_row == numRows - 1:
                flag = not flag
            if flag:
                cur_row += 1
            else:
                cur_row -= 1
        out = []
        for row in rows:
            out += row
        return ''.join(out)

优化方法

这里根据flag来判断cur_row是加1还是减1，可以使用python的三目运算：

1
res = 值1 if 条件1 else 值2

上述例子中：

1
2
3
4
if flag:
	cur_row += 1
else:
	cur_row -= 1

就可改写为：

1
cur_row += 1 if flag else -1

如果大家有更好的方法，欢迎一起探讨。