题目要求：
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".
为了解决这道题，我们再举一个例子：
如果我们把上图稍微转变一下：
也就是说，其实我们可以把中间斜线处的字母移到他们左边竖线字母下边，这样就更方便我们用二维矩阵来表示了。因此，我们可以将输入字符串分为等长的几个部分，不足的补充特别字符，如下图：
根据这种想法写出来的程序如下：
class Solution {
public:
string convert(string s, int numRows) {
int szS = s.size();
if(szS == || numRows < || szS <= numRows)
return s;
int nRows = numRows + numRows - ;
int nCols = szS / nRows + ;
vector<vector<char> > matrix(nRows, vector<char>(nCols, '#'));
int k = ;
for(int j = ; j < nCols; j++)
for(int i = ; i < nRows; i++)
{
if(k < szS)
{
matrix[i][j] = s[k];
k++;
}
}
string retStr;
for(int i = ; i < numRows; i++)
for(int j = ; j < nCols; j++)
if(i == || i == numRows - )
{
if(matrix[i][j] != '#')
retStr += matrix[i][j];
}
else
{
if(matrix[i][j] != '#')
retStr += matrix[i][j];
if(matrix[nRows - i][j] != '#')
retStr += matrix[nRows - i][j];
}
return retStr;
}
};
虽然没超时，但它的运行时间达到了49ms，另外占用的内存也比较多。
其实，我们有必要再构造一个二维数组吗？是没必要的。修改之后的程序如下：
class Solution {
public:
string convert(string s, int numRows) {
int szS = s.size();
if(szS == || numRows < || szS <= numRows)
return s;
int nRows = numRows + numRows - ;
int nCols = szS / nRows + ;
string retStr;
for(int i = ; i < numRows; i++)
{
for(int j = ; j < nCols; j++)
{
if((i == || i == numRows - ) && (i + j * nRows < szS))
retStr += s[i + j * nRows];
else
{
if(i + j * nRows < szS)
retStr += s[i + j * nRows];
if(nRows - i + j * nRows < szS)
retStr += s[nRows - i + j * nRows];
}
}
}
return retStr;
}
};
修改后的程序运行时间仅有16ms，是原来的1/3。