6. 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”.

解法1：O(N) Time + O(N) Space

这题的数学解法很难想，也比较花时间。很直观的做法倒是不错。就每一行用一个stringbuilder，然后一行行的塞。先从上往下，再从下往上斜着填。
当所有数字填满了之后把stringbuilder连起来就可以了。
C++

1

Java

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
public class Solution {
    public String convert(String s, int numRows) {
        StringBuilder[] builders = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            builders[i] = new StringBuilder();
        }
        int pos = 0;
        while (pos < s.length()) {
            for (int i = 0; i < numRows && pos < s.length(); i++) {
                builders[i].append(s.charAt(pos++));
            }
            for (int i = numRows - 2; i >= 1 && pos < s.length(); i--) {
                builders[i].append(s.charAt(pos++));
            }
        }
        for (int i = 1; i < numRows; i++) {
            builders[0].append(builders[i]);
        }
        return builders[0].toString();
    }
}