LeetCode 6 蛇形矩陣，一道簡單的模擬題
- 2020 年 3 月 5 日
- 筆記
點擊上方藍字，和我一起學技術。
題意
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) https://leetcode.com/problems/zigzag-conversion/
翻譯
給定一個字符串，將它變成蛇形輸出。這個蛇形的概念比較抽象，我們需要結合樣例才能理解。
樣例
P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows); Example 1: Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR" Example 2: Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I
分析
這題的題意有點鬼畜，意思是說將給定的字符串先按照蛇形排列好，然後再按行依次讀入，最後輸出新的字符串。
雖然LeetCode上給這題的難度是Medium，但實際上它還是比較簡單的。和上一題的曼切斯特算法比起來，算得上是很簡單的了。LeetCode 5 迅速判斷迴文串的曼切斯特算法
這題會告訴我們字符串以及蛇形扭曲的行數，將字符串排成蛇形。這種沒有任何算法或者數據結構，僅僅是實現題意的問題稱為模擬題。顯然今天的這一題就是一道模擬題。模擬題唯一的難度就是編碼，實現一些比較複雜的功能，考驗的其實是工程能力。
這個蛇形的排列也很簡單，因為我們只要輸出最後的按行連接的結果。所以我們完全可以忽略列的位置信息，只用關注擺放的行就好了。因為行數是有限的，對於每一行，我們可以用一個字符串記錄當前行目前為止擺放的字符串，最後按照行的順序將所有行的結果連接到一起就好了。通過觀察，我們很容易發現，擺放的行是有周期規律的。一個周期是2 * rowJum – 2，從0先遞增到rowNum – 1，再遞減到1。
發現規律之後，再寫出code就不難了。
def convert(text, numRows): # 記錄每一行結果的dict lines = {} if numRows == 0: return text for i in range(len(text)): # 計算應該放在哪一行 idx = i % (2 * numRows - 2) # 判斷是在遞增區間還是遞減區間 if idx >= numRows: idx = 2 * numRows - 2 - idx line = lines.get(idx, "") lines[numRows] = line + text[i] result = "" # 拼接答案 for i in range(numRows): result += lines[i] return result
上面的代碼很簡單，但是藏着一個可以優化的地方。
在於dict的使用，dict的查詢需要開銷。其實我們可以替換成數組，因為我們已經確定行數了，所以數組的長度是固定的。如此優化之後，時間效率會更高一點。但是差別不會很大，代碼就不放了，我想大家應該都能想明白。
今天的文章就到這裡，如果覺得有所收穫，請點個在看或者轉發吧。
