leetcode - 0006 Z 字形变换

https://leetcode-cn.com/problems/zigzag-conversion/

审题一分钟，脑子里大概想了一下，觉得这样可以解：

假设输入行数为 3

第一行：0, 4, 8, 12 ...
第二行：1, 3, 5, 7, 9, 11, 13...
第三行：2, 6, 10, 14 ...

假设输入行数为 4

1. 第一行：0,       6,        12, ...
2. 第二行：1,    5, 7,    11, 13
3. 第三行：2, 4,    8, 10     14
4. 第四行：3        9,        15

似乎其中可以看出一定的关系来。

整道题换个意思就是：假设要求输出 n 行，那么第 x 行的第 i 个字符是什么？

假设输入行数为 n，观察第 x 行，有一个特征，它会有两个取数间隔 a, b 。对于第一行和最后一行，a 和 b 其中有一个为 0。

解法一

每个跳跃周期是 period = (numRows - 1) * 2

第一行和最后一行，每个数间隔一个周期中间的行，每两个数间隔一个周期

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        period = (numRows - 1) * 2
        res = ""
        for x in range(numRows):
            i = 0
            while i < len(s):
                index_of_s = x
                if x == 0 or x == (numRows - 1):
                    index_of_s += period * i
                else:
                    if i % 2 == 1:
                        index_of_s += (numRows - x - 1) * 2
                    index_of_s += period * (i//2)
                if index_of_s >= len(s):
                    break
                print(index_of_s, end='')
                res += s[index_of_s]
                i += 1
            print()
        return res

解法二

看了评论里的一个解答，打开了新思路。

想像一下，字符串s 就是一串球，要分成 n 行就是要把它们装进 n 个管子里。

管子编号是 0 ... (n-1)

我按顺序从 s 中取出球，顺序往管子里装，装到最后一个再返回来装。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        row = [[] for _ in range(numRows)]
        i = 0
        forward = True
        for c in s:
            row[i].append(c)
            if i == 0:
                forward = True
            elif i == (len(row) - 1):
                forward = False
            if forward:
                i += 1
            else:
                i -= 1
        l = []
        for r in row:
            l.extend(r)
        return ''.join(l)

这个解法只需要把 s 遍历一遍就可以得到结果，时间复杂度为 O(n)

看了答案，答案中的方法一就是上面这种解法。

参考一个比我快的答案，写得比较 python 一点。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s

        res = [ '' for _ in range(numRows)]
        i = 0
        step = -1
        for c in s:
            res[i] += c
            if i == 0 or i == (numRows - 1):
                step = -step
            i += step
        return ''.join(res)

注意最开始的时候 i == 0，这个时候的方向应该是由高到低的方向，所以初始 step = -1

meishaoming / blog

leetcode - 0006 Z 字形变换 #71

解法一

解法二