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跟蹤當前處在哪一行阱当，按照這個模式把所有的字符填到對應的行上即可。
代碼
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
# 取出結果
res = ""
for row in rows:
res += row
return res
理解了上面的思路糜工，再看這個題的代碼就很自然弊添，也很簡單了。
時間復雜度：O(n)
空間復雜度：O(n)
新的思路
算法題捌木，除了掌握基本的算法寫法外油坝，不斷優(yōu)化算法的心理也很重要，不要滿足于當前的算法復雜度刨裆，精益求精澈圈。
自己想不到的就去看別人的思路，一定要有這種習慣帆啃。
TBD...
