每日leetcode- ZigZag Conversion

2,701次阅读
没有评论

原题目:

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

 

题目的要求就是根据指定的行数进行相应的zigzag转换,其实这些都是符合一定的规律,具体的规律可以参考以下:

就是将一个字符串按ZigZag格式进行转换,并返回。例如字符串”ABCDEFGHIJK”

转换后(3行):

1
2
3
A E I
BDFHJ
C G K

然后按行打印:AEIBDFHJCGK

如果按4行转换:

1
2
3
4
A  G
B FH
CE IK
D  J

打印:AGBFHCEIKDJ

思路:

其实这道题像是找规律题。当转换为3行时,我们可以以4为单位(4=(3-1)*2.也就是等于(行数-1)*2),将字符串分割(以ABCDEFGHIJK为例):

ABCD     EFGH   IJK

那么经过转换后打印的第0行,其实是分割后每一个数组的第0个元素:A E I 。对应到原字符串中就是第0个、第4个、第8.

所以规律为 0,4,8,…4*n..

那么经过转换后打印的第2行(最后一行):打印后的每个元素为:C G K.其实是分割后的每个数组的第二个元素(下标从0可开始) 。对应到原始字符串就是:2 ,2+4,2+4*2,..2+4*n..

从上面可以看出,第一行和最后一行的规律为(设行数为i,从0开始):i+4*n(n=0,1,2…)

其他行:

还是上面的例子,第一行输出为:B D F H J.每一个元素都是分割后的数组中的第1个和第-1个元素。对应到原字符串中为:

1,4-1,4+1,4*2-1,4*2+1…

因此规律为(设i为行数):4*n+i,4*n-i。

具体实现的代码如下:

 

 

 

class Solution {
public:
    string convert(string s, int numRows) {
        
          if (numRows==1)
          {
              return s;
          }
            
            int slength=s.length();
      
            string result="";
            int gap=2*(numRows-1);
            for(int i=0;i<numRows;i++)
            {   
                int tmp=i;
                int Agap = 2*numRows - 2 - 2*i;
                 while(tmp<slength)
                 {
                     result+=s[tmp];
                     if(i!=0&&i!=numRows-1&&tmp+Agap<slength)
                     {
                         result+=s[tmp+Agap];
                         
                     }
                     tmp+=gap;
                 }
            }
            return result;
        }
        

};
admin
版权声明:本站原创文章,由admin2016-04-06发表,共计1304字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)