LeetCode 6: ZigZag Conversion (JAVA)

NO IMAGE

給一個String: "PAYPALISHIRING"
要求按豎Z字方法去排列再橫向讀出,給定行數R。
若 R = 3:
P   A   H   N
A P L S I I G
Y   I   R
則程式輸出應為 :"PAHNAPLSIIGYIR"
若R = 4 :
P     I    N
A   L S  I G
Y A   H R
P     I
程式輸出應為 : "PINALSIGYAHRPI"


分析:找規律,將每行當作一個研究物件,找出每個字母在原字串中index的代數規律。
找規律最簡單的方法就是多舉幾個例子,其實就是高中數學題中找陣列的規律。

本題的規律:
/*R=numRows
d=2R-2    1                           2R-1                         4R-3
d=        2                     2R-2  2R                    4R-4   4R-2
d=        3               2R-3        2R 1              4R-5       .
d=        .           .               .               .            .
d=        .       R 2                 .           3R               .
d=        R-1 R 1                     3R-3    3R-1                 5R-5
d=2R-2    R                           3R-2                         5R-4
*/

假設當前行數是r,總行數R,I(n)表示某行第n個字母在原字串中的index,n從0開始:
r=1或R時:I(n 1) = I(n) 2*(R-1)
1<r<R時:
I(n 1)=I(n) 2*(R-r),n為偶數
I(n 1)=I(n) 2*(r-1),n為奇數


public static String convert(String s, int numRows) {
if(s == null || s.length() == 0 || numRows ==1 || numRows >= s.length())
return s;
StringBuilder myString = new StringBuilder();
//第1行
for(int i = 1; i < s.length() 1;i =2*(numRows-1))
myString.append(s.charAt(i-1));
//中間
for(int i = 2; i < numRows;i  ) {
boolean k=true;
for(int j = i; j < s.length() 1;j = (k) ? 2*(numRows-i) : 2*(i-1),k=!k)
myString.append(s.charAt(j-1));
}
//第R行
for(int i = numRows;i<s.length() 1;i =2*(numRows-1))
myString.append(s.charAt(i-1));
return myString.toString();
}

討論: 這程式碼不快(32%),如果用String而不是StringBuilder會更慢大約兩倍,
優點在於書寫簡單邏輯清晰,如果面試碰到,這樣的程式碼應該夠了。

若文章中有錯誤或者各路大神有更好解法,歡迎評論。

Ref: If you are confused with zigzag pattern,come and see!