leetcode 6 题解及思路

柔光的暖阳◎ 2023-01-12 04:27 52阅读 0赞

## 题目分析 ##

> [ 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。][_ s _ numRows _ Z]  
> 具体看原题，这里举一个比较特殊的例子(两行的之字形)  
> 输入：s = “ABCDEFG”, numRows = 2  
> 输出：“ACEGBDF”  
> 解释：  
> ACEG  
> BDF

## 思路记录 ##

>  *  利用二维数组模拟之字形
>  *  读取二维数组
>  *  重点主要是坐标的读写
>  *  效率很低，空间时间都有很大的优化空间
>  *  时间复杂度O(numRows*n)，空间复杂度O(numRows*n), n为字符串长度

## 代码及注释 ##

class Solution:
        def convert(self, s: str, numRows: int) -> str:
            len_s = len(s)
            con_z = [[None] * len_s for _ in range(numRows)]
            
            if numRows <= 1: #特殊情形，直接返回
                return s
    
            i = num = j = 0
            for ch in s:
                if not j % (numRows - 1):
                    con_z[i][j] = ch
    
                    if i < numRows - 1: 
                        i += 1
                    else:
                        i -= 1
                        j += 1
                else:
                    con_z[i][j] = ch
                    num += 1
                    j += 1
                    i -= 1
    
            ans = ''
            for i in range(numRows):
                for j in range(len_s):
                    if con_z[i][j]:
                        ans += con_z[i][j]
    
            return ans
    
    
    if __name__ == '__main__':
        s = Solution()
    
        s0, numRows0 = "PAYPALISHIRING", 3  # PAHNAPLSIIGYIR
        s1, numRows1 = "PAYPALISHIRING", 4  # PINALSIGYAHRPI
        s2, numRows2 = "PAYPALISHIRING", 1
        s3, numRows3 = "ABCDEFG", 2          # ACEGBDF
        s4, numRows4 = "PAYPALISHIRING", 3
        s5, numRows5 = "PAYPALISHIRING", 3
        for i in range(6):
            ss = eval('s%s' % i)
            numRows = eval('numRows%s' % i)
    
            print(s.convert(ss, numRows))

[_ s _ numRows _ Z]: https://leetcode-cn.com/problems/zigzag-conversion/