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".
thinking:
(1)读懂题意,把字符串依照"Z"形又一次排列,再按行链接起来输出。
(2)没有解体思路,能够列举几个简单的样例寻找规律。
一: 2排的时候,1到n的排序
1 3 5 7 9 。
。。
2 4 6 8 10 。。。
二: 3排的时候。1到n的排序
1 5 9 。
。。
2 4 6 8 10 。。。
3 7 11 。。。
三: 4排的时候,1到n的排序
1 7 13 。
。。
2 6 8 12 14 。。。
3 5 9 11 15 。
。。
4 10 16 。。
。
这到规律没有?如果没有找到, 你能够继续写5排的情况。非常快你就能够找到规律。
这是一个解决这个问题问题的方法。
当我们遇到难缠的问题的时候,我们先考虑简单的情形,看看能不能找到规律。这个题目。我们通过写出来这些特殊情况,我们发现例如以下规律,这里我们如果我们分成m排:
1 第i排从i開始
2 第i排两个数的间隔是2(i-1),2(m-i)交替
code:
class Solution {
public:
string convert(string s, int nRows) {
int length = s.size(); if((nRows==1)||(nRows>=length))
return s;
string result;
for(int i=0;i<nRows;i++)
{
bool flag=true;
int j=i;
while(j<length)
{ result.push_back(s.at(j));
if((i==0)||(i==nRows-1))
j+=2*(nRows-1);
else
{
if(flag)
{
j+=2*(nRows-i-1);
flag=false;
}
else
{
j+=2*i;
flag=true;
} }//else
}//while
}//for
return result;
}//convert
};