第六題：Z字形變換
將一個(gè)給定字符串根據(jù)給定的行數(shù)何吝，以從上往下切蟋、從左到右進(jìn)行 Z 字形排列朱浴。
比如輸入字符串為 "LEETCODEISHIRING" 行數(shù)為 3 時(shí)呈昔，排列如下：
L C I R
E T O E S I I G
E D H N
之后蒿讥，你的輸出需要從左往右逐行讀取蝶念，產(chǎn)生出一個(gè)新的字符串抛腕，比如："LCIRETOESIIGEDHN"。
請(qǐng)你實(shí)現(xiàn)這個(gè)將字符串進(jìn)行指定行數(shù)變換的函數(shù)：
string convert(string s, int numRows);
示例 1:
輸入: s = "LEETCODEISHIRING", numRows = 3
輸出: "LCIRETOESIIGEDHN"
示例 2:
輸入: s = "LEETCODEISHIRING", numRows = 4
輸出: "LDREOEIIECIHNTSG"
解釋:
L D R
E O E I I
E C I H N
T S G
V1版本
最開始看到這題的時(shí)候是想弄一個(gè)二維數(shù)組媒殉，根據(jù)規(guī)律依次將字符串依次填入數(shù)組的相應(yīng)位置担敌，然后遍列輸出
可越想越不對(duì)勁，因?yàn)橹恍枰覀冚敵鲎詈蟮淖儞Q過后的字符串廷蓉，根本不需要我們打印Z字形
這下就好辦了全封，只需要去找取字符的規(guī)
對(duì)于字符串 LEETCODEISHIRING
行數(shù)為3的時(shí)候：
L C I R
E T O E S I I G
E D H N
下標(biāo) 中間間隔的步數(shù)
0 4 8 12 4 4
1 3 5 7 9 11 13 15 2 2
2 6 10 14 4 4
行數(shù)為4的時(shí)候：
L D R
E O E I I
E C I H N
T S G
下標(biāo) 中間間隔的步數(shù)
0 6 12 6 6
1 5 7 11 13 4 2
2 4 8 10 14 2 4
3 9 15 6 6
行數(shù)為6的時(shí)候：
下標(biāo) 中間間隔的步數(shù)
0 10 10 10
1 9 11 8 2
2 8 12 6 4
3 7 13 4 6
4 6 14 2 8
5 15 10 10
規(guī)率很好發(fā)現(xiàn)，第一列就是 0~numRows桃犬，
間隔的步長可以通過 numRows + numRows - 2 獲取到
頭和尾的步長是一樣的刹悴，從第二行起，步長就等于 步長 - 2 和 2交替變化疫萤，
繼續(xù)向下走 左邊的步長 -= 2颂跨，右邊步長 += 2
只需要考慮一下邊界問題
行數(shù)為 1的時(shí)候，返回的就是原字符串
行數(shù)為 2的時(shí)候扯饶，本想單獨(dú)處理的恒削，直接輸出 0，2尾序，4钓丰，6.....1，3每币，5.....
代碼如下
public String convert(String s, int numRows) {
// 返回本身
if (numRows == 1) {
return s;
}
// 用于記錄新字串的char數(shù)組
char[] chars = new char[s.length()];
// 間隔的步長
int length = numRows + numRows - 2;
// 新字串的下標(biāo)
int charIndex = 0;
// 記錄應(yīng)該從什么位置取老字串的值
int index = 0;
// 遍列的行數(shù)
int row = 0;
// 左右的間隔數(shù)
int intervalLeft = length, intervalRight = length;
// 單行的循環(huán)次數(shù)
int rowCycleNum = 1;
while (row < numRows) {
if (index < s.length()) {
chars[charIndex++] = s.charAt(index);
index += rowCycleNum++ % 2 == 1? intervalLeft : intervalRight;
} else {
index = ++row;
// 重置單行的循環(huán)次數(shù)
rowCycleNum = 1;
if (row == 1) {
intervalLeft = length - 2;
intervalRight = 2;
}
if (row == numRows - 1){
intervalLeft = length;
intervalRight = length;
}
if (row != 1 && row != numRows - 1){
intervalLeft -= 2;
intervalRight += 2;
}
}
}
return String.valueOf(chars);
}
時(shí)間還可以携丁，代碼還需要優(yōu)化一下
V2版本
V2版本是參考官方的 ##按行排序##
簡單點(diǎn)說就是，遍例字符串時(shí)兰怠，我能知道每個(gè)字符所在的行
我先遍例一次梦鉴，按順序?qū)⒆址謩e添加至行，最終在將幾個(gè)行組合起來成為最終的行
例：
L C I R
E T O E S I I G
E D H N
隨著字符串的例揭保，行號(hào)的變化為 0 1 2 1 0 1 2
0 0 0
1 1 1 1 1
2 2 2
代碼如下
public String convert(String s, int numRows) {
// 返回本身
if (numRows == 1) {
return s;
}
List<StringBuffer> list = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++) {
list.add(new StringBuffer());
}
// 記錄當(dāng)前行
int cruRow = 0;
boolean isAdd = false;
for (int i = 0; i < s.length(); i++) {
list.get(cruRow).append(s.charAt(i));
// 第次遇到兩端就取反
if (cruRow == 0 || cruRow == numRows -1) {
isAdd = !isAdd;
}
cruRow += isAdd? 1 : -1;
}
// 遍歷填充完后肥橙，逐行整合在一起返回
StringBuffer sb = new StringBuffer(s.length());
for (StringBuffer stringBuffer : list) {
sb.append(stringBuffer);
}
return sb.toString();
}
不過這種用list保存數(shù)據(jù)的方式本來就是空間利用不高，執(zhí)行效率也不是特別的高秸侣，算是多了解一種思路吧
V3版本
V3版本參數(shù)參考官方的 ##按行訪問## 不過官方的是用StringBuilder存筏，我覺得用數(shù)組會(huì)更好
以4行為例
首先只看整體部分，步長為6
L D R
E O E I I
E C I H N
T S G
下標(biāo) 步長
0 6 12 6
1 7 13 6
2 8 14 6
3 9 15 6
在看完整的
0 6 12
1 5 7 11 13
2 4 8 10 14
3 9 15
其實(shí)只有在非首尾行時(shí)味榛，每兩個(gè)數(shù)中間會(huì)多夾帶一個(gè)數(shù)椭坚，用這個(gè)數(shù)的步長也是有規(guī)律的
按照這種思想自己在實(shí)現(xiàn)一下
public String convert(String s, int numRows) {
// 返回本身
if (numRows == 1) {
return s;
}
int strLength = s.length();
// 依舊使用數(shù)組保存最終結(jié)果
char[] chars = new char[strLength];
int charIndex = 0;
// 步長
int length = numRows + numRows - 2;
// 第一個(gè)循環(huán)循環(huán)行
for (int i = 0; i < numRows; i++) {
// 第二個(gè)循環(huán)獲限當(dāng)前行的字符
for (int j = 0; i + j < strLength; j += length) {
// 這里獲取的是上面整體部分的值
chars[charIndex++] = s.charAt(i + j);
// 首行和尾行沒有多余的字符,超過字符長度也過濾
if (i == 0 || i == numRows - 1 || j + length - i >= strLength) {
continue;
}
/**
* 例：像上面所說行數(shù)為4時(shí)，j總是在 0 6 12中進(jìn)行變化
* 而中間的值總是相對(duì)于在 1 6 12的基礎(chǔ)上搏色， -1 -2的值
*/
chars[charIndex++] = s.charAt(j + length - i);
}
}
return String.valueOf(chars);
}
