iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 12
0
自我挑戰組

有志者,事竟成。系列 第 12

Day12 LeetCode #6 ZigZag Conversion

題目描述

字串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=106+4=104+6=102+8=10都是10,第一列和最後一列也都是等差10。
所以恭喜我們找到規律啦!按照規律應該出現的順序輸出就行了~


上一篇
Day11 LeetCode #5 Longest Palindromic Substring
下一篇
Day13 LeetCode #7 Reverse Integer
系列文
有志者,事竟成。19

尚未有邦友留言

立即登入留言