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) 

1
2
3
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:

1
convert("PAYPALISHIRING", 3) ==>  "PAHNAPLSIIGYIR"

思路

首先考虑最简单的情况，行数为2的时候，行数为3的时候每一个元素的分布情况。可以发现，元素分布是有规律的。就拿例子而言，第一行的元素之间相隔3个字符，第二行的元素之间相隔1个字符，利用求余操作就可以得到对应关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        strlist = []
        length = len(s)
        for i in range(numRows):
            strlist.append("")
            
        if (numRows != 1):
            for i in range(length):
                remain = i % (2 * (numRows-1) )
                if (remain >= numRows):
                    remain = (2 * (numRows-1) ) - remain
                strlist[remain] += s[i]
                
            res = ""
            for k in strlist:
                res += k
            return res
        
        else:
            return s

下图也可以更好地理解此题

1
2
3
4
5
6
7
Δ=2n-2    1                           2n-1                         4n-3
Δ=        2                     2n-2  2n                    4n-4   4n-2
Δ=        3               2n-3        2n+1              4n-5       .
Δ=        .           .               .               .            .
Δ=        .       n+2                 .           3n               .
Δ=        n-1 n+1                     3n-3    3n-1                 5n-5
Δ=2n-2    n                           3n-2                         5n-4