LeetCode之“字符串”：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".

　　为了解决这道题，我们再举一个例子：

　　如果我们把上图稍微转变一下：

　　也就是说，其实我们可以把中间斜线处的字母移到他们左边竖线字母下边，这样就更方便我们用二维矩阵来表示了。因此，我们可以将输入字符串分为等长的几个部分，不足的补充特别字符，如下图：

　　根据这种想法写出来的程序如下：

 1 class Solution {
 2 public:
 3     string convert(string s, int numRows) {
 4         int szS = s.size();
 5         if(szS == 0 || numRows < 2 || szS <= numRows)
 6             return s;
 7         
 8         int nRows = numRows + numRows - 2;
 9         int nCols = szS / nRows + 1;
10         vector<vector<char> > matrix(nRows, vector<char>(nCols, '#'));
11         int k = 0;
12         for(int j = 0; j < nCols; j++)
13             for(int i = 0; i < nRows; i++)
14             {
15                 if(k < szS)
16                 {
17                     matrix[i][j] = s[k];
18                     k++;
19                 }
20             }
21              
22         string retStr;
23         for(int i = 0; i < numRows; i++)
24             for(int j = 0; j < nCols; j++)
25                 if(i == 0 || i == numRows - 1)
26                 {
27                     if(matrix[i][j] != '#')
28                         retStr += matrix[i][j];
29                 }
30                 else
31                 {
32                     if(matrix[i][j] != '#')
33                         retStr += matrix[i][j];
34                     if(matrix[nRows - i][j] != '#')
35                         retStr += matrix[nRows - i][j];
36                 }
37         
38         return retStr;
39     }
40 };

View Code

　　虽然没超时，但它的运行时间达到了49ms，另外占用的内存也比较多。

　　其实，我们有必要再构造一个二维数组吗？是没必要的。修改之后的程序如下：

 1 class Solution {
 2 public:
 3     string convert(string s, int numRows) {
 4         int szS = s.size();
 5         if(szS == 0 || numRows < 2 || szS <= numRows)
 6             return s;
 7         
 8         int nRows = numRows + numRows - 2;
 9         int nCols = szS / nRows + 1;
10         string retStr;
11         for(int i = 0; i < numRows; i++)
12         {
13             for(int j = 0; j < nCols; j++)
14             {
15                 if((i == 0 || i == numRows - 1) && (i + j * nRows < szS))
16                     retStr += s[i + j * nRows];
17                 else
18                 {
19                     if(i + j * nRows < szS)
20                         retStr += s[i + j * nRows];
21                     if(nRows - i + j * nRows < szS)
22                         retStr += s[nRows - i + j * nRows];
23                 }
24             }
25         }
26         
27         return retStr;
28     }
29 };

　　修改后的程序运行时间仅有16ms，是原来的1/3。