ZigZag Conversion (LeetCode 6)

Question

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

Solution

这是一道数学题，就是找规律。

可以发现，字符在主列和主列之间。主列之间间隔的距离为step=2 (numRows - 1)。然后除了第一行和最后一行外，其他每行都要加中间的数。对于第i行，其主列和下一个主列之间元素的间距为interval=step - i 2，即如果当前主列为j，则下一个主列之间的元素插入位置为j + interval。逐行遍历直到结束。

代码如下：

public class Solution {
    public String convert(String s, int numRows) {
        if(s.length() == 0 || numRows == 1 || numRows >= s.length()){
            return s;
        }

        char[] res = new char[s.length()];
        int step = 2 * (numRows - 1);
        int count = 0;

        for(int i = 0; i < numRows; i++){
            int interval = step - 2 * i;
            for(int j = i; j < s.length(); j = j + step){
                res[count++] = s.charAt(j);
                //第一行（interval == step）和最后一行（interval == 0）不用加之间的数
                if(interval < step && interval > 0 && j + interval < s.length() && count < s.length()){
                    res[count++] = s.charAt(j + interval);
                }
            }
        }

        return new String(res);
    }
}