题目：
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"
.
题目大意：
给定一个字符串，将字符串以N字形输出，返回以N字形输出的每一行构成的新字符串。
思路：
这道题是纯考找规律的题，只要将字符串以要求的形式在纸上写出来找出规律，然后用程序表达出来就行了。我找到的规律如下：
如上图：很容易可以发现，如果没有中间几个孤零零的节点（FGH等）则每一行排列的节点在原字符串中是等距的，都是2 * numRows - 2，中间孤零零的节点是在每次进行
2 * numRows - 2长度的偏移后再向前偏移(i - 1) * 2 个节点后的产物（PS：i为当前N字形的行，i != 1 && i != numsRows）。有了这两个规律我们就可以开开心心的些程序了（注意numRwos为1的情况和其他边界情况）。
代码：
class Solution {
public:
std::string convert(std::string s, int numRows) {
std::string result = "";
int tmp, off = numRows * 2 - 2; //固定偏移量(N字主干部分节点)
if (numRows >= s.size() || numRows == 1) {
return s;
}
for (int i = 1; i <= numRows; ++i) {
result += s[i - 1];
if (i == numRows){
tmp = 0; //特殊处理最后一行
} else{
tmp = (i - 1) * 2; //中间孤零零的节点
}
for (int j = 1; off * j + i - 1 - tmp < s.size(); ++j) {
if (tmp) {
result = result + s[off * j + i - 1 - tmp]; //N字主干部分
}
if (off * j + i - 1 < s.size()) {
result = result + s[off * j + i - 1]; //孤零零的中间节
}
}
}
return result;
}
};
这个程序的测试时间是26ms，去答案区看了看。。。有个16ms的答案，看了一眼，思路和我这个思考基本一致。
代码：
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
string ret;
int row = numRows-1, i, inter = numRows * 2 - 2, inner, size = s.size();
for (i = 0; i < size; i += inter) ret += s[i]; //第一行
//中间行
while (row > 1) {
inner = row * 2 - 2;
for (i = numRows - row + inner; i < size; i += inter) {
ret += s[i - inner];
ret += s[i];
}
row--;
if (i - inner < size) ret += s[i - inner];
}
for (i = numRows-1; i < size; i += inter) ret += s[i]; //最后一行
return ret;
}
};注：第二个程序原地址
https://leetcode.com/discuss/91383/my-c-code-with-clear-comment-16ms
转载于:https://www.cnblogs.com/jungzhang/p/5547323.html
