1.题目详情
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)
字符串"PAYPALISHIRING"要像下面一样以指定行数的锯齿状写出
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
然后逐行读取，得到字符串"PAHNAPLSIIGYIR"
写出代码，使得输入一个字符串后，像上面一样转换后将字符串输出。
Example 1:
Example 2:
然后完善下面代码：
class Solution {
public:
string convert(string s, int numRows) {
}
};
2.解题方法
以"PAYPALISHIRING"为例，转换为有4行的锯齿状的字符串，则从下图来看：
这些每个垂直向下铺开的"柱子"就是关键点，如第一个"柱子": P、A、Y、P，第二个"柱子": I、S、H、I，第三个"柱子": N、G。
可以看到第x个柱子的第一个字符到最后一个字符在原来字符串中的位置是(x-1)(2n-2) ~ (x-1)(2n-2)+n-1，其中n是行数。如第二个柱子的字符序列的位置就是(2-1)×(2×4-2) ~ (2-1)×(2×4-2)+4-1，即6到9。
遍历每个"柱子"，从这些字符出发，如第二个"柱子"的’S’，与它同一行的’L’在原来字符串中的位置是’S’的减去2，而这个2恰好是指遍历到了这个柱子的第二个字符’S’；同样，'A’也是第二个"柱子"的’G’的位置减去3的。即每个柱子前后的字符与柱子是有一定关系的。
所以代码如下：
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1)
return s;
int num = numRows * 2 - 2;
int limit = numRows - 1;
int size = s.size();
int trueLimit = size + limit - 1;
string result;
for (int i = 0; i < size; i = i + num)
result += s[i];
for (int i = 1; i < limit; i = i + 1) {
for (int j = 0; j < trueLimit; j = j + num) {
int left = j - i;
int right = j + i;
if (left >= 0 && left < size)
result += s[left];
if (right < size)
result += s[right];
}
}
for (int i = limit; i < size; i = i + num)
result += s[i];
return result;
}
};
运行时间为16ms。