Leetcode 6 ZigZag Conversion

发表于 |

将字符串按照Z字型排列成给定的行数，然后从左往右，逐行读取字符

题意分析：
按照Z字形读取字符串并输出

思路分析：
算法题分类中有一种题型叫模拟实现，也就是按照题目给的规则，我们实现算法来模拟过程
这道题就属于标准的一种模拟题，有人肯定会疑惑，这道题哪里有模拟嘛，其实你只要这样想，我们现在要读一个字符串，但是要读到不同的位置（行），应该怎么读呢？

我们对s = 'PAYPALISHIRING', numRows = 4来进行分析，我们直接写出这个字符串中的每一个字符所处的行数，则应该是 12343212343212。发现规律一下就找到了,下一个字符的行数取决于前一个字符的行数，要么+1要么-1，我们定义一个方向dire，向下走是+1，向上走是-1，当走到边界时(level == 0 or level == numRow-1)转向。具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 64ms, beats 80.44%
class Solution(object):
    def convert(self, s, numRows):
        if numRows == 1: return s
        res = [[] for _ in range(numRows)]
        level = 0
        dire = -1
        for ss in s:
            res[level].append(ss)
            if level == numRows-1 or level == 0: dire *= -1
            level += dire

        ans = ''
        for ss in res:
            ans += ''.join(ss)
        return ans