以下题干翻译自LeetCode,原文题目请参见LeetCode网址: ZigZagConversion
有一个字符串"PAYPALISHIRING"
,当使用ZigZag模式写,并且指定了对应的行数时,如下所示(最好设置一个定长的字体来看):
P A H N
A P L S I I G
Y I R
然后我们要将上面的显示格式一行行读出来,得到另一个字符串"PAHNAPLSIIGYIR"
。
现在请编写代码实现这一转换,当输入一个字符串,并且指定了输出行数的时候,返回转换后的字符串:
string convert(string text, int nRows);
e.g. convert("PAYPALISHIRING", 3)
应该返回 "PAHNAPLSIIGYIR".
把这道题写出来的原因是我在写第一种算法时,测得的效率只在LeetCode中排名后3%,特别沮丧!
而后我又思考了一会,然后写出了第二种算法,测试后发现效率排在了前2%!
所以在这里也整理一下自己的思路,供以后回顾温习。
算法一(慢)
算法一主要分两块逻辑
- 按照ZigZag顺序向一个多维数组中放入字符
- 按照一行一行的顺序将多维数组放入StringBuilder
public String convert(String s, int numRows) {
if (numRows == 1) return s;
int sign = -1;
char[][] chars = new char[numRows][s.length()];
for (int idx = 0, row = 0, col = 0; idx < s.length(); ++idx) {
chars[row][col] = s.charAt(idx);
if (row == 0 || row == numRows - 1) {
sign *= -1;
}
row += sign;
if (idx != 0 && idx % (numRows - 1) == 0) {
++col;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0, j = 0; i < numRows && j < s.length(); ++j) {
if (chars[i][j] != 0) {
sb.append(chars[i][j]);
}
if (j != 0 && j % (s.length() - 1) == 0) {
++i;
j = -1;
}
}
return sb.toString();
}
算法二(快)
直接根据ZigZag顺序特点,找到按一行一行顺序对应每个字符在字符串中的下标,顺序放入一维数组中。
要注意的是当行数大于3时,需要考虑步长步短的问题。
public String convert(String s, int numRows) {
if (numRows == 1) return s;
char[] result = new char[s.length()];
int resultIdx = 0;
for (int curRow = 0; curRow < numRows; ++curRow) {
int stepLen1 = 2 * (numRows - 1 - curRow);
int stepLen2 = 2 * (curRow );
if (stepLen1 < 1) stepLen1 = stepLen2;
if (stepLen2 < 1) stepLen2 = stepLen1;
for (int strIdx = curRow, step = 1; strIdx < s.length(); ++step) {
result[resultIdx] = s.charAt(strIdx);
++resultIdx;
int steplen = step % 2 == 0 ? stepLen2 : stepLen1;
strIdx += steplen ;
}
}
return String.valueOf(result);
}
以上这两种算法,虽说复杂度都是O(s.length()),但算法二使用了一维数组,且不再需要StringBuilder进行重组,速度上当然快了很多。但是从易思考的角度来说,算法一其实更符合一个思维的过程,二更偏向于规律的寻找和利用。
最后,在开发过程中,还是得要在保证功能正确和时间充裕的前提下,进行效率的提升,不要本末倒置,忘了项目真正的意义。