【力扣算法题解】6. Z 字形变换 两种解决方案

Problem: 6. Z 字形变换

方法一：StringBuilder[]相加

思路

示例
P   A   H   N
A P L S I I G
Y   I   R
1
2
3
4

通过flag来变换StringBuilder[]遍历方向，以示例数据来说就是 PA YP AL IS HI…这样遍历
最后将StringBuilder[]相加，较为复杂，速度较慢

解题方法

class Solution {
    public String convert(String s, int numRows) {
        StringBuilder[] builders = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            builders[i] = new StringBuilder();
        }
        int len = s.length();
        boolean flag = false;
        for (int i = 0; i < len; i++) {
            if (numRows == 1 || i % (numRows - 1) == 0) {
                flag = !flag;
            }
            if (flag) {
                builders[i % (numRows - 1 == 0 ? 1 : numRows - 1)].append(s.charAt(i));
                // System.out.println("a: " + i % numRows);
            } else {
                builders[numRows - 1 - (i % (numRows - 1 == 0 ? 1 : numRows - 1))].append(s.charAt(i));
                // System.out.println("b: " + (numRows-1 - (numRows-1 == 0 ? 1 : numRows-1)));
            }
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            // System.out.println(builders[i].toString());
            res.append(builders[i].toString());
        }
        return res.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

复杂度

时间复杂度:

$O(n)$ ，其中 n 是输入字符串的长度

空间复杂度:

$O(n+numRows)$

方法二：数学方法

思路

示例
P   A   H   N
A P L S I I G
Y   I   R
1
2
3
4

计算出第一行所有字符的下标间隔，再按顺序添加到char[]中，接着就开始第二第三行字符添加
在示例数据中，第一、二、三行的字符下标间隔分别为4 0, 2 2, 0 4，间隔为0的下标相当于当前遍历时所在的字符下标，已经添加过了，不需要再次添加。

numRows = 4的第一、二、三、四行字符下标间隔则分别为6 0, 4 2, 2 4, 0 6；

numRows = 4的第一、二、三、四行字符下标间隔则分别为8 0, 6 2, 4 4, 2 6, 0 8。由此可知字符下标间隔最大为(numRows-1)*2，且每行间隔相差2。
（略）

解题方法

class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        // 特例处理
        if (len <= 2 || numRows < 2 || numRows > len) {
            return s;
        }
        char[] res = new char[len];
        int num = 0;
        int index = 0;
        for (int i = (numRows-1)*2, j = 0; num < numRows; i -= 2, j += 2, num++) {
            int temp = num;
            // 第一个字符的添加
            res[index++] = s.charAt(temp);
            while (true) {
                // 接着一次添加两个，如果temp下标超过len则退出循环
                temp += i;
                if (temp >= len) {
                    break;
                }
                if (i != 0) {
                    res[index++] = s.charAt(temp);
                }
                temp += j;
                if (temp >= len) {
                    break;
                }
                if (j != 0) {
                    res[index++] = s.charAt(temp);
                }
            }
        }

        return new String(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

复杂度

时间复杂度:

$O(n)$ ，其中 n 是输入字符串的长度

空间复杂度:

$O(n)$