[LeetCode] 用 Table 來解 #6 ZigZag Conversion
LeetCode #6 官網的解答第一個其實就很好了解,所以似乎這題看起來沒必要寫文章?
但我就想用一些原創、網路上找不到的方法、又簡單的把他解掉。
題目與解法
例如他把一疊標記 ABCD... 的卡片擺成這樣:
你要從左到右,從上到下的順序把卡片重新排列輸出:
當然我第一個想到的就是用 table 的方式讓他把字串擺進我的 table 中,我再來從左到右、從上到下慢慢掃就結束啦。
最後再把 "*" 的字元刪掉就好了。
因為我們變成 table 所以我們需要知道 table 的寬度才能正確計算從 2D 變成 1D 的 index,我們其實可以把它變成一個一個 group 來算:
程式碼
所以 C++ 程式碼就會長這樣:
比較麻煩的是我要用 row 和 col 去追蹤他上上下下的位置,還有一開始要計算 columns 總共有幾個,看起來比 vector<string> 的要複雜多了。
不過我們可以再稍微想一下,我們一定要算出精準的 columns 數量嗎? 如果多加幾列(還是行)應該沒差吧:
反正多出來的 "*" 最後還是會被刪掉,所以我們可以粗略的計算一下就好,我們可以把 calcNumColumns 改一下,我們就不去計較最後一個 group 到底是一行還是兩行了:
結果當然會慢一點點,不過程式碼看起來就稍微變簡單了一點。
結果
前後兩個解法的結果分別是:
更棒的解法?
這個解法因為裡面有很多沒作用的 "*" 字元太佔空間了,我們有辦法不要用這些字元嗎?
有沒有什麼技巧可以忽略它?
下一篇我們就來介紹一個更棒的解法,而且最棒的是我們不用分析一堆奇怪的 index 計算。
GitHub
以上的 code 和投影片我都放在 GitHub 上了,有興趣的歡迎參考。
留言
發佈留言