難度: Medium
類型: String
==========================
前情題要:
將輸入的字串 s, 用深度numRows的 Zigzag 下去排列, 然後從第一列所有的 chars, 接著第二列, ...., 直到最後一列的 chars讀出來放到另一個字串, 並回傳這個字串。
==========================
思考方式:
1-1. 先建立一個 array, 每個index對應的值, 就是代表這個位置在第幾列。一開始是逐漸遞增列數, 到了最大的 numRows 後, 下面就逐漸遞減列數, 直到排到第一列, 之後再遞增, 一直循環。
1-2. 然後就每一列分別跑一輪字串s, 把第一列填完, 填第二列的, .... 直到填完最後一列的輸出字串。
1-3. 這方法簡單而暴力, 但是費時。所以後來又改寫第二種方法
2-1. 藉由觀察發現, 第一列和最後一列, 在填進第一個 char 後, 都會間隔 (numRows-1)*2) 的 char 又填回同一列。
2-2. 藉由觀察發現, 第 i 列, 會在填進第一個 char 後, 先間隔 (numRows-i)*2 個 char, 回到同一列, 然後再間隔 (i-1)*2 個 char, 回到同一列, 然後不斷兩種間隔循環。
2-3. 這方法必須觀察出規則才好寫, 然後要先判斷每個 index 是否超出輸入string 的長度再填入。
==========================
複雜度思考:
方法1:
Time: O (s_size*numRow+s_size)
Memory: O (s_size)
方法2:
Time: O (s_size)
Memory: O (s_size)
==========================
結果:
方法1:
Runtime: 10 ms, Beats: 35.03%
Memory: 11.80 MB, Beats: 77.02%
方法2:
Runtime: 0 ms, Beats: 100%
Memory: 10.79 MB, Beats: 97.02%
