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

解题思路

这道题的难点在于通过题目描述很难理解zigzag的遍历顺序。为此笔者在网上找到一张比较形象的图，如下：

接下来这道题的难度是找规律，从图中可以看到，首行和尾行相邻两个元素之间的距离是2*(numRows - 1)

首行和尾行之间的其他行除了像首位两行一样有间隔距离2*(numRows - 1)的元素，如，1，7和2，8，在它们之间还有一个元素，该元素到该行下一个元素的距离为2*i，i为所在行数，所以到上一个元素的距离为2*(numRows -1) - 2*i。

注意事项

注意理解题目的意思，注意边界条件。

参考答案

public class Solution {
    public String convert(String s, int nRows) {
        int length = s.length();
        if (length <= nRows || nRows == 1) return s;
        char[] chars = new char[length];
        int step = 2 * (nRows - 1);
        int count = 0;
        for (int i = 0; i < nRows; i++){
            int interval = step - 2 * i;
            for (int j = i; j < length; j += step){
                chars[count] = s.charAt(j);
                count++;
                if (interval < step && interval > 0 
    && j + interval < length && count <  length){
                    chars[count] = s.charAt(j + interval);
                    count++;
                }
            }
        }
        return new String(chars);
    }
}