ZigZag Conversion

Question:

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".
比方说一个字符串下标为1,2,3,4,5,6,7,8,9,10,....根据输入的nRows判断z的行数,

当nRows = 3 时

字符串格式为

1   5   9
2 4 6 8 10             
3   7   11

当nRows = 4时

字符串格式为

1     7       13
2   6 8    12 14       
3 5   9 11    15
4     10      16

理解题意就很好做

Examples:

input :"PAYPALISHIRING", 3
output:"PAHNAPLSIIGYIR"

Solution:

方法

我用了找规律的方式做这道题,首先我们建立一个不一样的z
假设nRows = 4

1     7       13
2 5   8 11    14       
3   6 9    12 15
4     10      16

但是我们先这样看这个z发现每一行的规律就很清晰了
首行与尾行每个字符间的的距离是 nRows*2-2
中间行的每个字符间的距离是是nRows-1
这时我们只需要在这样的格式上根据中心点进行一个对称,每次都去更新其步长就可以得到我们想要的格式

1     7       13
2   6 8    12 14       
3 5   9 11    15
4     10      16

是我们要求的z的格式

Code:

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        Slength = len(s)
        newStr = ''
        jump = numRows*2-2
        if(numRows>=Slength or numRows == 1):
            return s
        for i in range(numRows):
            temp = 1
            count = i
            if(i==0 or i==numRows-1):#首行与尾行的间距是不变的
                while(count<Slength):
                    newStr += s[count]
                    count+=jump
            else:
                if(temp == 1): #需要计算中间行时的第一次步长度
                    row = 2*i-numRows+1
                    stage = jump/2-row
                while (count < Slength):
                    temp = 0
                    newStr += s[count]
                    count += stage
                    stage = jump-stage #需要每次更新其步长度,为总长度-之前步长
        return newStr