原题目:
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"
.
题目的要求就是根据指定的行数进行相应的 zigzag 转换,其实这些都是符合一定的规律,具体的规律可以参考以下:
就是将一个字符串按 ZigZag 格式进行转换,并返回。例如字符串”ABCDEFGHIJK”
转换后(3 行):
1
2
3
|
A E I BDFHJ C G K |
然后按行打印:AEIBDFHJCGK
如果按 4 行转换:
1
2
3
4
|
A G B FH CE IK D J |
打印:AGBFHCEIKDJ
思路:
其实这道题像是找规律题。当转换为 3 行时,我们可以以 4 为单位(4=(3-1)*2.也就是等于(行数-1)*2),将字符串分割(以 ABCDEFGHIJK 为例):
ABCD EFGH IJK
那么经过转换后打印的第 0 行,其实是分割后每一个数组的第 0 个元素:A E I 。对应到原字符串中就是第 0 个、第 4 个、第 8.
所以规律为 0,4,8,…4*n..
那么经过转换后打印的第 2 行(最后一行):打印后的每个元素为:C G K.其实是分割后的每个数组的第二个元素(下标从 0 可开始) 。对应到原始字符串就是:2 ,2+4,2+4*2,..2+4*n..
从上面可以看出,第一行和最后一行的规律为(设行数为 i,从 0 开始):i+4*n(n=0,1,2…)
其他行:
还是上面的例子,第一行输出为:B D F H J.每一个元素都是分割后的数组中的第 1 个和第-1 个元素。对应到原字符串中为:
1,4-1,4+1,4*2-1,4*2+1…
因此规律为(设 i 为行数):4*n+i,4*n-i。
具体实现的代码如下:
class Solution { public: string convert(string s, int numRows) { if (numRows==1) { return s; } int slength=s.length(); string result=""; int gap=2*(numRows-1); for(int i=0;i<numRows;i++) { int tmp=i; int Agap = 2*numRows - 2 - 2*i; while(tmp<slength) { result+=s[tmp]; if(i!=0&&i!=numRows-1&&tmp+Agap<slength) { result+=s[tmp+Agap]; } tmp+=gap; } } return result; } };