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是“之字形”的意思歧蕉，“之字形”是“鋸齒形”的意思灾部，可以腦補一下鋸齒形的畫面，實在想不出可以看下圖惯退，因為這個詞一定得弄清楚不然會影響你的理解赌髓，甚至會直接引導你到錯誤的方向。
大致意思：給定連續(xù)幾行的字符串以鋸齒形的形式排列顯示催跪，編寫代碼實現將按照鋸齒形順序排列的字符轉換成按照一行接一行的字符順序顯示锁蠕，就是將示例中的
鋸齒形順序的”PAYPALISHIRING“轉換成行讀順序的”PAHNAPLSIIGYIR“。
常規(guī)解法：以一個正常的思路來思考這個問題懊蒸，大多數人都會采用一個比較通俗易懂的方法來解決荣倾，就是將鋸齒形順序排列的字符依次存入一個二維數組中，然后按照正常遍歷的順序也就是題目中的一行接一行的順序遍歷顯示出來即可骑丸。
class Solution {
public:
string convert(string s, int numRows) {
char tb[1000][1000]={NULL};
int len=s.length();
if(numRows==1)
return "";
if(numRows==1)
return s;
int z=ceil((double)(len+numRows-2)/(2*(numRows-1)));
int col=0;
int flag=0;
for(int i=0;i<z && flag<=len;++i)
{
int row=0;
while(row<numRows && flag<=len)
{
tb[row++][col]=s[flag++];
}
--row;
for(int ct=0;ct<numRows-2 && flag<=len;++ct)
{
tb[--row][++col]=s[flag++];
}
++col;
}
string ot;
int lie=z+(numRows-2)*(z-1);
for(int i=0;i<numRows;++i)
{
for(int j=0;j<lie;++j)
{
if(tb[i][j]!=NULL)
ot.append(1,tb[i][j]);
}
}
return ot;
}
};
代碼解釋：首先開辟了一個很大的二維數組舌仍，因為題目沒要求字符串的長度限制，所以一般不會特別大通危。思路是：先算出以鋸齒形排列的主干列數(完整的列)铸豁，也就是最高的行列數，從二維數組的左上角開始：1.從上到下依次填滿字符菊碟；2.然后再沿對角線的方向依次填滿字符节芥；不斷重復這兩個操作直到將字符串中的字符按照鋸齒形填完為止。整個過程要注意行標和列標的變化逆害。最后遍歷輸出即可头镊。
其他解法：兩個完整的列增炭，如示例中的“PAY”和“ALI”之間會有1個字符，也就是（numRows-2）個字符拧晕，這樣整個字符串就劃分成了很多個numRows+numRows-2個字符串隙姿，當然尾部不一定滿足，這樣第一行和最后一行就可以以此為間隔依次取原字符串中字符生成厂捞，中間的行需要加上鋸齒形中間的字符输玷。到這里大家會發(fā)現其實就是下標計算的問題，注意不要越界就行靡馁。
class Solution {
public:
string convert(string s, int numRows) {
if(numRows <= 0) return "";
if(numRows == 1) return s;
string rst = "";
int sz = s.size();
for(int i=0; i<numRows; ++i) {
int idx = i;
while(idx < sz) {
rst += s[idx];
if(i!=0 && i!=numRows-1) {
idx += (numRows-1-i)*2;
if(idx >= sz) break;
else rst += s[idx];
idx += i*2;
}
else idx += (2*numRows-2);
}
}
return rst;
}
};
