Leetcode: ZigZag Conversion

最近在改论文，不喜欢写论文，但是为了毕业也没有办法！尽自己最大的努力做到最好吧！

这道题目做完貌似所有的Easy级别的题目就做完了，开始Medium的题目！加油吧！

题目：

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

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

思路分析：

我们先来探索N字型排列以后下标的规律(为了方便规律探索，我们这里下标从1开始，行数从1开始，程序中从0开始)：

nRows = 2时，

nRows = 3时，

nRows = 4时，

nRows = 5时，

有没有发现什么规律?

每i行的第一个下标是i

没一个N型中间都会包含一个数（第一行和最后一行除外），我们可以看做是第一个数+一个间距，得到第二个数；第二个数+一个间距，得到第三个数。第一行和最后一行也符合这个规律，只不过可以看做两个间距中的一个间距是0.

下面看看这两个间距的规律：

我总结出的是：

第一个间距是2 * （nRows - i），

第二个间距是2 * （i- 1）

看看是不是？

拿nRows=5看：

第一行1+2*(5-1)=9

第二行2+2*（5-2）=8，8+2*（2-1）=10，

第三行3+2*（5-3）=7，7+2*（3-1）=11，

第四行4+2*（5-4）=6，6+2*（4-1）=12

最后一行5+2*（5-1）=13

OK，分析出了这个规律，下面开始写程序。

C++参考代码：

class Solution
{
public:
    string convert(string s, int nRows)
    {
    	int length = s.length();
    	if (length <= 1 || nRows <= 1 || nRows >= length) return s;
    	string result = "";
    	//current记录当前元素下标，next记录当前元素到下一个元素下标的间距，nnext记录current到下下一个元素下标的间距
    	int current, next, nnext;
    	//一行一行的循环计算
    	for (int i = 0; i < nRows; i++)
    	{
    		result += s[i];//第i列的第一个元素
    		current = i;//记录下标
    		while (true)
    		{
    			next = 2 * (nRows - i - 1);//计算到下一个元素下标之间的距离2*（nRow-1）
    			nnext = 2 * i;//计算到下下一个元素下标之间的额距离2*(i-1)
    			
    			if (next != 0)
    			{
    				current += next;
    				if (current < length) result += s[current];
    				else break;
    			}
    			
    			if (nnext != 0)
    			{
    				current += nnext;
    				if (current < length) result += s[current];
    				else break;
    			}
    		}
    	}
    	return result;
    }
};

C#参考代码：

public class Solution
{
    public string Convert(String s, int nRows)
    {
        if (s.Length <= 1 || nRows <= 1 || s.Length <= nRows) return s;
        String result = String.Empty;
        int current, next, nnext;
        for (int i = 0; i < nRows; i++)
        {
            current = i;
            result += s[current ];
            while (true)
            {
                next = 2 * (nRows - i - 1);
                nnext = 2 * i;
                if (next != 0)
                {
                    current += next;
                    if (current < s.Length) result += s[current];
                    else break;
                }
                if (nnext != 0)
                {
                    current += nnext;
                    if (current < s.Length) result += s[current];
                    else break;
                }
            }
        }
        return result;
    }
}

class Solution:
    # @return a string
    def convert(self, s, nRows):
        length = len(s)
        if length <= 1 or nRows <= 1 or nRows >= length:
            return s
        result = ""
        for i in range(nRows):
            current = i
            result = result + s[current]
            while True:
                next = 2 * (nRows - i -1)
                nnext = 2 * i
                if next > 0:
                    current = current + next
                    if current < length:
                        result =  result + s[current]
                    else:
                        break
                if nnext > 0:
                    current = current + nnext
                    if current < length:
                        result = result + s[current]
                    else:
                        break
        return result

Leetcode: ZigZag Conversion

原文：http://blog.csdn.net/theonegis/article/details/44594729