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".

Ref:http://blog.unieagle.net/2012/11/08/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Azigzag-conversion/

public class Solution {
    public String convert(String s, int nRows) {
        if (s == null || s.length() == 0 || nRows <= 1) 
            return s;
        
        StringBuilder ret = new StringBuilder();
        int zigsize = 2*nRows -2;
        for(int i = 0; i<nRows; ++i){
            for(int base = i; ; base += zigsize){
                if(base >= s.length()) // index 从0开始
                    break;
                ret.append(s.charAt(base));
                if(i>0 && i < nRows-1){
                    int ti = base+zigsize -2*i;
                    if(ti < s.length())
                        ret.append(s.charAt(ti));
                }
            }
        }
        return ret.toString();
        
    }
}

直观的算法，写一下不同行数下的例子就能找到规律了。

 nRows =20246...1357

 nRows =3048...135792610

 nRows =40612...157112481039

先计算一下每一个zig包含的字符个数，实际上是zigSize = nRows + nRows – 2
然后一行一行的加s中的特定元素就行。
第一行和最后一行都只需要加一个字符，每一个zig，而且在s中的index间隔是zigSize。
中间每一行需要添加两个字符到结果中去。第一个字符同上；第二个字符和前面添加这个字符在s上的inde相差正好是zigSize – 2*ir。ir是行index。