题目
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN”
示例 2:
输入: s = “LEETCODEISHIRING”, numRows = 4 输出: “LDREOEIIECIHNTSG” 解释:
解答
解法一：放置字符在对应行
类似于树层序遍历的递归实现，使用一个数组来保存每层的数据。
本题也可以这样做。
具体如下：
声明一个数组保存每行的字符串。确定方向，只有在到达行边界的时候才会改变方向。（第一行和最后一行）按照方向指针 down 改变 curRow 来确定当前字符应该放置在哪一行。
复杂度：O(n) 的时间，O(n) 的空间 。
代码
class Solution {
public String
convert(String s
, int numRows
) {
if(s
== null
|| s
.length() <= 1 || numRows
<= 1) return s
;
int curRow
= 0;
boolean down
= false;
String
[] rows
= new String[Math
.min(s
.length(), numRows
)];
for(int i
= 0; i
< s
.length(); i
++) {
if(rows
[curRow
] == null
) {
rows
[curRow
] = String
.valueOf(s
.charAt(i
));
} else {
rows
[curRow
] += s
.charAt(i
);
}
if(curRow
== 0 || curRow
== numRows
- 1) down
= !down
;
curRow
+= down
? 1 : -1;
}
return String
.join("", rows
);
}
}
结果
解法二：找规律
找到每一行的元素之间的规律即可。
要点如下：
注意当 numRows 为 1 时的边界问题，需要特殊处理。maxInterval 变量代表最大的跳跃间隔，在第一行和最后一行时使用此间隔。interval 变量代表每一行内两个相邻元素在字符串中的跳跃间隔。但因为是 Z 字形，所以需要注意奇偶步数的影响。每次换下一行时，让跳跃间隔减去 2 。
复杂度：O(n) 的时间，O(n) 的空间 。
代码
class Solution {
public String
convert(String s
, int numRows
) {
if(s
== null
|| s
.length() <= 1 || numRows
<= 1) return s
;
int maxInterval
= 2 * numRows
- 3 + 1;
int interval
= maxInterval
;
StringBuilder res
= new StringBuilder();
for(int i
= 0; i
< numRows
; i
++) {
int j
= i
;
int cycle
= 0;
while(j
< s
.length()) {
res
.append(s
.charAt(j
));
if(interval
== maxInterval
|| interval
== 0) {
j
+= maxInterval
;
} else {
j
+= cycle
% 2 == 0 ? interval
: maxInterval
- interval
;
}
cycle
++;
}
interval
-= 2;
}
return res
.toString();
}
}
结果
