189 8069 5689

leetcode中如何解决ZigZagConversion问题-创新互联

这篇文章将为大家详细讲解有关leetcode中如何解决ZigZag Conversion问题,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

发展壮大离不开广大客户长期以来的信赖与支持,我们将始终秉承“诚信为本、服务至上”的服务理念,坚持“二合一”的优良服务模式,真诚服务每家企业,认真做好每个细节,不断完善自我,成就企业,实现共赢。行业涉及成都玻璃钢雕塑等,在网站建设公司网络营销推广、WAP手机网站、VI设计、软件开发等项目上具有丰富的设计经验。

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问题”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


名称栏目:leetcode中如何解决ZigZagConversion问题-创新互联
文章分享:http://cdxtjz.cn/article/eehjj.html

其他资讯