6. Z 字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zigzag-conversion

姿势 1：模拟法

模拟构建 Z 字型的顺序将最后的二维数组构建出来，最后再将数组还原成字符串，虽然能通过。但是效率很低下。

class Solution:
    def computecolumns(self, length:int, numRows: int) -> int:
        s1, y1 = divmod(length, 2 * numRows - 2)
        s2, y2 = divmod(y1, numRows)
        return s1 * (numRows - 1) + s2 + y2


    def convert(self, s: str, numRows: int) -> str:
        length = len(s)
        if numRows == 1 or length == 0:
            return s
        maxRow = numRows
        maxCol = self.computecolumns(length,numRows)
        lst = [[-1 for i in range(maxCol)] for i in range(maxRow)]
        # 记录方向,True向下，False向上
        flag = False
        # 记录当前行号，行号从1开始，和numRows对应
        line = 1
        # 记录当前列号，从0开始
        col = 0
        # index
        i = 0
        while i < length:
            lst[line-1][col] = i
            i += 1
            if line == numRows or line == 1:
                flag = not flag
            if flag:
                line += 1
            else:
                line -= 1
                col += 1
        return "".join([s[j] for i in lst for j in i if j != -1])

姿势 2：按行访问

实际上，我们并不需要对每个元素的位置定义那么精准。

只需要知道他在哪一行就可以了。访问到当前行的时候，加入字符就可以了。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        length = len(s)
        if numRows == 1: return s
        lst = [[] for i in range(min(numRows, length))]
        line = 0
        flag = False
        for item in s:
            lst[line].append(item)
            if line == numRows - 1 or line == 0:
                flag = not flag
            line += 1 if flag else -1
        return "".join([j for i in lst for j in i])

姿势 3：找规律

这个需要一定的思考时间。

思路：

按照与逐行读取 Z 字形图案相同的顺序访问字符串。

算法：

首先访问行0中的所有字符，接着访问行1，然后行2，依此类推...

对于所有整数k，

• 行0中的字符位于索引k(2*numRows-2)处；

• 行numRows-1中的字符位于索引k(2*numRows-2)+numRows-1处；

• 内部的行i中的字符位于索引k(2*numRows-2)+i以及k(2*numRows-2)-i

  即，主列的在+i处，非主列的在-i处，并且非主列的只需要增加一个。

Python 代码如下：

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        ret = ""
        n = len(s)
        cycleLen = 2 * numRows - 2
        for i in range(numRows):
            for j in range(0, n, cycleLen):
                if j + i >= n: break
                ret += s[i + j]
                # 如果非首行尾行，两个主列之间只需要增加一个字母。并且增加的这个字母的索引不能超出范围。
                if i != 0 and i != numRows - 1 and j + cycleLen - i < n:
                    ret += s[j + cycleLen - i]
        return ret