題目描述
將一個給定字串根據給定的行數，以從上往下、從左到右進行 Z 字形排列，
比如輸入字串為 "LEETCODEISHIRING" 行數為 3 時，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的輸出需要從左往右逐行讀取，產生出一個新的字串，比如："LCIRETOESIIGEDHN"，
請你實作這個將字串進行指定行數變換的函式：
string convert(string s, int numRows);
示例 1:
輸入: s = "LEETCODEISHIRING", numRows = 3
輸出: "LCIRETOESIIGEDHN"
示例 2:
輸入: s = "LEETCODEISHIRING", numRows = 4
輸出: "LDREOEIIECIHNTSG"
解釋:
L D R
E O E I I
E C I H N
T S G
來源：力扣（LeetCode）
難度:中等
鏈接：https://leetcode-cn.com/problems/zigzag-conversion
題解
我的題解
我的思路：根據字串的長度和行數算出總共有多少列，然后創建一個二維字符陣列，依次遍歷字串將每個字符放在對應的位置上，最后遍歷二維字符陣列得出新字串，
下面講一下程序中遇到的問題吧！
問題一：計算多少列，由于字串長度和行數是不固定的，所以在計算多少列的時候比較麻煩（其實也沒有多麻煩，想通就行，一開始算錯了，后面各種下標越界，心態都炸了）
問題二：計算每個字符所在位置，假設二維字符陣列為strs[row][colume],從strs[0][0]開始放入第一個字符,以后
1.每次row遞增放入字符
2.當row達到最大時,每次row遞減的同時colume遞增放入字符
3.當row達到最小值0時,再重復1和2的操作,直到所有字符放入
官方題解
方法一：按行排序
思路
通過從左向右迭代字串，我們可以輕松地確定字符位于 Z 字形圖案中的哪一行，
演算法
我們可以使用 min(numRows,len(s)) 個串列來表示 Z 字形圖案中的非空行，
從左到右迭代 ss，將每個字符添加到合適的行，可以使用當前行和當前方向這兩個變數對合適的行進行跟蹤，
只有當我們向上移動到最上面的行或向下移動到最下面的行時，當前方向才會發生改變，
public String convert(String s, int numRows) {
if (numRows == 1) return s;
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++)
rows.add(new StringBuilder());
int curRow = 0;
boolean goingDown = false;
for (char c : s.toCharArray()) {
rows.get(curRow).append(c);
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
StringBuilder ret = new StringBuilder();
for (StringBuilder row : rows) ret.append(row);
return ret.toString();
}
復雜度:
時間復雜度:O(n)
空間復雜度:O(n)
方法二：按行訪問
思路
按照與逐行讀取 Z 字形圖案相同的順序訪問字串，
演算法
首先訪問 行 0 中的所有字符，接著訪問 行 1，然后 行 2，依此類推...
對于所有整數 k，
行 0 中的字符位于索引 k(2?numRows?2) 處;
行 numRows?1 中的字符位于索引 k(2?numRows?2)+numRows?1 處;
內部的 行 i 中的字符位于索引 k(2?numRows?2)+i 以及 (k+1)(2?numRows?2)?i 處;
public String convert(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder ret = new StringBuilder();
int n = s.length();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
ret.append(s.charAt(j + i));
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
ret.append(s.charAt(j + cycleLen - i));
}
}
return ret.toString();
}
復雜度:
時間復雜度:O(n)
空間復雜度:O(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139977.html
標籤：其他
上一篇：彩色紋理網格
下一篇：C語言遞回之求根到葉節點數字之和