• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

每日leetcode- ZigZag Conversion

leetcode admin 4年前 (2016-04-05) 2369次浏览 0个评论 扫描二维码

原题目:

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;
        }
        

};

Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明每日 leetcode- ZigZag Conversion
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!