基于Python实现对字符串的Z形转换

1、题目描述

    将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数：

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

    之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"

    示例 1:

输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"

    示例 2:

输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"
解释:

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

2、算法设计

    首先观察Z形转换的规律，转换的规则如下所示：

    如上图所示，是按照箭头指示方向排列字符串的，其中数字代表字符串的索引。

    算法一：可以通过暴力解算，即建立一个足够大的二维数组，将按照规则转换的Z形数据存放到二维数组中，然后按照行顺序读取。

    算法二：按照Z形排列的规律，直接在字符串上读取对应索引的元素即可。在这里采取第二种算法。算法具体原理如下：

    通过观察，可得到下图所示的规律：、

    如上图所示，在Z形数据中中，每一行的两个Z的边界之间的距离为6，在此设n1和n2两个变量，其中n1表示Z形中左边部分的距离，n2表示Z形中右边部分的距离，则n1+n2 = 6；通过观察还会发现，两个Z形数据的边界之间的距离6其实是行数相关的，即zlen = 2*(numRows-1)，经证明，该公示是正确的! 通过观察发现，其中n1是numRows和i相关的，n1 = 2*(numRows-i-1)。

    而对于第i行的数据（其中i为字符串s中的第i个元素，i<numRows），后边的数据都和i相关，即index = i; index = index+n1或者index = index  + n2，而n1+n2 = zlen。

3、最终实现

    算法的最终实现如下所示：

    def convert(self, s, numRows):
        if numRows <= 1:
            return s

        k = len(s)
        rstr = ""

        zlen = 2 * (numRows - 1)        #求zlen, 即Z形数据的边界
        for i in range(0, numRows):
            n1 = 2 * (numRows-i-1)        #计算n1
            n2 = zlen - n1                #计算n2

            if n1 == 0 or n2 == 0:
                n1 = n2 = zlen

            j = 1
            index = i
            while index < k:
                rstr = rstr + s[index]
                if j % 2 != 0:
                    index = index + n1
                else:
                    index = index + n2
                j += 1
        return rstr

    该算法的平均耗时120ms。