我現(xiàn)在在做一個叫《leetbook》的開源書項目，把解題思路都同步更新到github上了，需要的同學可以去看看
地址：https://github.com/hk029/leetcode
這個是書的地址：https://hk029.gitbooks.io/leetbook/

這里寫圖片描述

006.ZigZag Conversion[E]

題目

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)

這里寫圖片描述

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

思路1——用字符串數(shù)組

我能說我一開始完全沒看懂嗎？我是根據(jù)Custom Testcase自己慢慢測試摸索出來的。
其實，應該是這樣的
2行：
A _ C _ E _
_ B _ D _ F

3行：
A _ _ _ E _ _ _ I _ _ _
_ B _ D _ F _ H _ J _
_ _ C _ _ _ G _ _ _ K

所以有個簡單的思路：

• 每行弄個string。
• 對原始字符串進行掃描，從上往下，從下往上，依次加入每行的string
• 最后把所有的string拼接起來

 class Solution {
public:
    string convert(string s, int numRows) {
        string str[numRows],tmp;
        if(numRows == 1)
            return s;
        int flag;
        for(int i = 0,j = 0;i < s.length(); i++)
        {
            if(j == 0)
                flag = 1;
            if(j == numRows-1)
                flag = -1;
            str[j] += s[i];
            j += flag;            
        }
        for(int i = 0; i < numRows;i++){
            tmp += str[i];
        }
        return tmp;
    }
};

思路2——觀察規(guī)律

2行：
A _ C _ E _
_ B _ D _ F

3行：
<font color=red>A </font>_ _ _ <font color=red>E </font>_ _ _ <font color=red>I </font>_ _ _
_ B _ D _ F _ H _ J _
_ _ C_ _ _ G _ _ _ K

4行：
<font color=red>A </font>_ _ _ _ _ <font color=red> G </font>_ _ _ _ _
_ B _ _ _ F _ H _ _ _
_ _ C _ E _ _ _ I _ K
_ _ _ D _ _ _ _ _ J

觀察規(guī)律后，以每行的元素作為軸，可以發(fā)現(xiàn)，下面的字母都是對稱排列的
換成對應的index后，規(guī)律更明顯
<font color=red>0 </font>_ _ _ <font color=red>4 </font>_ _ _ <font color=red>8 </font>_ _ _
_ 1 _ 3 _ 5 _ 7 _ 9 _
_ _ 2 _ _ _ 6 _ _ _ 10

第2層的元素就是以第一行的元素為軸，+1,-1
第三層的元素就是以第一行的元素為軸，+2,-2
……
但是最后一層的元素，由于其特殊性，我們可以只考慮+k

Ps.所有過界的元素都不考慮

軸也有規(guī)律：除了首尾兩層，其他都是2個，所以第一層每隔2n-2出現(xiàn)一次。

class Solution {
public:
    string convert(string s, int numRows)
    {
        string tmp;
        if(numRows == 1)
            return s;
        int inc = 2*numRows-2;  //每次軸增加的步長
        int len = s.length();
        for(int i = 0; i < numRows;i++)
        {
            for(int j = 0;j < s.length()+numRows; j += inc)
            {
                if(j - i > 0 && j - i < s.length() 
                && i != 0 && i != numRows -1)  //首，尾只考慮+不考慮-
                    tmp+= s[j-i];
                if(j + i < s.length())
                    tmp += s[j+i];
            }
        }
        return tmp;
    }
};