首页 > 代码库 > ZigZag Conversion

ZigZag Conversion

题目:

zigzag,就是锯齿状的数字顺序,其形式就是首尾行间断的比内部行少一个,就是下面的形式。

1     *     7                                       

2    6     8     12

3    5    9      11

4     *   10

更好看点就是 

1                      7

2               6     8              12

3       5             9       11

4                      10


找找规律,对于给定的行数r,总是r行 + r - 2 行在交替,将二者看为一体,总是 ( r 行,r - 2行)在不断的重复。

抛开中间的 r - 2行不说,1 - 7, 2 -8, 3 -9, 4- 10,相差的都是6,再继续画下去,就找到规律(其实很明显了),总是 2 * r - 2,减的这个 2 是因为 中间首尾行各少一个。

所以在处理的时候,我们可以将( r 行,r - 2行) 这个重复的部分视为大的单元,其中单元内部要额外的附加处理。

string convert(string s, int nRows) {

	string re;
	if(s.empty() || s.size() < nRows || nRows == 1)
		return s;
	const int circle = (nRows - 1) << 1;

	for (int i = 0; i < nRows; ++i)
	{
		/*
	row:0  1       7
	row:1  2    6  8  -----> i = 1, (4 - 1) - 1%3 = 2, 2*2=4, 2 + 4 = 6
	.	   3  5    9         i = 2, (4 - 1) - 2%3 = 1, 1*2=2, 3 + 2 = 5
	.	   4       10
	    由于是内部行,所以 (nRows - 1) - i % (nRows - 1) <==> (nRows - 1) - i
		                  
		*/
		int inner_steps = ((nRows - 1) - i) << 1;
		int index = i;
		while (index < s.size())
		{
			re.push_back(s[index]);
			//handle the inner rows.
			if(i != 0 && i != nRows - 1 && (index + inner_steps) < s.size())
			{
				re.push_back(s[index + inner_steps]);
			}
			index += circle;
		}
	}
	return re;
}