乘风破浪：LeetCode真题_006_ZigZag Conversion
一、前言
到这里我们对基本的问题有了一定的理解，其中字符串的操作一直是一个比较困难的问题，这一点我们需要认真对待，采用合理的方案去解决问题。下面我们就看看将字符串按照某种格式排列之后再按行输出的问题。
二、ZigZag Conversion
2.1 问题理解
2.2 分析以解决问题
看到这样的问题我们最直接的想法就是构造一个二维数组，初始化成某种字符，然后按照题目给定的规则进行填充，填充完成之后按行进行遍历，将结果拼凑起来输出出去。这种方法复杂度为O(n~2)。因此我们进行优化，采用StringBuilder这样的结构来直接进行存储，能够将时间复杂度缩小到O(n)。
下面是官方的解法：
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++)
rows.add(new StringBuilder());
int curRow = 0;
boolean goingDown = false;
for (char c : s.toCharArray()) {
rows.get(curRow).append(c);
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
StringBuilder ret = new StringBuilder();
for (StringBuilder row : rows) ret.append(row);
return ret.toString();
}
}我们的算法：
public class Solution {
/**
* 题目大意
* 输入一个字符串和指定的行数，将字符以Z字型输出。
*
* 解题思路
* 计算出字符的最大列数，根据列数和行数创建一个一维数组，再计算每个字符中一维数组中的位置，
* 再对一维数组中的字符进行紧凑操作，返回结果。
* </pre>
*
* @param s
* @param nRows
* @return
*/
public String convert(String s, int nRows) {
if (s == null || s.length() <= nRows || nRows == 1) {
return s;
}
int index = s.length();
int rowLength = 0; // 计算行的长度，包括最后换行字符
int slash = nRows - 2; // 一个斜线除去首尾所占用的行数
while (index > 0) {
// 竖形的一列
index -= nRows;
rowLength++;
// 斜着的列数
for (int i = 0; i < slash && index > 0; i++) {
rowLength++;
index--;
}
}
char[] result = new char[nRows * rowLength]; // 保存结果的数组，最后一列用于保存换行符
for (int i = 0; i < result.length; i++) { // 初始化为空格
result[i] = ' ';
}
int curColumn = 0; // 当前处理的行数
index = 0;
while (index < s.length()) {
// 处理竖线
for (int i = 0; i < nRows && index < s.length(); i++) {
result[rowLength * i + curColumn] = s.charAt(index);
index++;
}
curColumn++;
// 处理斜线
for (int i = nRows - 2; i > 0 && index < s.length(); i--) {
result[rowLength * i + curColumn] = s.charAt(index);
curColumn++;
index++;
}
}
// 对字符数组进行紧凑操作
index = 0;
while (index < s.length() && result[index] != ' ') { // 找第一个是空格的字符位置
index++;
}
int next = index + 1;
while (index < s.length()) {
while (next < result.length && result[next] == ' ') { // 找不是空格的元素
next++;
}
result[index] = result[next];
index++;
next++;
}
return new String(result, 0, index);
}
}
这样的算法其实就是笨办法了，首先计算出虚拟的二维数组需要的空间大小，然后实际上（物理上）用一维数组来表示，并且初始化为空，之后将源字符串的字符按照规则填到虚拟的二维数组中，其实是一维数组，最后将一维数组中的空格去除掉就得到了想要的结果，显然是一个O(n~2)的算法，没有官方的好。
三、总结
通过这样的一个例子，我们可以发现往往我们的原始想法都是暴力法，按部就班的来，只要稍微的优化一下就能变成更好的方法，得到更优质的结果，写更少的代码。