每日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行）：

A E I
BDFHJ
C G K

然后按行打印：AEIBDFHJCGK

如果按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;
        }
        

};

发表于：leetcode

2016-04-06

# leetcode