数据结构算法之leetcode ZigZag Conversion

ZigZag转换就是将字符串按之字排列,然后按行输出。如字符串”PAYPALISHIRING”,ZigZag转换之后是

1
2
3
P A H N
A P L S I I G
Y I R

按行输出之后的字符串是”PAHNAPLSIIGYIR”。

用算法实现,参数为字符串和行数,返回按行输出的字符串。

题中给出了行数是奇数的排列方式,那么其对立面就是偶数,写出偶数的排列方式

1
2
3
4
P I I
A L S R N
Y A H I
P I

然后结合奇数和偶数的排列方式并未每个字符按照在原字符串中的顺序标上号之后(其实使用数字作为字符串进行ZigZag转换看的更清晰)发现其有一个数学规律,每两个主列上字符索引的差值为2row-2,而斜线上字符的索引不难看出是*下一个字符的索引减去两个当前字符所在行索引的值

发现这个普遍规律之后就万事大吉,可以写代码了吗?

我们发现了普遍的规律还应该去关注下特殊情况,也就是常说的边界值

边界值考虑:

  • 第一行和最后一行不存在斜线上的数据
  • 最后的一个之字可能不完整,如只有斜线上的数据

代码如下:

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
public String convert(String str, int numRows) {
if (numRows == 1){
return str;
}
StringBuffer stringBuffer = new StringBuffer();
for (int i=0; i<numRows; i++){
if ((str.length()-1) >= i) {
stringBuffer.append(str.charAt(i));
}
int index = i;
while ((str.length()-1) >= (index+numRows+(numRows-2))){
// 首行 && 尾行
// 注意边界值
if ((index+numRows+(numRows-2) > (index+numRows+(numRows-2)-i-i)) && ((index+numRows+(numRows-2)-i-i) > index) ){
stringBuffer.append(str.charAt(index+numRows+(numRows-2)-i-i));
}
stringBuffer.append(str.charAt(index + numRows + (numRows - 2)));
index = index+numRows+(numRows-2);
}
if (((str.length()-1) >= (index+numRows+(numRows-2)-i-i)) && ((index+numRows+(numRows-2)-i-i) != index)){
stringBuffer.append(str.charAt(index+numRows+(numRows-2)-i-i));
}
}
return stringBuffer.toString();
}

此方法感觉就是简单粗暴,从排列中归纳出规律,按照公式进行编码。

但是总感觉应该有更好的方法或者更加高大上一点,然后并没有找到什么好的算法,普遍都是这种利用规律来解答。

前面说没有好的算法并不代表没有那些特立独行的方法,如下面这个就是如此的简单直接和自信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static String conv(String str, int row){
StringBuffer[] sbArr = new StringBuffer[row];
for (int i=0; i<row; i++){
sbArr[i] = new StringBuffer();
}
int i = 0;
while (i < str.length()){
for (int rowIndex=0;rowIndex<row && i<str.length();rowIndex++){
sbArr[rowIndex].append(str.charAt(i++));
}
for (int rowIndex=row-2;rowIndex>=1 && i<str.length(); rowIndex--){
sbArr[rowIndex].append(str.charAt(i++));
}
}
for (int r=1; r<row; r++){
sbArr[0].append(sbArr[r]);
}
return sbArr[0].toString();
}

之所以说这个代码写出来很自信,就貌似有人让你打印10遍hello world,而你就直接写了10遍的System.out.println("hello world");

您的肯定,是我装逼的最大的动力!