LC 6. Z 字形变换

题目描述

这是 LeetCode 上的 6. Z 字形变换 ,难度为 中等

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

比如输入字符串为 "PAYPALISHIRING" 行数为 $3$ 时,排列如下:

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

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

请你实现这个将字符串进行指定行数变换的函数:string convert(string s, int numRows);

示例 1:

1
2
3
输入:s = "PAYPALISHIRING", numRows = 3

输出:"PAHNAPLSIIGYIR"

示例 2:
1
2
3
4
5
6
7
8
9
输入:s = "PAYPALISHIRING", numRows = 4

输出:"PINALSIGYAHRPI"

解释:
P I N
A L S I G
Y A H R
P I

示例 3:
1
2
3
输入:s = "A", numRows = 1

输出:"A"

提示:

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

模拟

由于最终是要我们对 Z 型矩阵进行从上往下、从左往右的构建输出。

因此可以构建一个矩阵 g 存储 Z 型中的每行字符(忽略 Z 中的空格间隙),同时使用 idxs 存储 Z 型中每行用到的下标。

目标 Z 型 和 矩阵 g 以及 idxs 三者关系:

1
2
3
4
P     I    N             PIN                3
A L S I G => ALSIG => 5
Y A H R YAHR 4
P I PI 2

代码:

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
class Solution {
static int N = 1010;
static char[][] g = new char[N][N];
static int[] idxs = new int[N];
public String convert(String s, int m) {
if (m == 1) return s;
int n = s.length();
Arrays.fill(idxs, 0);
for (int i = 0, j = 0, k = 1; i < n; i++) {
g[j][idxs[j]++] = s.charAt(i);
j += k;
if (j < 0) {
j += 2; k = 1;
} else if (j == m) {
j -= 2; k = -1;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; i++) {
for (int j = 0; j < idxs[i]; j++) {
sb.append(g[i][j]);
}
}
return sb.toString();
}
}

  • 时间复杂度:创建数组的工作只会发生一次,清空 idxs 数组操作会发生在每个样例中,复杂度为 $O(m)$;将 s 的每个字符填入矩阵的复杂度为 $O(n)$;从矩阵中取出字符构建答案复杂度为 $O(n)$。整体复杂度为 $O(m + n)$
  • 空间复杂度:$O(n \times m)$

数学规律

对于本题,我们可以不失一般性的将规律推导为「首项」和「公差公式」。

这通常能够有效减少一些判断。

分情况讨论:

  • 对于第一行和最后一行:公差为 2 * (n − 1) 的等差数列,首项是 i
  • 对于其他行:两个公差为 2 * (n − 1) 的等差数列交替排列,首项分别是 i2 * n − i − 2

代码:

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
class Solution {
public String convert(String s, int r) {
int n = s.length();
if (n == 1 || r == 1) return s;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < r; i++) {
if (i == 0 || i == r - 1) {
int pos = i, offset = 2 * (r - 1);
while (pos < n) {
sb.append(s.charAt(pos));
pos += offset;
}
} else {
int pos1 = i, pos2 = 2 * r - i - 2;
int offset = 2 * (r - 1);
while (pos1 < n || pos2 < n) {
if (pos1 < n) {
sb.append(s.charAt(pos1));
pos1 += offset;
}
if (pos2 < n) {
sb.append(s.charAt(pos2));
pos2 += offset;
}
}
}
}
return sb.toString();
}
}

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.6 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!