https://leetcode-cn.com/problems/zigzag-conversion/
题目看了半天有点懵，查了一下发现是 Z 字形排列字符串的问题。
采用最淳朴的思路，直接构建 Z 形数组，方案如下（为了不各种考虑各种边界值，所以直接将列数取了一个最大值）。大概超过了 28% 的人。
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
| class Solution {
public String convert(String s, int numRows) {
char[] sc=s.toCharArray();
if(sc.length<=numRows || numRows<=1) return s;
int numCols=sc.length;
char[][] cs=new char[numRows][numCols];
int i=0,j=0;
boolean isDown=true;
for(int k=0;k<sc.length;k++){
cs[i][j]=sc[k];
if(isDown){
if(i<numRows-1){
i++;
}else{
isDown=false;
i--;
j++;
}
}else{
if(i>0){
i--;
j++;
}else{
isDown=true;
i++;
}
}
}
StringBuilder sb=new StringBuilder();
for(i=0;i<numRows;i++){
for(j=0;j<numCols;j++){
if(cs[i][j]!='\u0000'){
sb.append(cs[i][j]);
}
}
}
return sb.toString();
}
}
|
看了一眼 Solution，它的 Sort By Row 的方法和上面类似，不过避免了大数组的使用，而且更加本质——轮流向每一行中填入字符即可，并不必须要保持好看的形状。
需要注意的是 Java 中对象数组需要自己进行实例化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public String convert(String s, int numRows) {
char[] sc=s.toCharArray();
if(sc.length<=numRows || numRows<=1) return s;
StringBuilder[] sbs=new StringBuilder[Math.min(numRows,sc.length)];
int curRow=0;
boolean isDown=false;
for(char c:sc){
if(sbs[curRow]==null) sbs[curRow]=new StringBuilder();
sbs[curRow].append(c);
if(curRow==0 || curRow==numRows-1) isDown=!isDown;
curRow+=isDown?1:-1;
}
StringBuilder ret=new StringBuilder();
for(StringBuilder sb:sbs) ret.append(sb);
return ret.toString();
}
}
|
最后一个办法，也是最有意思的，就是找到每个字符出现的规律：
- 每一行重复间隔 2*(numRows-1)
- 首末行中中必定出现字符每一个轮回中对应取模的字符
- 中间行中会出现重复间隔减去行数后取模的字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public String convert(String s, int numRows) {
char[] sc=s.toCharArray();
if(sc.length<=numRows || numRows<=1) return s;
int circleLen=2*(numRows-1);
StringBuilder ret=new StringBuilder();
for(int i=0;i<numRows;i++){
for(int j=0;i+j<sc.length;j+=circleLen){
ret.append(sc[i+j]);
if(i!=0 && i!=numRows-1 && j+circleLen-i<sc.length)
ret.append(sc[j+circleLen-i]);
}
}
return ret.toString();
}
}
|