Z 字形变换

一：题目

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

二：实例

示例 1：

1
2
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

1
2
3
4
5
6
7
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

1
2
输入：s = "A", numRows = 1
输出："A"

三：提示

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、',' 和 '.' 组成
  • 1 <= numRows <= 1000

四：算法实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * Author: Rupert Tears
 * Date: Created in 18:54 2022/11/12
 * Description: Thought is already is late, exactly is the earliest time.
 * Z 字形变换
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串
 * <p>
 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时;
 * 输出需要从左往右逐行读取，产生出一个新的字符串为："PAHNAPLSIIGYIR"。
 */
public class Aigo_006 {

    public static void main(String[] args) {
        String str = "PAYPALISHIRING";
        String res = convert(str, 3);
        System.out.println(res);
    }

    public static String convert(String str, int numRows) {
        // 单个字符情况
        if (numRows < 2) {
            return str;
        }

        // 存放行结果
        List<StringBuilder> rows = new ArrayList<>();

        // 生成指定行数 stringbuilder
        for (int i = 0; i < numRows; i++) {
            rows.add(new StringBuilder());
        }

        // 行数
        int i = 0;
        // 首位变换标识
        int flag = -1;

        // 遍历字符串
        for (char c : str.toCharArray()) {
            // 向目标行添加字符
            rows.get(i).append(c);
            if (i == 0 || i == numRows - 1) {
                // 首尾标志变换
                flag = -flag;
            }
            // 行数变换
            i += flag;
        }

        // 存储结果
        StringBuilder result = new StringBuilder();
        // 遍历添加结果
        for (StringBuilder row : rows) {
            result.append(row);
        }

        return result.toString();
    }
}

五：思路总结

  • 将 Z 形变换的结果，存储到一个父 StringBuilder 中。通过下标，控制向子 StringBuilder 中添加字符，即添加到对应的行中。
  • 通过 flag 变量，来控制遍历字符串时，对子 StringBuilder 的选择。
  • 遍历父 StringBuilder ，获取最终的输出结果。