LeetCode 6 ZigZag Conversion
Problem :
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:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
Solution :
刚拿到这道题的时候其实我对题的理解是 “numRows给定为基数才可以形成这样的H状”，但是写完代码才发现报错了（numRows传入了偶数）。
当时的思路是，新建个数为numRows的StringBuilder数组，再遍历字符串保存进相应的数组元素。看了答案发现可以直接通过一个StringBuilder来解决，果然学习道路还长，要不断努力。
后来我Google了一下zigzag又看了一下这道题的评论，发现有人贴出了zigzag的标准图。
如图所示我们可以看出，在第一行和最后一行中，每两个数之间的差值(2n-2)，而其他行之间残次不齐。
1
2
3
4
5
6
7
8
9
/*n=numRows
Δ=2n-2 1 2n-1 4n-3
Δ= 2 2n-2 2n 4n-4 4n-2
Δ= 3 2n-3 2n+1 4n-5 .
Δ= . . . . .
Δ= . n+2 . 3n .
Δ= n-1 n+1 3n-3 3n-1 5n-5
Δ=2n-2 n 3n-2 5n-4
*/
但是仔细查看又可以发现其中的规则，即对于其他行（非第一行或最后一行）来说，第一步的差值（即第二行的第1、2个）为2(n-2-2i),第二步（2和3之间）为2i，并不断的交替。
由此可以相应的写出代码。(下列代码中有两种方式的交替与j相加，推荐上面一种（未注释的），被注释的代码容易写错)。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1)
return s;
StringBuilder result = new StringBuilder();
// 最后一行和第一行的相隔2n-2(n为numRows)
int step = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
int j = i;
// 如果是第一行或最后一行直接写进result里面
if (i == 0 || i == numRows - 1) {
for (; j < s.length(); j += step)
result.append(s.charAt(j));
} else {
int step1 = step - 2 * i;
int step2 = step - step1;
boolean flag = true;
while (j < s.length()) {
result.append(s.charAt(j));
if (flag)
j += step1;
else
j += step2;
flag = !flag;
}
// int temp = step2;
// for (; j < s.length(); j += temp) {
// result.append(s.charAt(j));
// if (temp == step1)
// temp = step2;
// else
// temp = step1;
// }
}
}
return result.toString();
}
}
