LeetCode解析（六）： 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:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Explanation:
P   A   H   N
A P L S I I G
Y   I   R



Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

难度：Medium

解析：将原字符串按照给出的行数，以Z字型重新排序，输出排序后的字符串。

方法一：寻找规律遍历（★★★★）

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
|P     |I    |N
|A   L |S  I |G
|Y A   |H R  |
|P     |I    |
  n=1    n=2   n=3

即如下图：
| 0     | 6     | 12
| 1   5 | 7  11 | 13
| 2 4   | 8 10  |
| 3     | 9     |
  n=1     n=2     n=3

总结：
  第n个
| a     | 
| b   f |
| c e   | 
| d     | 
可知：
第一部分：
a =  0 + （n-1） * （numRows * 2 - 2）
b =  1 + （n-1） * （numRows * 2 - 2）
c =  2 + （n-1） * （numRows * 2 - 2）
·
·
·
d = （numRows -1） + (n-1) * （numRows * 2 - 2）

第二部分：
e = (2n-1) * （numRows * 2 - 2） - c
f =  (2n-1) * （numRows * 2 - 2） - b

按照Z字型重新排序，可以发现一些规律：
（1）第一行：第一个字符是原字符串的第0个字符，第二个是原字符串的第numRows * 2 - 2个字符，第三个为 2 * （numRows * 2 - 2），依次类推。
（2）最后一行：第一个字符是原字符串的第（numRows -1）个字符，第二个是原字符串的第（numRows -1） +（numRows * 2 - 2）个字符，第三个为（numRows -1） + 2 * （numRows * 2 - 2），依次类推。
（3）从第二行至倒数第二行：也存在类似于（2）中的规律。

class Solution {
    public String convert(String s, int numRows) {
        
        if (numRows == 1) return s;

        StringBuilder ret = new StringBuilder();
        
        int basic = numRows * 2 - 2 ;
        char[] c = s.toCharArray();
        for(int i = 0 ; i < numRows ; i++){
            if( i == 0 ){
                for(int n = 0 ; n < s.length() ; n += basic){
                    ret.append(c[n]);
                }
                
            }else if(i == numRows -1){
                for(int n = numRows -1 ; n < s.length() ; n += basic){
                    ret.append(c[n]);
                }
            }else{
                int sub = basic - i * 2;
                for(int n = i ; n < s.length() ; n += basic){
                    ret.append(c[n]);
                    if(n + sub < s.length()){
                        ret.append(c[n + sub]);
                    }
                    
                }
            }
        }
        
        return ret.toString();
    }
}

结果：Runtime : 17 ms，beats 99.99% of Java submission.
备注：时间复杂度O(n)。

LeetCode解析（六）： ZigZag Conversion

难度：Medium

方法一：寻找规律遍历（★★★★）

推荐阅读更多精彩内容