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".
分析：
这道题主要是找规律。
方法一：
比较直观的解法，使用list存储每一行，最后拼接。
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
res = [‘‘]*numRows
step = 1
row = 0
if len(s) <= 2 or numRows <= 1:
return s
for i in range(len(s)):
res[row] += s[i]
row += step
if row >=numRows:
row = numRows-2
step = -1
if row < 0:
row = 1
step = 1
ans = ‘‘
for i in range(len(res)):
ans += res[i]
return ans
方法二：
发现所有行的重复周期都是 2 * nRows - 2，对于首行和末行之间的行，还会额外重复一次，重复的这一次距离本周期起始字符的距离是 2 * nRows - 2 - 2 * i
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if len(s) < 2 or numRows < 2:
return s
jump = 2*(numRows-1)
res = ‘‘
for i in range(numRows):
j = i
while j < len(s):
res += s[j]
if i > 0 and i < numRows-1 and j+jump-2*i < len(s):
res += s[j+jump-2*i]
j += jump
return res
原文：http://www.cnblogs.com/Peyton-Li/p/7648549.html