Time: 2019-08-01
語言：Python3
難度：中等

題目描述

將一個給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進行 Z 字形排列。

比如輸入字符串為"LEETCODEISHIRING" 行數(shù)為 3 時，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個新的字符串，比如："LCIRETOESIIGEDHN"。

請你實現(xiàn)這個將字符串進行指定行數(shù)變換的函數(shù)：

string convert(string s, int numRows);
示例 1:

輸入:s = "LEETCODEISHIRING", numRows = 3
輸出: "LCIRETOESIIGEDHN"
示例 2:

輸入: s = "LEETCODEISHIRING", numRows = 4
輸出: "LDREOEIIECIHNTSG"
解釋:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

思路

一種簡單但是耗費空間的做法是，用代碼模擬字符的填充過程。

我們首先定義一個數(shù)組，按行存儲元素。注意，如果字符串中的字符個數(shù)小于numRows，則一個豎行都走不完的，這在定義數(shù)組大小時候需要注意。

如何定義已知大小的數(shù)組？

答案是用生成式來寫。

rows = ['' for i in range(min(len(s), numRows))]

用一個變量goingDown來表示行走的方向，在遇到豎行的末尾時，掉頭向上。用curRow跟蹤當前處在哪一行，按照這個模式把所有的字符填到對應(yīng)的行上即可。

代碼

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        # 按行存儲數(shù)據(jù)的對象
        rows = ['' for i in range(min(len(s), numRows))]
        curRow = 0
        goingDown = False
        
        for c in s:
            rows[curRow] += c
            if curRow == 0 or curRow == numRows - 1 :
                goingDown = not goingDown
            if goingDown:
                curRow += 1
            else:
                curRow -= 1
                
        # 取出結(jié)果
        res = ""
        for row in rows:
            res += row
        return res

理解了上面的思路，再看這個題的代碼就很自然，也很簡單了。

時間復雜度：O(n)
空間復雜度：O(n)

新的思路

算法題，除了掌握基本的算法寫法外，不斷優(yōu)化算法的心理也很重要，不要滿足于當前的算法復雜度，精益求精。

自己想不到的就去看別人的思路，一定要有這種習慣。

TBD...