LeetCode 6. ZigZag ConversionZ字形转换

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 s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

直接跳转法(横着走)

按照规律走，对于第一行和最后一行，我们能够能发现，一个元素到他的下一个元素的距离为2 * numRow - 2。

对于中间的元素，我们能都发现他的下一元素与其步长有关。我们可以从每列的第一个元素A开始算起，到满列的元素C的距离为2 * numRow - 2。达到下一个满列元素之前必然会遇到一个元素B。即A->B->C的总距离为2 * numRow - 2。同时有A->B 的距离加上 B->C的距离等于总距离。因此步长为step(B -> C) = 2 * numRows - 2 - step(A->B)。

上述很容易通过画出图以及下标来进行验证。这样时间复杂度为O(n)，空间复杂度为O(n^2)

public String convert(String s, int numRows) {
        if(numRows == 1){
            return s;
        }
        
        StringBuilder res = new StringBuilder();
        int len = s.length();
        for(int i = 0; i < len; i = i + 2 * numRows - 2){
            res.append(s.charAt(i));
        }
        
        for(int i = 1; i < numRows - 1; i++){
            int step = 2*i;
            int index = i;
            while(index < len){
                res.append(s.charAt(index));
                step = 2 * numRows - 2 - step;
                index += step;
            }
        }
        
        for(int i = numRows - 1; i < len; i = i + 2 * numRows - 2){
            res.append(s.charAt(i));
        }
        
        return res.toString();
    }

拉链法（竖着走）

拼接法是按着原来的字符串的顺序走。与拉链法类似。设置一个长度为numRows的数组，每个数组对应着一个链表。然后将字符串的每个字符加入到对应的位置。按链表的方式输出字符串。这样时间复杂度为O(n)，空间复杂度为O(n^2)

public String convert(String s, int numRows) {

    if (numRows == 1) return s;

    List<StringBuilder> rows = new ArrayList<>();
    for (int i = 0; i < Math.min(numRows, s.length()); i++)
        rows.add(new StringBuilder());

    int curRow = 0;
    boolean goingDown = false;

    for (char c : s.toCharArray()) {
        rows.get(curRow).append(c);
        if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
        curRow += goingDown ? 1 : -1;
    }

    StringBuilder ret = new StringBuilder();
    for (StringBuilder row : rows) ret.append(row);
    return ret.toString();
}