題目描述

字串PAYPALISHIRING拿到給定的數字(比如3)並轉換為ZigZag型式後會變成

P   A   H   N
A P L S I I G
Y   I   R

然後輸出的字串就會變成PAHNAPLSIIGYIR
請寫出將字串轉為ZigZag型式的function

思路

找規律，並依規律的順序加入空字串中。

程式碼

class Solution {
public:
    string convert(string s, int numRows){
        if(numRows==1)
            return s;
        int diff=(numRows)*2-2;
        string ans="";
        for(int row=0;row<numRows;row++)
        {
            bool flag=false;
            for(int j=row;j<s.length();flag=flag?false:true)
            {
                ans=ans+s[j];
                if(row==0||row==numRows-1)
                	j+=diff;
                else if(flag)
                    j+=row*2;
                else
                    j+=(diff-row*2);
            }
        }
        return ans;
    }
};

心路歷程

其實也就是寫寫畫畫而已
如果將ZigZag壓扁，你會發現其實他是長這樣的(我以index表示)

0   10    20
1 9 11 19 21
2 8 12 18 22
3 7 13 17 23
4 6 14 16 24
5   15    25

大家有沒有發現他的順序是先下來在上去再下來。
接下來發現第一列和最後一列等差10
然後中間的分別差

第二列：8 2 8 2
第三列：6 4 6 4
第四列：4 6 4 6
第五列：2 8 2 8

發現規律了沒有！
8+2=10、6+4=10、4+6=10、2+8=10都是10，第一列和最後一列也都是等差10。
所以恭喜我們找到規律啦！按照規律應該出現的順序輸出就行了～