# LeetCode-6.Z字形变换(ZigZag Conversion)

10/18 17:20

## 6. Z 字形变换

``P   A   H   N``A P L S I I G``Y   I   R``

``string convert(string s, int numRows);``

``Input: s = "PAYPALISHIRING", numRows = 3``Output: "PAHNAPLSIIGYIR"``

``Input: s = "PAYPALISHIRING", numRows = 4``Output: "PINALSIGYAHRPI"``Explanation:``P     I    N``A   L S  I G``Y A   H R``P     I``

## 模拟法1

O(N)

``P     I    N  # P     # I    # N ``A   L S  I G  # A   L # S  I # G``Y A   H R     # Y A   # H R  #``P     I       # P     # I    #``
``class Solution:``    def convert(self, s: str, numRows: int) -> str:``        if numRows < 2 or numRows >= len(s):``            return s``        rows = ['' for i in range(numRows)]``        i = 0``        while (i < len(s)):``            n = 0``            while n < numRows and i < len(s):``                # 垂直向下｜``                rows[n] += s[i]``                i += 1``                n += 1``            n = numRows - 2``            while n > 0 and i < len(s):``                # 斜向上 /``                rows[n] += s[i]``                i += 1``                n -= 1``        return ''.join(rows)``

## 模拟法2

O(N)

``P   A   H   N  # 4  4  4``A P L S I I G  # 2  2  2  2  2  2``Y   I   R      # 4  4``
``P     I    N  # 6  6``A   L S  I G  # 4  2  4  2``Y A   H R     # 2  4  2``P     I       # 6``
``P       H     # 8``A     S I     # 6  2``Y   I   R     # 4  4``P L     I G   # 2  6  2``A       N     # 8``

``class Solution:``    def convert(self, s: str, numRows: int) -> str:``        if numRows < 2 or numRows >= len(s):``            return s``        base = (numRows - 1) * 2``        res = ''``        for i in range(numRows):``            step = i``            last = i * 2``            while(step < len(s)):``                res += s[step]``                if base - last > 0:``                    step += base - last``                    last = base - last``                else:``                    step += base``                    last = base``        return res``

--End--

0
0 收藏

0 评论
0 收藏
0