6. ZigZag Conversion

最近再刷leetcode,除了链表之外的都用python 实现,贴出一些代码,希望指正.

问题描述:
原文中说的比较麻烦,这里用一幅图说明问题
也就是按照图片的方式读,按照横行的方式返回.

zigzag.png

结题思路:

这里有两个重点:

1. 对原图中排列方式按照一个向下和一个斜上为一个单元进行分组,每个单元的个数是rows+(rows-2)

   
   zigzag.png
   

   rows = 3 的时候 一个单元 有4个
   rows = 4 的时候 一个单元 有6个

2. 存储方式,我们按照进行存入,每行是一个list.到时候输出的时候也方便,
   如果rows = 3 那么
   list1 = [0,4,8]
   list2 = [1,3,5,7,9]
   list3 = [2,6]
   (这里的list编号和下面二维数组的标号没有关系.)
   最后输出的时候用两个for(或其他更方便的办法)拼接一下 .

有了单元的概念之后也知道了存储的方式之后我们便开始遍历数组.
每个单元有两部分,竖直向下和向上的勾,

        list1 = []
        for i in range(numRows):
            list1.append([])

构造一个二维数组.

• 对于竖直向下 直接用rem = i % (numRows + numRows - 2) 用下标用对单元的个数取余数 然后list1[rem].append(s[i])
• 对于向上的勾 list1[numRows - 2 - (rem - numRows)].append(s[i])进行循环存入.

我可能没有讲的很清楚,可以看一下代码,多看几遍就懂了

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        list1 = []
        for i in range(numRows):
            list1.append([])
        if numRows ==1:
            return s
        for i in range(len(s)):
            rem = i % (numRows + numRows - 2)
            if rem < numRows:
                list1[rem].append(s[i])
            else:
                list1[numRows - 2 - (rem - numRows)].append(s[i])
        list2 = []
        for i in range(numRows):
            for each in list1[i]:
                list2.append(each)
        return ''.join(list2)


solution = Solution()
print(solution.convert("ABCDEF", 3))