题目描述：

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 text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

题目大意：

在行数给定时，字符串“PAYPALISHIRING”的Z字形（zigzag）写法像这样：（使用等宽字体可以得到更好的显示效果）：

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

然后一行一行的读取：“PAHNAPLSIIGYIR”

编写代码读入字符串以及行数，将字符串转化为其Z字形式：

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3)应当返回“PAHNAPLSIIGYIR”。

解题思路：

模拟题，使用长度为numRows的数组按行存储经过zigzag转化后的字母

最后将每一行的字母顺次拼接即可

Python代码：

class Solution:
    # @param {string} s
    # @param {integer} numRows
    # @return {string}
    def convert(self, s, numRows):
        if numRows == 1 or numRows >= len(s):
            return s
        zigzag = [[] for x in range(numRows)]
        row, step = 0, 1
        for c in s:
            zigzag[row] += c,
            if row == 0:
                step = 1
            elif row == numRows - 1:
                step = -1
            row += step
        return ''.join(reduce(operator.add, zigzag))

另一种解法是寻找字母下标与其所在行的对应关系：

参考：https://leetcode.com/discuss/39346/an-accepted-6-line-python-solution

编写一个函数convertRowNum(idx, numRows)

输入当前的字符下标idx与行数numRows，返回其所在的行号rowNum

函数如下：

def convertRowNum(self, idx, numRows):
    return numRows -1 - abs(numRows - 1 - i % (2 * numRows - 2))

zigzag字符串中字母所在的行号序列为：

1, 2, ... , numRows - 1, numRows, numRows - 1, ... 2, 1

上述序列是一个长度为 2 * numRows - 2 的无限循环

Python代码：

class Solution:
    # @param {string} s
    # @param {integer} numRows
    # @return {string}
    def convert(self, s, numRows):
        if numRows == 1 or numRows >= len(s): 
            return s
        final = [[] for row in xrange(numRows)]
        for i in range(len(s)): 
            final[numRows -1 - abs(numRows - 1 - i % (2 * numRows - 2))].append(s[i])
        return "".join(["".join(final[i]) for i in xrange(numRows)])

 

本文链接：http://bookshadow.com/weblog/2015/08/12/leetcode-zigzag-conversion/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码