以下题干翻译自LeetCode，原文题目请参见LeetCode网址: ZigZagConversion
有一个字符串"PAYPALISHIRING"，当使用ZigZag模式写，并且指定了对应的行数时，如下所示(最好设置一个定长的字体来看)：
P A H N
A P L S I I G
Y I R
然后我们要将上面的显示格式一行行读出来，得到另一个字符串"PAHNAPLSIIGYIR"。
现在请编写代码实现这一转换，当输入一个字符串，并且指定了输出行数的时候，返回转换后的字符串：
string convert(string text, int nRows);
e.g. convert("PAYPALISHIRING", 3) 应该返回 "PAHNAPLSIIGYIR".
把这道题写出来的原因是我在写第一种算法时，测得的效率只在LeetCode中排名后3%，特别沮丧！
算法一
而后我又思考了一会，然后写出了第二种算法，测试后发现效率排在了前2%！
算法二
所以在这里也整理一下自己的思路，供以后回顾温习。
算法一（慢）
算法一主要分两块逻辑
- 按照ZigZag顺序向一个多维数组中放入字符
- 按照一行一行的顺序将多维数组放入StringBuilder
public String convert(String s, int numRows) {
if (numRows == 1) return s;
int sign = -1;
char[][] chars = new char[numRows][s.length()];
for (int idx = 0, row = 0, col = 0; idx < s.length(); ++idx) {
chars[row][col] = s.charAt(idx);
if (row == 0 || row == numRows - 1) {
sign *= -1;
}
row += sign;
if (idx != 0 && idx % (numRows - 1) == 0) {
++col;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0, j = 0; i < numRows && j < s.length(); ++j) {
if (chars[i][j] != 0) {
sb.append(chars[i][j]);
}
if (j != 0 && j % (s.length() - 1) == 0) {
++i;
j = -1;
}
}
return sb.toString();
}
算法二（快）
直接根据ZigZag顺序特点，找到按一行一行顺序对应每个字符在字符串中的下标，顺序放入一维数组中。
要注意的是当行数大于3时，需要考虑步长步短的问题。
public String convert(String s, int numRows) {
if (numRows == 1) return s;
char[] result = new char[s.length()];
int resultIdx = 0;
for (int curRow = 0; curRow < numRows; ++curRow) {
int stepLen1 = 2 * (numRows - 1 - curRow);
int stepLen2 = 2 * (curRow );
if (stepLen1 < 1) stepLen1 = stepLen2;
if (stepLen2 < 1) stepLen2 = stepLen1;
for (int strIdx = curRow, step = 1; strIdx < s.length(); ++step) {
result[resultIdx] = s.charAt(strIdx);
++resultIdx;
int steplen = step % 2 == 0 ? stepLen2 : stepLen1;
strIdx += steplen ;
}
}
return String.valueOf(result);
}
以上这两种算法，虽说复杂度都是O(s.length())，但算法二使用了一维数组，且不再需要StringBuilder进行重组，速度上当然快了很多。但是从易思考的角度来说，算法一其实更符合一个思维的过程，二更偏向于规律的寻找和利用。
最后，在开发过程中，还是得要在保证功能正确和时间充裕的前提下，进行效率的提升，不要本末倒置，忘了项目真正的意义。
