6. Z 字形变换
题目描述
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
示例 3：
输入：s = "A", numRows = 1
输出："A"
方法一：找规律
以 s = "PAYPALISHIRING", numRows = 3 为例，仔细分析
P A H N
下标 0 4 8 12
A P L S I I G
下标 1 3 5 7 9 11 13
Y I R
下标 2 6 10
可以得到以下规律：
- 第一行元素的下标对
4求余数全得0； - 最后一行元素的下标对
4求余数全得2； - 第二行元素的下标对
4求余数全得1或者3，而1+3=4；
而 4=2*(3-1)=2*(numRows-1)。
numRows = 4的时候
P I N
0 6 12
A L S I G
1 5 7 11 13
Y A H R
2 4 8 10
P I
3 9
- 第一行元素的下标对
6求余数全得0； - 第二行元素的下标对
6求余数全得1或者5，而1+5=6； - 第三行元素的下标对
6求余数全得2或者4，而2+4=6； - 第四行元素的下标对
6求余数全得3。
class Solution {
public String convert(String s, int numRows) {
if (numRows < 2)
return s;
int length = s.length();
int num = 2 * (numRows - 1);
StringBuilder builder = new StringBuilder();
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < length; j++) {
if (j % num == i || j % num == num - i) {
builder.append(s.charAt(j));
}
}
}
return builder.toString();
}
}
方法二：模拟
以下思路来自于 Leetcode 大神，闪瞎我的眼。
链接：https://leetcode-cn.com/problems/zigzag-conversion/solution/zzi-xing-bian-huan-by-jyd/。
- 字符串
s是以 Z 字形为顺序存储的字符串，目标是按行打印。 - 设
numRows行字符串分别为 $s_1,s_2,…, s_n$，则容易发现：按顺序遍历字符串 $s$ 时，每个字符 $c$ 在 $Z$ 字形中对应的 行索引 先从 $s_1$增大到 $s_n$，再从 $s_n$减小至 $s_1$…… 如此反复。 - 因此，解决方案为：模拟这个行索引的变化，在遍历
s中把每个字符填到正确的行res[i]。
算法流程：
res[i] += c： 把每个字符c填入对应行 $s_i$；i += flag： 更新当前字符c对应的行索引；flag = - flag： 在达到 $Z$ 字形转折点时，执行反向。
复杂度：
- 时间复杂度 $O(N) $ ：遍历一遍字符串
s； - 空间复杂度 $O(N)$ ：各行字符串共占用 $O(N)$额外空间。
class Solution {
public String convert(String s, int numRows) {
if (numRows < 2) {
return s;
}
List<StringBuilder> rows = new ArrayList<>();
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.toString());
}
return ans.toString();
}
}