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".
参考：
http://www.cnblogs.com/springfor/p/3889414.html
https://kevinclcn.gitbooks.io/leetcodejava/content/006_zigzag_conversion.html
这道题就是看坐标的变化。并且需要分块处理。
n=2时，字符串坐标变成zigzag的走法就是：
0 2 4 6
1 3 5 7
n=3时的走法是：
0 4 8
1 3 5 7 9
2 6 10
n=4时的走法是：
0 6 12
1 5 7 11 13
2 4 8 10 14
3 9 15
对于zig直线, 即第一列（0，1，2，3），第三列（6，7，8，9），第五列（12，13，14，15）
第三列 － 第一列 = 6 6 － 0 ＝ 6 7 － 1 ＝ 6 8 － 2 ＝ 6 9 － 3 ＝ 6
第五列 － 第三列 ＝ 6 12 － 6 ＝ 6 13 － 7 ＝ 6 14 － 8 ＝ 6 15 － 9 ＝ 6
对于zig斜线，
5 ＝ 1 ＋ 6 － 2 ＊ 1
4 ＝ 2 ＋ 6 － 2 ＊ 2
11 ＝ 7 ＋ 6 － 2 * 1
10 ＝ 8 ＋ 6 － 2 ＊ 2；
＝ > 斜线的序号 ＝ j + size - 2*i , 其中： size = numRows * 2 - 2
备注 ： i为行号，j不为列号，j为zig最近左边直线代表的序号
总结： 遇到矩阵类的，想办法搞清楚坐标之间的关系。 尽量把行列考虑进来。 本例trick， 把行跟序号结合起来。
package com.zhaochao.leetcode;
/**
* Created by zhaochao on 17/2/1. @new york, columbia law school
*/
public class LC_ZigzagConversion {
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 = numRows * 2 - 2;
for(int i = 0; i < numRows; i++)
for(int j = i; j < s.length(); j += size) {
res.append(s.charAt(j));
int tmp = j + size - 2 * i;
if(i != 0 && i != numRows - 1 && tmp < s.length()) {
res.append(s.charAt(tmp));
}
}
return res.toString();
}
}