leetcode中如何解決ZigZag Conversion問題

這篇文章將為大家詳細講解有關leetcode中如何解決ZigZag Conversion問題，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

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

題意：

鋸齒形（Z字形）的變換。變換形式如下所示：

A）行數為兩行的情形：
0 2 4
1 3 6

B）行數為三行的情形：
0   4   8
1 3 5 7 9
2   6   10

C）行數為四行的情形：      
0     6      12
1   5 7   11 13
2 4   8 10   14
3     9      15

D）行數為七行的情形：
第一行：0             12                24
第二行：1          11 13             23 25
第三行：2       10    14          22    26
第四行：3     9       15       21       27
第五行：4   8         16    20          28
第六行：5 7           17 19             29
第七行：6             18                30

觀察上面情形可知：

1）第一行和最后一行兩個元素之間的距離是：（行數 － 1）* 2

2）中間幾行中第一個元素與第二個元素和第二個元素與第三個元素間的距離和是：（行數 － 1）* 2.

3）中間幾行中第一個元素和第二個元素間的距離與第幾行的關系：（行數－第幾行）* 2.

4）中間幾行中第二個元素和第三個元素間的距離與第幾行的關系：（第幾行 － 1） * 2.

故有getIndex()函數：

1）如果是每行的第一個元素，直接返回行數。

2）如果是第一行或者最后一行的除首元素外的下標獲取：前一個元素的下標 ＋ （行數 － 1）* 2

3）中間幾行的偶數列的下標獲取：前一元素的下標 ＋ （行數－第幾行）* 2

4）中間幾行的奇數列的下標獲取（除首元素）：前一元素下標 ＋ （第幾行 － 1） * 2

注：

    程序中行數由于是從零開始的的，所以程序中會有相差一的出入。

int
getIndex(int index, int cnt, int numRows, int flag)
{
    if ( flag == 0 )
    {
        return cnt;
    }
    else if ( cnt == 0 || cnt == numRows - 1 )
    {
        index = index + ( numRows - 1) * 2;
    }
    else if ( flag % 2 != 0 )
    {
        index = index + (numRows - 1 - cnt) * 2;
    }
    else if ( flag % 2 == 0 )
    {
        index = index + cnt * 2;
    }
    
    return index;
}

char* convert(char* s, int numRows) 
{
    if ( *s == '\0' || numRows == 1 )
    {
        return s;
    }
    
    int len = strlen(s);
    if ( len <= numRows )
    {
        return s;
    }
    
    int add = 0;
    char rest[len + 1];
    int cnt = 0;
    for ( cnt = 0; cnt < numRows; cnt++ )
    {
        int index = 0;
        int flag  = 0;
        index = getIndex(index, cnt, numRows, flag);
        while ( index < len )
        {
            rest[add] = *(s + index);
            add   += 1;
            flag  += 1;
            index = getIndex(index, cnt, numRows, flag);
        }
    }
    rest[len] = '\0';
    
    sprintf(s, "%s", rest);
    
    return s;
}

逐行讀取每個元素，存入rest結果集中。最后寫會s，防止出現局部數組返回。

關于“leetcode中如何解決ZigZag Conversion問題”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。