ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".


Naive Way:我第一次做的时候以为3是个常数呢。这种zigzag scan 有规律可循啊，只要找到index的映射规律，就可以一次scan 实现。首先例子是一个nRows = 3的，写一个nRows = 4的。

P         I         N
A    L S      I  G
Y A    H R
P         I

首先看第一行，前一个和后一个的间隔是 2*nRows - 1(折点）-1(起点) -1(终点)，如果是步长就还要+1算上自己，那么步长就是 2*nRows-2，这个规律是普适的。
然后看第二行，前一个和中间那个的步长是 2*(nRows-1)-2，这个很好理解就是 减少了两个点。 注意到，竖直方向上前一个和竖直方向上后一个的步长还是 2*nRows-2，相当于之前分析部分起点+1, 终点+1。所以可以把中间部分的单独列出来考虑。
第三行就显而易见，竖直方向上第一个和中间的步长是2*(nRows-2)-2，因为又减少了两个。
第四行的情况和第一行一样。

总结一下就是，基本步长为2*nRows-2。如果不是第一行和最后一行，就要增加中间点，它和前一个竖直方向上的步长是 2*(nRows-index)-2，index是行的序号。还有就是nRows=1时，步长为0，不能统一，单独步长。

算法复杂度O(n), space O(n)。 一次扫描。

 public class Solution {  
   public String convert(String s, int nRows) {  
     StringBuilder str = new StringBuilder();  
     for(int i = 0;i < nRows;i++){  
       int j = i;  
       while(j < s.length()){  
         str.append(s.charAt(j));  
         if(i!=0 && i!=nRows-1 && j+2*(nRows-i)-2 < s.length())  
           str.append(s.charAt(j+2*(nRows-i)-2));  
         j += nRows==1?1:(2*nRows-2);  
       }  
     }  
     return str.toString();  
   }  
 }