LeetCode_String #6. ZigZag Conversion (Easy)

NO IMAGE

題目:ZigZag Conversion

圖片描述

解題方法:

圖片描述

以這樣的方式畫出String更方便看出它的規律。

1 當numRows = 4的時候,第一行和最後一行position每次都是+6.
可以設一個 magicNum = 2 * numRows – 2;

2 再來看,中間的行數(除了第一行和最後一行), position 跳的規律發生變化,其實每次+6(magicNum) 還是存在,只不過中間多了一些char。
規律: 設一個 specialNum = magicNum;
行數每增加一行, specialNum - 2;
每次加完一個char,再加一次char(position=i specialNum)

舉例:
第二行的時候, magicNum = 6; specialNum = 4;
1- Position = 1, A, 加入A.
額外加入(Position specialNum = 1 4 = 5), L, 加入L.
2- Position = Position magicNum = 1 6 = 7, S, 加入S.
額外加入(Position specialNum = 7 4 = 11), I, 加入I.
3- Position = Position magicNum = 7 6 = 13, G, 加入G.

所以第二行加入的是: ALSIG.

程式碼:

public class Solution 
{
public String convert(String s, int numRows) 
{
if( s == null || s.length() == 0 || numRows <0)
return "";
if(numRows == 1)
return s;
StringBuilder res = new StringBuilder();
int magicNum = 2*numRows-2;
int specialNum = magicNum;
for(int i=0; i<numRows; i  )
{
for(int j=i; j<s.length(); j =magicNum)
{
res.append(s.charAt(j));
if(i>0 && i<numRows-1)
{
if(j specialNum < s.length())
res.append(s.charAt(j specialNum));
}
}
specialNum -= 2;
}
return res.toString();
}