ZigZag Conversion

Q:
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".
A:
就是，用一个数组，来按照zigzag的方式，跑完，再逐行取出来就行。

public class Solution {
    public String convert(String s, int nRows) {
        if(nRows == 1)
            return s;
        List<StringBuilder> list = new LinkedList();
        for(int i =0;i<nRows;i++)
            list.add(new StringBuilder());
        while(!s.isEmpty()){
            String str = s.substring(0,Math.min(s.length(),nRows*2-2));
            s = s.substring(Math.min(s.length(),nRows*2-2));
            for(int i =0;i<nRows;i++){
                if(i>=str.length())
                    break;
                list.get(i).append(str.charAt(i));
            }
            for(int i = 0;i<nRows-2;i++){
                if(i+nRows>= str.length())
                    break;
                list.get(nRows-2-i).append(str.charAt(nRows+i));
            }
        }
        StringBuilder buf = new StringBuilder();
        for(StringBuilder tmp : list)
            buf.append(tmp.toString());
        return buf.toString();
    }
} 

Mistakes:
1:  当update index 出界的时候， 我们检查了出界的情况，并更正之，  这个时候，要记得把 k 退回去一个。
2: 哎，一直是column number计算地不对。      应该一下一上，半个zigzag，是nRow-1列

------------------- 第二遍-------------
1：  刚开始，列数计算的不对：
        int nCols = (s.length() / (2 * nRows - 2) + 1) * (nRows-1);

2：  填充char数组的时候，j的update 也犯错了。  因为，在向上的时候， j++了。但是，在向下的时候，没有++. 导致， 二者不协调。 
3： 又一次，  当减掉一个数的时候， 有可能就是0 啊，什么的，  要 小心对待。
因此，这里错在没有先检查 nRow -1 是否== 1    对于特例，要 特殊处理。

4: 当  nRows == 2的时候， 向上是没有列数的增加的， 因此，要小心哦。

Learned:

---------------第二遍代码----------------（不聪明的地方，就在于根据列数计算向上还是向下。 ，不如第一次，用个boolean表示向上，向下。 简单，易懂，不会犯错）

public class Solution {
public String convert(String s, int nRows) {
        if (s == null || s.length() == 0)
            return "";
            
        if(nRows == 1)
                return s;
        int nCols = (s.length() / (2 * nRows - 2) + 1) * (nRows-1);
        // assume char ch = 0 is not used in nRows
        char[][] A = new char[nRows][nCols];
        for (int i = 0; i < nRows; i++)
            for (int j = 0; j < nCols; j++)
                A[i][j] = 0;
        int indexS = 0;
        for (int j = 0; j < nCols; ) {
            if (j % (nRows-1) == 0){ // going down
                for (int i = 0; i < nRows; i++){
                    if(indexS >= s.length())
                        break;
                    A[i][j] = s.charAt(indexS++);
                }
                j++;
            }
            else{
                // going up
                for (int i = nRows - 2; i >= 1; i--){
                    if(indexS >= s.length())
                        break;
                    A[i][j++] = s.charAt(indexS++);
                }
            }
            if(indexS >= s.length())
                break;
        }
        // read the matrix to get result
        StringBuffer buf = new StringBuffer();
        for (int i = 0; i < nRows; i++)
            for (int j = 0; j < nCols; j++)
                if (A[i][j] != 0)
                    buf.append(A[i][j]);
        return buf.toString();
    }
}

根据上面的算法，  空间复杂度和时间复杂度都太高。
一个小小的技巧就是每次upward的时候，列数并不变。
这样，空间和时间都变成了O(n)

public class Solution { 
    public String convert(String s, int numRows) {
        int start = 0;
        if(numRows == 1)
            return s;
        char[][] A = new char[numRows][s.length()/(2*numRows-2) *2 +2];
        for(int i =0;i<numRows;i++)
            Arrays.fill(A[i],'@');
        int t = 0, col = 0;
        while(t<s.length()){
            for(int i = 0;i<numRows;i++){
                if(t>=s.length())
                    break;
                A[i][col] = s.charAt(t++);
            }
            col++;
            for(int i = numRows-2;i>0;i--){
                if(t>=s.length())
                    break;
                A[i][col]=s.charAt(t++);
            }
            col++;
        }
        StringBuffer buf = new StringBuffer();
        for(int i =0;i<A.length;i++)
            for(int j =0;j<A[0].length;j++)
                if(A[i][j] != '@')
                    buf.append(A[i][j]);
        return buf.toString();
    }
}

Mistakes:
1: 当有除法儿的时候， 一定要检测是否  divided by zero.

-----------  3 rd pass ----------- calculate the index directly --------
就是分成一上一下  一对pair,

public class Solution { 
    public String convert(String s, int nRows) {
        if(nRows==1)
            return s;
        StringBuffer buf = new StringBuffer();
        for(int i =0;i<nRows;i++){ 
            for(int j =0;j<s.length()/(nRows*2-2)+1;j++){ 
                int index1 = j*(nRows*2-2)+i;
                if(index1<s.length())
                    buf.append(s.charAt(index1));
                int index2 = j*(nRows*2-2)+(nRows*2-2-i);
                if(i!=0 && i!= nRows-1 && index2<s.length())
                    buf.append(s.charAt(index2));
            }
        }
        return buf.toString();
    }
} 

Mistakes:
1:  当检测 第二个char的时候，应该是 既不是第一行，也不是第二行。  应该用&& ,结果写成了用 || .   这个比较SB
2： 又一次，除法的时候，没有检查是否divide by zero