LeetCode ZigZag Conversion 打印之字形字符图案 带打印程序

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".

按照它题目给出来的例子，不熟悉的话，还真不知道他想我们干嘛，所以还是看看图样就清楚了，如下面的运行打印图：

8行的时候

5行的时候

10行的时候

这就清楚了，利用输入字符打印一个倒立之字形的图样。

关键是要会如何计算各个字符的位置，这就需要数学知识了，根据特殊推导出公式来。

主要是3个公式：

1 之字形行数为nRows,那么每次重复样出现前的间隔字符为zigSpan= nRows*2-2;

2 第一行和最尾一行都是存放一个字符的，所以存储的字符为间隔为zigSpan的字符

3 中间行是需要额外存储多一个字符的，存储的字符位置是： zigSpan + j - 2*i（其中i为行数，j为该行第几个字符了）

如下面程序：

class Solution {
public:
	string convert(string s, int nRows)
	{
		if(nRows <= 1 || s.length() < 3 || s.length() <= nRows) return s;
		string s2;
		int zigSpan = nRows*2 - 2;
		for (int i = 0; i < nRows; i++)
		{
			for (int j = i; j < s.length(); j+=zigSpan)
			{
				s2.push_back(s[j]);
				//注意：推导出zigSpan+j-2i的数学公式，一点都不能错
				if (i != 0 && i != nRows-1 && zigSpan+j-2*i<s.length())
				{
					s2.push_back(s[zigSpan+j-2*i]);
				}
			}
		}
		return s2;
	}
};

下面是打印测试程序，运行结果如前面看到的图样：

void printZigzag(const string &s, int nRows)
{
	if(s.empty() || nRows < 1) return;
	if (nRows == 1)
	{
		cout<<s<<endl;
		return;
	}

	int zigSpan = nRows*2 - 2;
	int zig = nRows - 2;
	for (int i = 0; i < nRows; i++)
	{
		for (int j = i; j < s.length(); j+=zigSpan)
		{
			cout<<s[j];
			//注意：推导出zigSpan+j-2i的数学公式，一点都不能错
			if (i != 0 && i != nRows-1 && zigSpan+j-2*i<s.length())
			{
				for (int r1 = 0; r1 < zig-i; r1++)
				{
					cout<<" ";
				}
				cout<<s[zigSpan+j-2*i];
				for (int r2= 0; r2 < i-1; r2++)
				{
					cout<<" ";
				}
			}
			else
			{
				for (int r = 0; r < zig; r++)
				{
					cout<<" ";
				}
			}
		}
		cout<<endl;
	}
}


int main()
{
	string str1 = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";
	Solution solu;
	int nRows = 5;
	//string str2 = solu.convert(str1, nRows);
	//cout<<str2<<endl;

	printZigzag(str1, nRows);

	system("pause");
	return 0;
}

2014-1-24 update
解决此类题：画图，根据图，仔细观察，然后按例子计算，最后得出公式

	string convert(string s, int nRows)
	{
		//测试少了这句，居然是 Memory Limit Exceeded 错误
		//主要是不能没有nRows===1这句判断，Leetcode喜欢这么设计，没办法。
		//不用额外判断应该本程序也是可行的。
		if(nRows <= 1 || s.length() < 3 || s.length() <= nRows) return s;

		string rs;
		int span = nRows*2-2;
		
		for (int i = 0; i < nRows && i < s.length(); i++)
		{
			rs.push_back(s[i]);
			int j = i+span;
			for (; j < s.length(); j+=span)
			{
				if (i != 0 && i != nRows-1) rs.push_back(s[j-i*2]);
				rs.push_back(s[j]);
			}
			//注意这句的判断条件，不能少
			if (i != 0 && i != nRows-1 && j-i*2<s.length()) rs.push_back(s[j-i*2]);
		}

		return rs;
	}