6. ZigZag Conversion (medium)
6.1.png
题目意思:将一个字符串按照之字形(zigzag)排列,然后按行输出,如下图:
6.2.png
- 核心思想:之字形排列可以分解为两步:向下竖直排列;斜向上排列,竖直在前,斜在后,通过两个循环分别实现两个分解动作,再通过一个大循环遍历所有元素
- 数组约束i与StringBuffer约束row相互独立,故分别判断i与row是否越界
- 学习了StringBuffer的用法,这里可以用StringBuilder,速度更快.因为StringBuffer是线程安全的,但StringBuilder不是,所以StringBuilder更快
- complexity analysis:
- time complexity: O(n / (2numsRow - 2))
- space complexity: O(n)
class Solution {
public String convert(String s, int numRows) {
char[] c = s.toCharArray();
int n = c.length;
StringBuffer[] currRow = new StringBuffer[numRows];
// 初始化StringBuffer
for (int row = 0; row < numRows; row++)
currRow[row] = new StringBuffer();
// zigzag可分解为两个基础步骤:竖直运动,倾斜运动
// i表示字符串中的字符索引,其大小由内部循环控制,故使用while
int i = 0;
while (i < n){
// 竖着添加
//因为i自加,所以每次循环都要检查i是否越界
for (int row = 0; row < numRows && i< n; row++){
currRow[row].append(c[i++]);
}
// 斜着添加
for (int row = numRows - 2; row > 0 && i< n; row--){
currRow[row].append(c[i++]);
}
}
//转换成一行字符
for (int row = 1; row < numRows; row++ )
currRow[0].append(currRow[row]);
return currRow[0].toString();
}
}
6.3.png
