1.問題
2.題目意思
給定一個字符串晶密，使它按照Z字型排列（說起來應(yīng)該是一個倒N字形吧）财松，這個Z字形的大小由傳入的參數(shù)決定，然后我們應(yīng)該返回一個順序讀的字符串
3.思路
當時找了個紙畫了一下扩然，不過等想起寫博客的時候紙已經(jīng)不見了……
為了 彌補我的過失觅闽，特地畫了一個狗血的示意圖帝雇。【processon.com】
按照圖中所示蛉拙，我們目前拿數(shù)組下標來表示數(shù)據(jù)尸闸，而且整個題目都會以數(shù)組下標作為關(guān)鍵。那我們的核心就是創(chuàng)建一個StringBuilder孕锄，直接從源字符串取數(shù)據(jù)進行append吮廉，像是一種沒有進行zigzag排序，直接進行合理的字符串選取.
- 圖中可以顯然知道numRows等于4畸肆，也就是說在字符串長度內(nèi)宦芦，首先訪問第一排數(shù)字 0，6轴脐，12 （這里我把轉(zhuǎn)折點理解做兩個重疊的數(shù)）调卑，參考下面的代碼，i = 0時豁辉，在字符串長度范圍內(nèi)令野，添加第一個字符舀患，
-
下一行代碼 j += 2*(numRows-i-1);是一個找規(guī)律找出來的數(shù)學公式徽级，有種像初中找規(guī)律的題，就是說我們要確定3這個轉(zhuǎn)折點到6這個轉(zhuǎn)折點中間有多少數(shù)據(jù)聊浅，當然我們口算都能答上來的問題餐抢，計算機可需要提示现使，那么我們看到下面的圖的數(shù)據(jù)
image.png
numRows = 4
0 --- 6 間隔6 （i = 0）
1 --- 5 間隔4 （i = 1）
2 --- 4 間隔2 （i = 2）
3 --- 3 間隔0 （i = 3）
那么我們把他轉(zhuǎn)換成一個找規(guī)律的數(shù)學題，小學生也可以找到規(guī)律吧旷痕，
6碳锈，4，2欺抗，0 也就是 2(4-i-1) 或者 2(numRows-i-1); 可以帶入值驗證一下售碳。
-
當然我們這個是不夠的，因為這是一個V的形狀绞呈， 倒V的形狀是一個反的公式贸人，2*i ，大家可以研究一下佃声。
image.png 那么這個循環(huán)就可以理解了艺智，訪問添加第一個字符，按照V型公式位移j圾亏，判斷位移后的j的合法性十拣，而且需要判斷是否是轉(zhuǎn)折點（因為我們剛才說假設(shè)轉(zhuǎn)折點兩個重復數(shù)據(jù)的情況，這里只需要添加一個才能滿足題意）志鹃，合法后添加字符串夭问，接著按照倒V型公式位移j，直到字符串遍歷完成曹铃。
while(j < s.length()){
sb.append(s.charAt(j));
j += 2*(numRows-i-1);
if(i!=numRows-1&&i!=0&&j<=s.length()-1)
{
sb.append(s.charAt(j));
}
j += 2*i;
}
- 最后的i循環(huán)甲喝，就是控制一層一層向下遍歷。此外一些特殊的情況铛只，numRows == 1的情況埠胖，直接返回，采用StringBuilder方式加快構(gòu)造字符串
4.代碼
class Solution {
public String convert(String s, int numRows) {
int j = 0;
if(numRows == 1){
return s;
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<numRows;i++){
j = i;
while(j < s.length()){
sb.append(s.charAt(j));
j += 2*(numRows-i-1);
if(i!=numRows-1&&i!=0&&j<=s.length()-1)
{
sb.append(s.charAt(j));
}
j += 2*i;
}
}
return sb.toString();
}
}
5.大佬算法
public String convert(String s, int nRows) {
char[] c = s.toCharArray();
int len = c.length;
StringBuffer[] sb = new StringBuffer[nRows];
for (int i = 0; i < sb.length; i++) sb[i] = new StringBuffer();
int i = 0;
while (i < len) {
for (int idx = 0; idx < nRows && i < len; idx++) // vertically down
sb[idx].append(c[i++]);
for (int idx = nRows-2; idx >= 1 && i < len; idx--) // obliquely up
sb[idx].append(c[i++]);
}
for (int idx = 1; idx < sb.length; idx++)
sb[0].append(sb[idx]);
return sb[0].toString();
}
這個算法淳玩，也算是空間換取時間吧直撤，建立一個StringBuffer數(shù)組，數(shù)組長度是nRows的長度蜕着，首先初始化谋竖，接著來一遍字符串循環(huán)，然后把豎行數(shù)據(jù)分別添加到StringBuffer[0] ,StringBuffer[1],StringBuffer[2] ……StringBuffer[nRows -1]承匣，然后下一個循環(huán)是把斜行數(shù)據(jù)存起來蓖乘，如此循環(huán)，那么我們就可以知道韧骗，StringBuffer[n] 存的就是第n橫行的數(shù)據(jù)嘉抒，這樣子在最后的循環(huán)中拼接到StringBuffer[0]上就行了。
6.根據(jù)大佬算法改進我的算法
class Solution {
public String convert(String s, int numRows) {
int i,j = 0;
if(numRows == 1){
return s;
}
StringBuffer[] sbs = new StringBuffer[numRows];
for ( i = 0; i < sbs.length; i++) sbs[i] = new StringBuffer();
i = 0;
while(j < s.length() && i < numRows){
sbs[i].append(s.charAt(j));
j += 2*(numRows-i-1);
if(i!=numRows-1&&i!=0&&j<=s.length()-1)
{
sbs[i].append(s.charAt(j));
}
j += 2*i;
if(s.length() <= j ){
j = ++i;
}
}
for (i = 1; i < sbs.length; i++)
sbs[0].append(sbs[i]);
return sbs[0].toString();
}
}
這樣優(yōu)化的話袍暴，從240ms的用時到了50多些侍，核心的思想隶症，也就是那個公式?jīng)]有變，增加了StringBuffer來數(shù)組來管理數(shù)據(jù)岗宣。
7.總結(jié)
人丑就得多讀書蚂会。
LeeCode 之旅繼續(xù).
