蜗牛慢慢爬 LeetCode 6. ZigZag Conversion [Difficulty: 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);

翻译

此题坑爹在于关于zigzag的形式没有说清楚然后在leetcode上负分较多

其实只要理解了zigzag的形式就好了

/*n=numRows

Δ=2n-2    1                           2n-1                         4n-3

Δ=        2                     2n-2  2n                    4n-4   4n-2

Δ=        3               2n-3        2n+1              4n-5       .

Δ=        .           .               .               .            .

Δ=        .       n+2                 .           3n               .

Δ=        n-1 n+1                     3n-3    3n-1                 5n-5

Δ=2n-2    n                           3n-2                         5n-4

*/

Hints

Related Topics: String

一开始我的想法是用二维数组在遍历的时候把字符存到对应的位置之后再join到一个字符串里面这样挺直观的但是python的话慢了一点

事实上我的代码有点硬推出每个字符的位置填上去的意思(囧) discuss中类似状态机改变index变化步长的方法显然更好

代码

Java

public String convert(String s, int nRows) {

    char[] c = s.toCharArray();

    int len = c.length;

    StringBuffer[] ss = new StringBuffer[nRows];

    for (int i = 0; i < ss.length; i++) ss[i] = new StringBuffer();

    int i = 0;

    while (i < len) {

        for (int idx = 0; idx < nRows && i < len; idx++)

            ss[idx].append(c[i++]);

        for (int idx = nRows-2; idx >= 1 && i < len; idx--)

            ss[idx].append(c[i++]);

    }

    for (int idx = 1; idx < ss.length; idx++)

        ss[0].append(ss[idx]);

    return ss[0].toString();

}

Python

class Solution(object):

    def convert(self, s, numRows):

        """

        :type s: str

        :type numRows: int

        :rtype: str

        """

        l = len(s)

        if l<=1 or numRows<=1:   return s

        k = numRows - 2

        n = l/(numRows+k)+1

        n = n*(k+1)

        zigzag = [['']*n for i in range(numRows)]

        for i in range(l):

            c = (2*numRows-2)*(i/(2*numRows-2))

            if (i-c)/numRows==0:

                zigzag[((i-c)%numRows)][(i/(2*numRows-2))*(k+1)] = s[i]

            else:

                zigzag[numRows-2-(i-c)%numRows][(i/(2*numRows-2))*(k+1)+((i-c)%numRows+1)] = s[i]

        ss =''

        for i in range(numRows):

            ss += ''.join(zigzag[i])

        return ss

#better solution

class Solution(object):

    def convert(self, s, numRows):

        if numRows==1or numRows>=len(s):

            return s

        L = ['']*numRows

        index, step = 0, 1

        for i in s:

            L[index] += i

            if index==0:

                step = 1

            elif index==numRows-1:

                step = -1

            index += step

        return ''.join(L)

巴特西

蜗牛慢慢爬 LeetCode 6. ZigZag Conversion [Difficulty: Medium]

题目

翻译

Hints

代码

Java

Python

最新文章

热门文章