LeetCode刷題筆記 06 ZigZag Conversion

不得不說，大家喜歡做題勝過看書。

學習群里不少人幾天前就問我這周會不會做題，好吧，今天就來滿足大家

今天要做的還是一道「簡單」難度的題目

這首題目雖然等級是「簡單」，題目本身還挺難理解的

鏈接

https://leetcode.com/problems/zigzag-conversion/

題目

大意就是：給定一個字元串，我們需要把它的字元按照Z字形排列，然後按行輸出（排幾行也是指定的）

是不是有點暈?

沒事，讓小馬哥來給你畫個圖

假設輸入是"PAYPALISHIRING"，要求排3行

那麼按Z字形排列之後是這樣的

P A H N A P L S I I G Y I R

其實說N字形排列更加合適

如果還沒有看明白的話，咱們用下標來表示

0 4 8 12 1 3 5 7 9 11 13 2 6 10

下一步是把排列後的結果按行輸出

「PAHNAPLSIIGYIR」

函數定義

leetcode給定的函數定義是這樣的：

class Solution { public: string convert(string s, int numRows) { } };

那麼convert("PAYPALISHIRING", 3)的返回值就是"PAHNAPLSIIGYIR"

看到這裡您應該停下來自己思考一下了。

解題思路

好了，看懂題目之後我們就來想一想這道題目怎麼解

重點還是在於尋找內在的規律。

我的方法是給定numRows幾個值，分別在紙上寫一寫，可能還沒等我們寫完就能找到規律了

比如讓numRows等於4，那麼Z字形排列後是

P L I A L I R N Y A S I G P H

仔細觀察，我們可以把它看成是有周期的

P | L | I A L | I R | N Y A | S I | G P | H |

怎麼樣，是不是有點思路了？

每個周期裡面，除了第1行和最後一行只有一個元素外，其他行都是有兩個元素

那麼每個周期裡面有多少個元素應該不難算吧，進而總共有多少個周期也是可以知道的了

我們可以把輸入的字元串按周期分段，把每小段的第一個元素連起來就是第一行，最後一個元素連起來就是最後一行，中間行要取首尾兩個元素。。。

但是，這個解法看上去有點複雜，讓我們再想想

我們還可以觀察到：

1. 在豎排上的元素，行逐漸增加，列不變
2. 非豎排的元素，行逐漸減少，列逐漸增加

是不是離寫出程序又近了一步？

再想一想，我們關心列有什麼用呢？只需要關心每一行有哪些元素就可以了，不是嗎？

有沒有一種呼之欲出的感覺？

再具體點，我們可以

1. 定義numRows個空的string
2. 遍歷整個輸入string，將字元加入對應行
3. 把每一行的string拼接起來，得到輸出

好了，正式開始擼代碼

class Solution { public: string convert(string s, int numRows) { vector<string> vecRowStrings(numRows); int iRow = 0; bool bIsAdd = true; for (auto c : s) { auto sRowString = vecRowStrings[iRow]; sRowString += c; if (0 == iRow) { bIsAdd = true; } if (numRows - 1 == iRow) { bIsAdd = false; } bIsAdd ? (++iRow) : (--iRow); } string sResult; for (auto sRow : vecRowStrings) { sResult += sRow; } return sResult; } };

「Run Code」，出錯了。。。

大家可以試下通過看代碼能不能找出這個錯誤

給出的信息又很少怎麼辦？ 這個時候就有必要打開visual studio建個工程跑一跑了

原來是auto sRowString = vecRowStrings[iRow];這裡忘記使用引用了，所以對sRowString的修改變沒有作用到vector中

修改之後再提交，還是有case跑不過，發現是numRows為1的情況

把1代入我們的程序走一遍，確實會出問題，iRow會出現負值的情況

而我們使用下標進行vector元素的訪問時並沒有進行下標判斷

其實對於行為1的情況，不存在z字形排列，直接將原始字元串返回就可以了

下面是修改後的程序

class Solution { public: string convert(string s, int numRows) { if( 1 == numRows ) { return s; } vector<string> vecRowStrings(numRows); int iRow = 0; bool bIsAdd = true; for (auto c : s) { auto &sRowString = vecRowStrings[iRow]; sRowString += c; if (0 == iRow) { bIsAdd = true; } if (numRows - 1 == iRow) { bIsAdd = false; } bIsAdd ? (++iRow) : (--iRow); } string sResult; for (auto sRow : vecRowStrings) { sResult += sRow; } return sResult; } };

「Run Code」，通過。提交。

19ms，擊敗42.16% 挺好的，不是嗎？

接下來就是想一想有沒有其他的解題方法，不管效率會不會有提高，都可以實現一下練練手。

也可以看看討論區其他人的分享

https://discuss.leetcode.com/category/14/zigzag-conversion

如果大家能優化上面的代碼，歡迎留言討論。也可以分享你的解題方法