学步园

题目:

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

题意解析:

The key here is to figure out the index pattern, just draw several concrete example could hele:

nRow = 2:

0 2 4 6 8 10 12
1 3 5 7 9 11 13

nRow = 3: 

0     4      8     12 
1  3  5   7  9  11
2     6     10

nRow = 4:
0      6       12
1   5  7    11 13
2 4    8  10
3      9

第0, len-1行各个字符之间的间隔为2×nRows - 2
第1~len-2行之间会有两个固定间隔之间会有其他字符插入

规律：index + 2 * nRows - 2 * i - 2, 这里i是指行号

public class Solution {
    public static String convert(String s, int nRows) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (s == null || s.length() == 0 || nRows <= 1) {
            return s;
        }

        String result = generate(s, nRows);
        return result;
    }

    private String generate(String s, int nRows) {
        int len = s.length();
        StringBuffer buffer = new StringBuffer();
        int diff = 2 * nRows - 2;
        for (int i = 0; i < nRows && i < len; i++) {
            if (i == 0 || i == nRows - 1) {
                buffer.append(s.charAt(i));
                int index = i;
                while (index + diff < len) {
                    buffer.append(s.charAt(index + diff));
                    index = index + diff;
                }
//                int tmp = i;
//                while (i + diff < len) {
//                    buffer.append(s.charAt(i + diff));
//                    i = i + diff;
//                }
//                i = tmp;
            } else {
                buffer.append(s.charAt(i));
//                int tmp = i;
                int index = i;
                while (2 * nRows - 2 * i - 2 + index < len
                        || index + diff < len) {
                    if(2 * nRows - 2 * i - 2 + index < len){
                        buffer.append(s.charAt(2 * nRows - 2 * i - 2 + index));
                    }
                    if (index + diff < len) {
                        buffer.append(s.charAt(index + diff));
                    }
                    index += diff;
                }
//                while (2 * nRows - i - 2 < len || i + diff < len) {
//                    if (2 * nRows - i - 2 < len && 2 * nRows - i - 2 >= 0) {
//                        buffer.append(s.charAt(2 * nRows - i - 2));
//                    }
//                    if (i + diff < len) {
//                        buffer.append(s.charAt(i + diff));
//                    }
//                    i = i + diff;
//                }
//                i = tmp;
            }
        }
        return buffer.toString();
    }
}

class Solution {
public:
    string convert(string s, int nRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string result;
        if (nRows < 2) return s;
        for (int i = 0;i < nRows;++i) {
            for (int j = i;j < s.length();j += 2 * (nRows - 1)) {
                result.push_back(s[j]);
                if (i > 0 && i < nRows - 1) {
                    if (j + 2 * (nRows - i - 1) < s.length())
                        result.push_back(s[j + 2 * (nRows - i - 1)]);
                }
            }
        }
        return result;
    }
};