FlareBall's Blog
0%

6.Z字形变换

Posted on Edited on In ,

按行访问

观察 $Z$ 字形排列可以发现，字符的分布具有周期性。

当行数为 $numRows$ 时，一个完整周期长度为 $2 \times numRows - 2$。对于第 $row$ 行而言，每个周期中一定会出现一个位置 $i + row$ 的字符；如果这一行既不是第一行也不是最后一行，那么同一周期内还会额外出现一个斜着走的位置 $i + cycle - row$。

因此可以直接按行枚举，每一行把属于它的字符按顺序加入答案即可。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        StringBuilder ans = new StringBuilder();
        int n = s.length();
        int cycle = 2 * numRows - 2;
        for (int row = 0; row < numRows; ++row) {
            for (int i = 0; i + row < n; i += cycle) {
                ans.append(s.charAt(i + row));
                if (row != 0 && row != numRows - 1 && i + cycle - row < n) {
                    ans.append(s.charAt(i + cycle - row));
                }
            }
        }
        return ans.toString();
    }
}

模拟走位

也可以直接模拟字符在各行之间来回移动的过程。

准备 $numRows$ 个字符串，依次把字符放入当前行中。当走到第一行或最后一行时，就改变移动方向，于是在各行之间上下折返。最终再把所有行拼接起来，就是按题目要求逐行读取后的结果。

这种写法更符合题意描述，按实际书写过程完成模拟。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for (int i = 0; i < numRows; ++i) {
            rows.add(new StringBuilder());
        }
        int i = 0, flag = -1;
        for (char c : s.toCharArray()) {
            rows.get(i).append(c);
            if (i == 0 || i == numRows - 1) flag = -flag;
            i += flag;
        }
        StringBuilder ans = new StringBuilder();
        for (StringBuilder row : rows) {
            ans.append(row);
        }
        return ans.toString();
    }
}