LeetCode 6. ZigZag Conversion

原题链接在这里：https://leetcode.com/problems/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".

题解：

e.g. 若是给出0,1,2,3.....11. numRow = 4

0　　  　　6

1　　5　　7　　11

2　　4　　8　　10

3　　 　　 9

Find routine, 发现第一行和最后一行, 每两位之间差了interval = 2*(numRow-1).

中间行每两位之间交替差了interval - 2*i, 2*i(i 为行数，从0开始).

采用方法是每隔interval都加上一位，然后判断当前若不是第一行和最后一行就再在加完的数位后再加一个s.charAt(j+interval-2*i).

外层loop的 i 是行数, 内层loop的 j 是string要加位置的index.

Note:numRows == 1的情况要单独拿出来讨论。若是numRows == 1时, interval = 0, 进入内层循环，j+=interval 就不会动是infinite loop.

Time Complexity: O(s.length()), 外层循环用了numRows, 内层循环用了s.length()/numRows, 所以用了 numRows * (s.length()/numRows) = s.length().

Space: O(s.length()), StringBuilder 的大小.

AC Java:

public class Solution {
    public String convert(String s, int numRows) {
        if(s == null || s.length() == 0){
            return s;
        }
        if(numRows == 1){
            return s;
        }
        StringBuilder sb = new StringBuilder();
        int interval = 2*numRows-2;
        for(int i = 0; i<numRows; i++){
            for(int j = i; j<s.length(); j+=interval){
                sb.append(s.charAt(j));
                if(i != 0 && i != numRows-1 && j+interval-2*i < s.length()){
                    sb.append(s.charAt(j + interval - 2*i));
                }
            }
        }
        return sb.toString();
    }
}