@NewWorld
2016-09-25T23:16:12.000000Z
字数 1781
阅读 1703
LeetCode
题目链接:ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
第一版代码,通过模拟ZigZag Conversion的过程得到一个字符矩阵,然后遍历矩阵得到结果,代码比较丑,然而我也不想改了,将就看吧:
public class Solution {
public String convert(String s, int numRows) {
if (s == null || numRows == 1) {
return s;
}
int length = s.length();
int baseRows = numRows - 1;
// 计算结果矩阵的列数
int numColumns = (length / (numRows + numRows-2)) * baseRows;
int remainder = length % (numRows + numRows-2);
if (remainder > numRows) {
numColumns += 1+remainder-numRows;
} else if (0 < remainder && remainder <= numRows) {
numColumns++;
}
char[][] temp = new char[numRows][numColumns];
// 模拟 ZigZag Conversion 过程,构造字符矩阵
for (int j = 0, index = 0; j < numColumns; j++) {
if ((j % baseRows) == 0) {
for (int i = 0; i < numRows && index < length; i++,index++) {
temp[i][j] = s.charAt(index);
}
} else {
for (int i = numRows-2; i > 0 && index < length; i--,j++,index++) {
temp[i][j] = s.charAt(index);
}
j--;
}
}
// 先行后列遍历矩阵,取出结果
StringBuilder val = new StringBuilder();
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numColumns; j++) {
if (temp[i][j] != 0) {
val.append(temp[i][j]);
}
}
}
return val.toString();
}
}
第二版代码,直接计算字符出现的顺序,不构造矩阵:
public class Solution {
public String convert(String s, int numRows) {
if (s == null || numRows == 1) {
return s;
}
int len = s.length();
StringBuilder val = new StringBuilder();
// 逐行添加字符
for (int i=0; i<numRows; i++) {
// 这里为了区分下降和上升两种情况,设置了一个布尔变量来进行控制
boolean flag = true;
for (int j=i; j<len; flag=!flag) { // 下降和上升总是交替的
int pos = j;
if (flag) {
j += (numRows-i-1)*2; // 接下来是下降,很显然要填满下面的行(画一个凹曲线)
} else {
j += i*2; // 接下来是上升,很显然要填满上面的行(画一个凸曲线)
}
if (j == pos) { // 当前值处在矩阵边界
continue;
}
val.append(s.charAt(pos));
}
}
return val.toString();
}
}