以下题干翻译自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进行重组，速度上当然快了很多。但是从易思考的角度来说，算法一其实更符合一个思维的过程，二更偏向于规律的寻找和利用。

最后，在开发过程中，还是得要在保证功能正确和时间充裕的前提下，进行效率的提升，不要本末倒置，忘了项目真正的意义。