- ZigZag Conversion
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".
思路:
比如有一個(gè)字符串 “0123456789ABCDEF”号坡,轉(zhuǎn)為zigzag
image.png
除了第一行和最后一行沒有形成之字形的數(shù)字外挚躯,其他的都有,不算中間的斜線部分合蔽,每行中相鄰兩個(gè)元素的index之差和行數(shù)是相關(guān)的怀骤,為size=2numRows-2费封,根據(jù)這個(gè)特點(diǎn),可以按順序找到所有黑色元素在字符串中的位置蒋伦,將他們按順序加到新字符串里弓摘。對于紅色元素的位置為j+size-2i,其中j是前一個(gè)黑色元素的列數(shù)痕届,i為當(dāng)前行數(shù)韧献。比如當(dāng)n=4中的那個(gè)紅色5,它的位置為1+6-2*1=5研叫。當(dāng)我們知道所有黑色元素和紅色元素位置的正確算法锤窑,就可以一次性的把他們按順序都加到新的字符串里邊。
var convert = function(s, numRows) {
if(numRows<=1) return s;
var res='';
var size=2*numRows-2;
for (var i = 0; i < numRows; i++) {
for (var j = i; j < s.length; j+=size) {
res+=s[j];
var tmp=j+size-2*i;
if(i!=0 && i!=numRows-1 && tmp<s.length) res+=s[tmp];
}
}
return res;
};