Last Updated on 2021-01-01 by Clay
題目
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)
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:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I這個題目給定輸入一個字串以及行高 numRows，我們將其重新排序成 Z 字型，並再次按照一行行的順序重新回傳字串。
也就是將這一字串重組。
解題思路
以下這個方法是我自己的第一感，但看最終執行結果，很難說這是最好的方法，執行速度雖然較快，但記憶體使用率似乎是比較差的。
- 首先創造 numRows 個字串
- 依照字串順序放入不同行的字串中，若是已經放到最後一行，接著便倒著放順序回去
- 假設有 3 行，放的順序便是 1、2、3、2、1、2、3 ...... 依此類推
- 最終再將不同行的字串串接成同樣的字串並回傳
C++ 程式碼
class Solution { public: string convert(string s, int numRows) { if (numRows==1) return s; vector<string> v(numRows, ""); int carry = 1; int save_pos = 0; for (char w: s) { if (save_pos == 0) { carry = 1; } else if (save_pos == numRows-1) { carry = -1; } v[save_pos] += (w); save_pos += carry; } string results; for (int i=0; i<v.size(); i++) { for (int n: v[i]) { results += n; } } return results; } };
Python 程式碼
class Solution: def convert(self, s: str, numRows: int) -> str: if numRows == 1: return s results = ["" for _ in range(numRows)] carry = 1 save_pos = 0 for w in s: if save_pos == 0: carry = 1 elif save_pos == numRows-1: carry = -1 results[save_pos] += w save_pos += carry return ''.join(results)