leecode day8 ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);
Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

Z字型排列之后重读，意思要是不理解，直接看上面的例子，一目了然。
我这里使用的是紧密重排。比较麻烦，意思理解清楚也可以直接往下看看别人的解法。
定义一个矩阵，列是固定的，Z的一大半，以example2为例，第一行就是PAYPAL。列通过len(s)除法就可以求出来，我这里直接使用了len(s)，保证够用。

从上图可以看到，除去收尾两行，中间的每一行加起来是固定的，这个数值和行数有关，行数减一乘以2.
我们用下面的方式排列之后就可以直接遍历读取：

遍历的时候，只取前四列，后面的直接用找到的规律去减。
debug过程中有些特例需要处理，放到了最前面，还有一些边界的处理，用例子最直观，代码如下：

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if len(s) == 0:
            return ''
        if len(s) == 1 or numRows == 1:
            return s
        temp_len = numRows - 2
        import numpy as np
        map_res = np.zeros((len(s), (temp_len+numRows)), dtype = int)
        indi = 0
        indj = 0
        for i in range(len(s)):
            map_res[indi, indj] = i#final point position
            if (i+1)%(temp_len+numRows)!=0:
                indj += 1
            else:
                indi += 1
                indj = 0
        if indj == 0:# 如果是紧密排列，最后一行满满的，需要在序号上进行操作
            indi -= 1
            indj = temp_len+numRows
        res_str = ''
        for i in range(numRows):
            for j in range(indi+1):
                if i == 0:
                    res_str += s[map_res[j, i]]
                elif i == (numRows-1):
                    if j < indi:
                        res_str += s[map_res[j, i]]
                    elif  indj > i:
                        res_str += s[map_res[j, i]]
                else:
                    if i==(indj+1) and j == indi:
                        break
                    else:
                        if j < indi:
                            res_str += s[map_res[j,i]]
                            res_str += s[map_res[j,(numRows-1)*2-i]]
                        else:
                            if indj > i:
                                res_str += s[map_res[j,i]]
                            if indj > ((numRows-1)*2-i): 
                                res_str += s[map_res[j,(numRows-1)*2-i]]
        return res_str

代码处理起来特别麻烦，照例看看别人的解法：

说是Z字形，其实就是来回，所以只要来回走就行了，这种来回的操作，确认边界，一加一减就好，思路简单了很多，简单有效。

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1 or numRows >=len(s): # no need for partation
            return s

        row = [''] * numRows# 用LIST来存，（吐槽：脑海中一闪而过，最后还是用numpy矩阵）

        index,step = 0,1

        for x in s:
            row[index] += x #直接在对应行上进行更新操作
            if index ==0: # get back to zero  往下走
                step = 1
            elif index == numRows - 1:
                step = -1 # go the the corner go back 往上走
            index += step

        return "".join(row)#最后把list连在一起

有了好的思想尝试一下，毕竟别人的代码是别人的：

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if len(s) == 0:
            return ""
        res_str = [""]*numRows
        index = 0
        for st in s:
            res_str[index] += st
            if index == (numRows-1):
                index -= 1#这里想把代码简化一下，结果意思其实完全不对了
            if index == 0:
                index += 1
        return "".join(res_str)

修改之后：

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if len(s) == 0:
            return ""#因为s就是“”,所以可以和后面合并
        if numRows == 1:
            return s
        res_str = [""]*numRows
        index = 0
        for st in s:
            res_str[index] += st
            if index == (numRows-1):
                step = -1
            if index == 0:
                step = 1
            index = index + step
        return "".join(res_str)