一.题目

ZigZag Conversion

Total Accepted: 31399 Total
Submissions: 140315My Submissions

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

Show Tags

Have you met this question in a real interview?

Yes

No

Discuss

二.解题技巧

    这道题是就是原来的字符串的元素与锯齿化后的字符串的元素之间的关系，我们能够举个样例来说明，如果原来的字符串的每个字符的下标为0，1，2，3。…, 12分别进行行数为3。4，5行的锯齿化后，得到的锯齿化形状例如以下：

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc2hlbmdfYWk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">

    定义将原来的字符串依照nRows行进行锯齿化，定义 Step= 2 * nRows - 2; 从上面的样例能够看出，对于第i行。有以下两种情况：

1.对于第0行和第(nRows - 1)行，每一行的元素为i, i+Step, i+2*Step,…；

2.对于其它的行来说，每一行的元素为i, Step - i, i + Step, 2*Step - i,…。

得到这些映射关系之后，将上面得到锯齿化矩阵进行按行展开，放入到新的字符串中就得到满足要求的新字符串了。

三.实现代码

class Solution {
public:
string convert(string s, int nRows)
{
const int Size = s.size();
if ((Size <= nRows) || (nRows == 1))
{
return s;
}
const int Step = 2 * nRows - 2;
string Result;
for (int RowIndex = 0; RowIndex < nRows; RowIndex++)
{
int Index = RowIndex;
if ((RowIndex == 0) || (RowIndex == (nRows - 1)))
{
while (Index < Size)
{
Result.push_back(s[Index]);
Index = Index + Step;
}
continue;
}
int SecondIndex = Step - Index;
while ((Index < Size) || (SecondIndex < Size))
{
if (Index < Size)
{
Result.push_back(s[Index]);
Index = Index + Step;
}
if (SecondIndex < Size)
{
Result.push_back(s[SecondIndex]);
SecondIndex = SecondIndex + Step;
}
}
}
return Result;
}
};

四.体会

    这道题主要是寻找原来是字符串的元素坐标与锯齿化后的字符串的坐标关系，假设将原始字符串的元素坐标看作是一组已经排好序的数组的话，我们要做的就是怎样将这个数组依照一定规律进行乱序。主要是通过几个样例来推出通用的映射关系，然后依据这些映射关系进行编程就可以。绘图对于解决算法题目还是十分有效的。

版权全部，欢迎转载，转载请注明出处，谢谢