6. Z 字形变换

https://leetcode-cn.com/problems/zigzag-conversion/

解法一:

按如下规律

/*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
*/

两列之间的差距为2n-2,若有斜线,两列之间差距设为step1和step2,有step1+step2=2n-2。

pos从i开始,每次+step1或+step2,交替进行

注意 numRows==1 && numRows==2的情况,没有斜线。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        length = len(s)
        result = ""
        for i in range(numRows):    #一行行输出
            step1 = 2*(numRows-1-i)
            step2 = 2*i
            pos = i    #起始位置
            if pos >= length:
                break
            result += s[pos]
            while True:
                pos += step1
                if pos >= length:    #直到pos越界
                    break
                if step1:    #step1不为0则输出
                    result += s[pos]
                pos += step2
                if pos >= length:
                    break
                if step2:
                    result += s[pos]
        return result

最后更新于