前往
大廳
主題

LeetCode - 6. Zigzag Conversion 解題心得

Not In My Back Yard | 2023-05-03 12:00:16 | 巴幣 102 | 人氣 230

題目連結:


題目意譯:
字串 "PAYPALISHIRING" 以「之字形」的方式寫在給定的列數上,如下(你可能會想要將下列圖示以等寬字型來表示,以確保易讀性):
P   A   H   N
A P L S I I G
Y   I   R
接著一列一列讀得到:"PAHNAPLSIIGYIR"

撰寫一份程式碼,其將把給定的字串並在給定的列數下以上述形式轉換成另一字串:
string convert(string s, int numRows);

限制:
1 ≦ s.length ≦ 1000
s 由英文字母(小寫和大寫)、',' 和 '.' 所組成。
1 ≦ numRows ≦ 1000


範例測資:
範例 1:
輸入: s = "PAYPALISHIRING", numRows = 3
輸出: "PAHNAPLSIIGYIR"

範例 2:
輸入: s = "PAYPALISHIRING", numRows = 4
輸出: "PINALSIGYAHRPI"
解釋:
P     I    N
A   L S  I G
Y A   H R
P     I

範例 3:
輸入: s = "A", numRows = 1
輸出: "A"


解題思維:
首先,如果 numRows 恰好為 1,則答案就是 s 本身。

反之,我們可以看到實際上不需要真的形成「之字形」。例如範例 2 的
P     I    N
A   L S  I G
Y A   H R
P     I
可以去掉空白得到
PIN
ALSIG
YAHR
PI
然後從上至下串接起來依舊可以得到原本的答案。

因此我們只需要宣告出 numRows 個空字串。然後就直接從第一個字串開始依序把 s 的每一個字母放到第一個、第二個、 ……這些字串的尾端,然後碰到第 numRows 個字串就回頭放在第 numRows - 1 個、第 numRows - 2 個、……直到回到第一個字串。然後就重複這個步驟直到 s 中的字母都放完為止。

最後把每一個字串串接起來便可以得到所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作