6. ZigZag Conversion (medium)
6.1.png
題目意思:將一個字符串按照之字形(zigzag)排列,然后按行輸出,如下圖:
6.2.png
- 核心思想:之字形排列可以分解為兩步:向下豎直排列;斜向上排列,豎直在前,斜在后,通過兩個循環(huán)分別實現兩個分解動作,再通過一個大循環(huán)遍歷所有元素
- 數組約束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表示字符串中的字符索引,其大小由內部循環(huán)控制,故使用while
int i = 0;
while (i < n){
// 豎著添加
//因為i自加,所以每次循環(huán)都要檢查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
