卖萌的弱渣

I am stupid, I am hungry.

ZigZag Conversion

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

string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

Solution

  • 模拟从第一行插入到numRows-1行，再倒回去，依次往复

  • Java:

(ZigZag-Conversion.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class Solution {
    public String convert(String s, int numRows) {
        char[] c = s.toCharArray();
        int len = c.length;
        StringBuffer[] sb = new StringBuffer[numRows];
        for (int i=0;i<numRows;i++)
            sb[i] = new StringBuffer();
        int i =0;
        while(i<len){
            for(int idx = 0; idx<numRows && i<len; idx++)
                sb[idx].append(c[i++]);
            for(int idx = numRows-2; idx>=1 && i<len; idx--)
                sb[idx].append(c[i++]);
        }

        for(i=1;i<numRows;i++)
            sb[0].append(sb[i]);
        return sb[0].toString();
    }
}
  • Python
(Zigzag-Conversion.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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 i in range(numRows)]
        step = 1
        i = 0
        for c in s:
            zigzag[i] += c
            # 从0行开始的话往下走
            if i == 0:
                step = 1
            # 到达末尾行要返回
            if i == numRows -1:
                step = -1
            i += step
        ret = ""
        for i in zigzag:
            ret += i
        return ret