LeetCode-Python-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

第一种思路：

直白的麻瓜思路，开个数组按顺序一个个压进去，得到上面解释里的数组，然后再从左到右，从上到下读出来就好。

压进去的过程有两种可能，

1. 从上往下压， 定义state = "down"， 每次x += 1，当x触底就转换state为"up"

2. 从左下往右上压， 定义state = "up"， 每次 x -= 1, y += 1， 当x归零就转换state为"down"

class Solution(object):
    def convert(self, s, n):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        #麻瓜解法：开个数组，把输入按要求放进去，然后再按输出顺序读出来
        if n <= 1:
            return s
        l = len(s)
        record = [[0] * l for _ in range(n)]
        x, y = 0, 0
        state = "down"
        for i, char in enumerate(s):
            # print x, y, char
            record[x][y] = char
            if state == "down":
                if x != n - 1:
                    x += 1
                else:
                    state = "up"
                    x -= 1
                    y += 1
                continue
            
            elif state == "up":
                if x != 0:
                    x -= 1
                    y += 1
                else:
                    state = "down"
                    x += 1
        # print record
        res = ""
        for row in record:
            for char in row:
                if char != 0:
                    res += char
        
        return res

第二种思路:

找规律。

class Solution(object):
    def convert(self, s, n):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        #找规律
        if n <= 1:
            return s
        l = len(s)
        res = ""
        for i in range(n):
            tmp, index = "", i
            if i in [0, n - 1]:
                while(index < l):
                    
                    tmp += s[index]
                    index += 2 * (n - 1)
            else:
                state = "down"
                while(index < l):
                    tmp += s[index]
                    if state == "down":
                        state = "up"
                        index += 2 * (n - 1 - i)
                    else:
                        state = "down"
                        index += 2 * i
            res += tmp

        return res
                    
                        
            

上面是2019.5.10写的，下面是2019.6.1写的，更丑了……

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        #第一行和最后一行都是相差 2 * (n - 1)
        #对于直角在上面的直角三角形， 相差 2 * (n - 1 - i)
        #对于直角在下面的直角三角形， 相差 2 * i
        if not s:
            return s
        res = ""
        for idx in range(numRows):
            res += s[idx]
            
            if idx in [0, numRows - 1]:
                tmp = idx + 2 *(numRows - 1)
                while tmp < len(s):
                    res += s[tmp]
                    tmp += 2 *(numRows - 1)
            else:
                tmp = idx + 2 * (numRows - 1 - idx)
                tri = "down"
                while tmp < len(s):
                    res += s[tmp]
                    if tri == "up":
                        tmp += 2 * (numRows - 1 - idx)
                        tri = "down"
                    else:       
                        tmp += 2 * idx
                        tri = "up"
                    
        return res