Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
52 lines (47 sloc) 1.31 KB
problem:
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".
----------------------------------------------------------
solution:关键点是对zigzag pattern的理解,然后找出规律
nRows = 2
0 2 4 6 ...
1 3 5 7
nRows = 3
0 4 8 ...
1 3 5 7 9
2 6 10
nRows = 4
0 6 12 ...
1 5 7 11
2 4 8 10
3 9
//每个满zig包含的字符个数为zigSize = nRows + nRows - 2
//第一行和最后一行只有一个字符
//中间的每行有两个字符。第二个字符索引为zigSize - 2*ir, ir是行index
string convert(string s, int nRows)
{
if(s == "" || nRows <= 1)
return s;
string s_new = "";
int zigSize = nRows + nRows - 2;
for(int i = 0; i < nRows; i++)
for(int j = i; ; j+= zigSize)
{
if(j >= s.length())
break;
s_new.append(1, s[j]);
if(i > 0 && i < nRows - 1)
{
int t = j + zigSize - 2 * i;
if(t < s.length())
s_new.append(1, s[t]);
}
}
return s_new;
}