題目：
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”
我的答案:
版本一：

string convert(string s, int numRows) {if (numRows == 1)return s;int L = s.length();const char *p = s.c_str();vector<vector<char> > A;vector<char> a;int N = 0;while (N < L){if (N > L)break;for (int i = 0; i < numRows; i++){if (N < L){a.push_back(*(p + N));N++;}elsebreak;}A.push_back(a);a.clear();for (int i = numRows - 2; i > 0; i--){if (N < L){for (int j = 0; j < numRows; j++){if (N < L){if (j != i)a.push_back('\0');else{a.push_back(*(p + N));N++;}}elsebreak;}A.push_back(a);a.clear();}elsebreak;}}//對最后一列的數據進行完善,因為字符串長度是隨機的，所以最后一列可能在沒有裝滿之前，字符串已經被分配完畢，所以采用這種方式補全，以進行下面每行的鏈接int last_size = A[A.size() - 1].size();if (last_size != numRows){for (int i = 0; i < numRows - last_size; i++)A[A.size() - 1].push_back('\0');}//數據已經存好for (int i = 0; i < A.size(); i++){for (int j = 0; j < A[i].size(); j++)cout << A[i][j] << " ";cout << endl;}stringstream ss;for (int i = 0; i < numRows; i++){for (int j = 0; j < A.size(); j++){if (A[j][i] == '\0')continue;elsess << A[j][i];}}return ss.str(); }

思路解析：遍歷整個字符串，將其按照之字形的結構，按列存儲，顯然除了部分列的元素個數是numRows之外，其他列的元素個數都是1，為了后續字符重新排序的方便，將每列不含有字符串字符的地方用結束符代替，使得每列數據在存儲中占用相同的空間，在后續數據重新排序的時候，只需要循環遍歷所有的列并依次輸出各列的元素（遇到結束符的時候，不輸出該字符），在利用該方法的時候關鍵是保證一開始在遍歷存儲字符串的時候要保證每列都占用相同的空間，并且所有列中的非結束符字符的存放結構滿足之字形結構。所以如果最后在遍歷字符串結束后，要判斷最后一列的元素是否為numRows個，如不是需要利用結束符補全。整個算法的思想就是不用費力去觀察之字形結構的規律并建模，只需要按列存儲之后并循環遍歷輸出即可，比較好理解，但是運行時間較長。
版本二（進階版）：

string zigzag_convert(string s, int numRows) {if (numRows == 1)return s;if (numRows < 1)return "";int gap = 2 * numRows - 2;int val = 0;int L = s.length();string res = "";for (int i = 0; i < numRows; i++,val += 2){res += s[i];for (int j = i; j<L;){if ((gap - val) != 0){j += (gap - val);if (j < L)res += s[j];elsebreak;}if (val != 0){j += val;if (j < L)res += s[j];elsebreak;}}}return res; }

思路解析：該版本的思想是觀察之字形結構并進行建模。舉例說明：
假設輸入字符串為S，
S=”abcdefghijklmnopqrstuvwxyz”;
numRows=5;
以下是之字形中每行元素在字符串中的下標（為了方便表述，從數據存儲的角度出發，引入第0行）：
第0行：0 8 16 24
第1行：1 7 9 15 17 23 25
第2行：2 6 10 14 18 22
第3行：3 5 11 13 19 21
第4行：4 12 20
觀察以上下標，可以得到結論，除了第0行與最后一行，每相隔的兩個下標之間的距離都是：gap=2*numRows-2，每行的第一個元素的下標都與行號相同；第0行與最后一行的各元素相鄰下標的距離為gap；根據這個規律寫出以上代碼。顯然，利用這種方法不會消耗多余的空間，而且只需要遍歷一次字符串即可，算法高效。

總結

以上是生活随笔為你收集整理的leetcode_zigzag conversion的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。