文章目录
题目
标题和出处
标题：Z 字形变换
出处：6. Z 字形变换
难度
4 级
题目描述
要求
将一个给定字符串 s \texttt{s} s 根据给定的行数 numRows \texttt{numRows} numRows，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" \texttt{"PAYPALISHIRING"} "PAYPALISHIRING"，行数为 3 \texttt{3} 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如： "PAHNAPLSIIGYIR" \texttt{"PAHNAPLSIIGYIR"} "PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows); \texttt{string convert(string s, int numRows);} string convert(string s, int numRows);
示例
示例 1：
输入：
s
=
"PAYPALISHIRING",
numRows
=
3
\texttt{s = "PAYPALISHIRING", numRows = 3}
s = "PAYPALISHIRING", numRows = 3
输出：
"PAHNAPLSIIGYIR"
\texttt{"PAHNAPLSIIGYIR"}
"PAHNAPLSIIGYIR"
示例 2：
输入：
s
=
"PAYPALISHIRING",
numRows
=
4
\texttt{s = "PAYPALISHIRING", numRows = 4}
s = "PAYPALISHIRING", numRows = 4
输出：
"PINALSIGYAHRPI"
\texttt{"PINALSIGYAHRPI"}
"PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
示例 3：
输入：
s
=
"A",
numRows
=
1
\texttt{s = "A", numRows = 1}
s = "A", numRows = 1
输出：
"A"
\texttt{"A"}
"A"
数据范围
- 1 ≤ s.length ≤ 1000 \texttt{1} \le \texttt{s.length} \le \texttt{1000} 1≤s.length≤1000
- s \texttt{s} s 由英文字母（小写和大写）、 ‘,’ \texttt{`,'} ‘,’ 和 ‘.’ \texttt{`.'} ‘.’ 组成
- 1 ≤ numRows ≤ 1000 \texttt{1} \le \texttt{numRows} \le \texttt{1000} 1≤numRows≤1000
解法
思路和算法
首先考虑最简单的情形：当 numRows = 1 \textit{numRows}=1 numRows=1 时，将字符串 s s s 按照 Z 字形排列只有 1 1 1 行，且字符顺序不变，因此在 Z 字形变换之后的字符串仍然是 s s s，直接返回 s s s。
当 numRows ≥ 2 \textit{numRows} \ge 2 numRows≥2 时，Z 字形排列会有多行。在生成 Z 字形排列时，需要从左到右遍历字符串 s s s，对于每个字符，计算得到该字符位于 Z 字形排列的哪一行，然后将该字符拼接到所在行。
每个字符在 Z 字形排列中的行下标为从 0 0 0 增加到 numRows − 1 \textit{numRows}-1 numRows−1，然后减少到 0 0 0，重复在该范围内变化。因此需要维护行下标 rowIndex \textit{rowIndex} rowIndex 和变化方向 direction \textit{direction} direction，初始时 rowIndex = 0 \textit{rowIndex}=0 rowIndex=0， direction = 1 \textit{direction}=1 direction=1。遍历 s s s 的每个字符时，将该字符拼接到下标为 rowIndex \textit{rowIndex} rowIndex 的行，然后将 rowIndex \textit{rowIndex} rowIndex 的值增加 direction \textit{direction} direction，则更新后的 rowIndex \textit{rowIndex} rowIndex 为下一个字符应该拼接到的行的下标。由于行下标的取值范围是 [ 0 , numRows − 1 ] [0, \textit{numRows}-1] [0,numRows−1]，因此当更新后的 rowIndex \textit{rowIndex} rowIndex 为 0 0 0 或 numRows − 1 \textit{numRows}-1 numRows−1 时，需要将 direction \textit{direction} direction 取相反数，表示下次行下标的更新需要往相反方向移动。
对 s s s 遍历结束之后，即可得到 Z 字形排列的每一行，将每一行拼接之后，即可得到 Z 字形变换后的结果。
具体实现方面，由于涉及到字符串的拼接，因此使用 StringBuffer \texttt{StringBuffer} StringBuffer 实现。创建长度为 numRows \textit{numRows} numRows 的 StringBuffer \texttt{StringBuffer} StringBuffer 类型数组，该数组的每个元素对应 Z 字形排列的每一行。在拼接每一行得到最终答案时，同样使用 StringBuffer \texttt{StringBuffer} StringBuffer 类型进行拼接。
还有一个可以优化的点。由于 Z 字形排列的每一行都至少有一个字符，因此 Z 字形排列的行数不会超过 s s s 的长度。当 s s s 的长度为 n n n 时，Z 字形排列的行数为 min ( numRows , n ) \min(\textit{numRows}, n) min(numRows,n)，因此在生成 Z 字形排列之前，令 numRows = min ( numRows , n ) \textit{numRows} = \min(\textit{numRows}, n) numRows=min(numRows,n)，可以达到优化的效果。
代码
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
int length = s.length();
numRows = Math.min(numRows, length);
StringBuffer[] rows = new StringBuffer[numRows];
for (int i = 0; i < numRows; i++) {
rows[i] = new StringBuffer();
}
int rowIndex = 0, direction = 1;
for (int i = 0; i < length; i++) {
rows[rowIndex].append(s.charAt(i));
rowIndex += direction;
if (rowIndex == 0 || rowIndex == numRows - 1) {
direction = -direction;
}
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < numRows; i++) {
sb.append(rows[i]);
}
return sb.toString();
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 s s s 的长度。创建 StringBuffer \texttt{StringBuffer} StringBuffer 类型的数组并初始化元素需要 O ( numRows ) O(\textit{numRows}) O(numRows) 的时间，生成 Z 字形排列和拼接得到 Z 字形变换后的结果各需要 O ( n ) O(n) O(n) 的时间，由于会对 numRows \textit{numRows} numRows 预处理确保 numRows ≤ n \textit{numRows} \le n numRows≤n，因此总时间复杂度是 O ( n ) O(n) O(n)。
-
空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 s s s 的长度。Z 字形排列的结果需要 O ( n ) O(n) O(n) 的空间存储，Z 字形变换后的结果也需要 O ( n ) O(n) O(n) 的空间存储。由于 Java 中的 String \texttt{String} String 类型的对象不可变，因此存储 Z 字形变换后的结果的 O ( n ) O(n) O(n) 空间无法省略。