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

示例

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:

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

解析

1)看到这个题目,第一感觉就是二维列表来存储;

2)难点在于二维列表的压入顺序,是先顺序,后逆序;

3)所以需要先造出一个Z字形的索引列表,比如 numRows=3 时,[0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1];

4)看似像回文的规律,其实索引列表是4个值一重复,而且对应变化为 [1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1];

5)到这应该就能发现规律了,循环周期是 2*numRows,索引值变化是 i % 2*numRows < numRows - 1 为正,反之为负。

代码示例

1、先搞定 Z 字形索引

numRows = 3

r = numRows * 2 - 2
x = 0

for i in range(10):
    print(x, end=' ')
    a = i % r < numRows - 1
    x += 1 if a else -1

# 0 1 2 1 0 1 2 1 0 1
2、二维列表结合Z字索引解题
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        mat = [[] for _ in range(numRows)]
        r = 2 * numRows - 2
        x = 0
        for i,w in enumerate(s):
            mat[x].append(w)
            a = i % r < numRows-1
            x += 1 if a else -1

        return ''.join([i for l in mat for i in l])

执行用时:72 ms, 在所有 Python3 提交中击败了 35.36% 的用户.

本文为 陈华 原创,欢迎转载,但请注明出处:http://www.ichenhua.cn/read/413