LeetCode-Zigzag Conversion

Posted by mapoto4 on 2017-12-21

题目

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.

解题思路

0123456789 nRows = 2

1
2
0 2 4 6 8
1 3 5 7 9

Output:
0 2 4 6 8 1 3 5 7 9

0123456789 nRows = 3

1
2
3
0   4   8
1 3 5 7 9
2 6

Output:
0 4 8 1 3 5 7 9 2 6

0123456789 nRows = 4

1
2
3
4
0     6
1 5 7
2 4 8
3 9

Output:
0 6 1 5 7 2 4 8 3 9

每个Zigzag包含的字符为 size = nRows + nRows - 2
每次跨度一个之,第一行和最后一行只需要添加一个字符,中间每一行需要添加两个字符
第二个字符和前面添加这个字符在s的index相差size - 2 * index

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String convert(String s, int numRows) {

if (s == null || s.length() == 0 || numRows <= 0)
return "";

if (numRows == 1)
return s;

StringBuilder res = new StringBuilder();
int size = 2 * numRows - 2;

for (int i = 0; i < numRows; i++) {
for (int j = i; j < s.length(); j += size) {
res.append(s.charAt(j));
if (i != 0 && i != numRows - 1) {
int temp = j + size - 2 * i;
if (temp < s.length())
res.append(s.charAt(temp));
}
}
}
return res.toString();
}