分析

• 本题的考点：找规律。

/*
 * 本质上是一个找规律的题目，一共n行
 * 0       6         12
 * 1    5  7     11  13
 * 2  4    8  10     14
 * 3       9         15
 * 第一行和最后一行都是等差数列，公差为 d = 2*n-2
 * 中间的行为两个等差数列的组合，公差均为 d = 2*n-2, 第一个等差数列首项为i, 第二个首项为 d-i
 */

代码

• C++

class Solution {
public:
    string convert(string s, int numRows) {

        if (numRows == 1) return s;

        string res;
        int d = 2 * numRows - 2;  // 公差
        for (int i = 0; i < numRows; i++) {
            if (i == 0 || i == numRows - 1) {  // 第一行或者最后一行
                for (int j = i; j < s.size(); j += d)
                    res += s[j];
            } else {
                for (int j = i, k = d - i; j < s.size() || k < s.size(); j += d, k += d) {
                    if (j < s.size()) res += s[j];
                    if (k < s.size()) res += s[k];
                }
            }
        }
        return res;
    }
};

• Java

class Solution {
    public String convert(String s, int numRows) {

        if (numRows == 1) return s;

        char[] cs = s.toCharArray();

        StringBuilder res = new StringBuilder();
        int d = 2 * numRows - 2;
        for (int i = 0; i < numRows; i++) {
            if (i == 0 || i == numRows - 1) {
                for (int j = i; j < cs.length; j += d)
                    res.append(cs[j]);
            } else {
                for (int j = i, k = d - i; j < cs.length || k < cs.length; j += d, k += d) {
                    if (j < cs.length) res.append(cs[j]);
                    if (k < cs.length) res.append(cs[k]);
                }
            }
        }
        return res.toString();
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为字符串长度。

• 空间复杂度：$O(n)$，n为字符串长度。