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

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

思路分析:

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

nRows = 2时,

1

4

2

3

nRows = 3时,

1

5

2

4

6

3

7

nRows = 4时,

1

7

2

6

8

3

5

9

4

10

nRows = 5时,

1

9

2

8

10

3

7

11

4

6

12

5

13

有没有发现什么规律?

每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;
    }
}

Python参考代码:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券