LeetCode-ZigZag Conversion

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%numRows==0?sc.length/numRows:sc.length/numRows+1;
// int numCols=(sc.length/(2*numRows-2)+1)*(numRows-1);
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();
}
}