LeetCode6-Z字形变换

解题记录
458 words , 2 mins.

题目描述

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

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

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

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

请你实现这个将字符串进行指定行数变换的函数：

1
string convert(string s, int numRows);

示例 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

思路

找规律间隔读取重新组装

一开始的思路是寻找变换之后的行和字符间间隔的规律。比如 rowNum = 1 的时候，其实就是间隔一个字符读取，然后重新拼接。但是当 rowNum > 2 之后，情况比较复杂，遂放弃。

利用二维数组

这种思路简单直接，代价就是需要额外的空间。先遍历字符串并将每一个字符按照从上往下、从左向右的顺序放到二维数组中，然后按顺序遍历二维数据，将各个字符进行拼接即是答案。

更具体一点：以需要塞满的这些列为分界线，将整个填充过程划分为若干个重复的流程。

观察易得如下规律：

  1. 每一列需要填满的列的行数 = rowNum。
  2. 每一列需要填满的列和下一列需要填满的列相隔 rowNum - 2) 列。
  3. 每一轮需要消耗掉 2 * rowNum - 2 个字符，总共需要 s.length / (2 * rowNum - 2) 轮。
  4. 特别的，当 rowNum = 1 或 s.length = 1 的时候，结果等于原字符串。

代码实现

Java 代码实现如下：

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
public class Solution6 {
    public static String convert2Arr(String s, int rowNum) {
        if (s.length() == 1 || rowNum == 1) {
            return s;
        }

        int length = s.length();
        char[] charArray = s.toCharArray();

        int countPerRound = 2 * rowNum - 2;
        int colPerRound = rowNum - 1;
        int round = (int) Math.ceil((double) length / countPerRound);

        int arrLength = round * colPerRound;

        char[][] arr = new char[rowNum][arrLength];
        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < arrLength; j++) {
                arr[i][j] = '0';
            }
        }
        int ps = 0;
        for (int r = 1; r <= round; r++) {
            int p1 = (r - 1) * colPerRound;
            int p2 = 0;
            while (p2 < rowNum && ps < length) {
                arr[p2][p1] = charArray[ps];
                p2++;
                ps++;
            }

            int m = rowNum - 2;
            int n = p1 + 1;
            while (m > 0 && ps < length) {
                arr[m][n] = charArray[ps];
                m--;
                n++;
                ps++;
            }
        }

        return print(arr);
    }

    private static String print(char[][] arr) {
        int length1 = arr.length;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < length1; i++) {
            int length2 = arr[i].length;
            for (int j = 0; j < length2; j++) {
                if (arr[i][j] != '0') {
                    stringBuilder.append(arr[i][j]);
                }
            }
        }

        return stringBuilder.toString();
    }
}

可参考的解法

以空间换时间的解法：巧设 flag ，非常之巧妙。