06. Z字形變換
難度中等610收藏分享切換為英文關注反饋
將一個給定字符串根據給定的行數这橙，以從上往下、從左到右進行 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
解法一：利用周期特性
根據z字排列的特性止毕，發(fā)現字符串成周期排列模蜡，周期為2 * numRows -2，
發(fā)現第n行的元素扁凛，為每個周期的第i個或者第（周期-i）個
public static String convert1(String s, int numRows) {
if(numRows == 1) return s;
int len = s.length();
int cycle = 2 * numRows -2;
StringBuilder sBuffer = new StringBuilder(len);
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < len; j++) {
if (j % cycle == i || j % cycle == (cycle - i)) {
sBuffer.append(s.charAt(j));
}
}
}
return sBuffer.toString();
}
時間復雜度：O(n)忍疾，其中 n == len（s）* numRows。每個索引被訪問 numRows 次谨朝。
空間復雜度：O(n)卤妒。創(chuàng)建了一個 len（s）大小的StringBuilder。
解法二：第一種解法的升級
去掉了跳過了許多沒必要的檢測字币，省去了大量的時間
算法：
每次一行一行訪問则披，對于第k個周期：
- 首先，先對邊界行洗出，做出判斷：
- 第0行字符位于 k * ( 2 * numRows - 2 ) 處
- 第numRows - 1 行中字符位于索引 k * （ 2 * numRows -2 ）+numRow - 1
- 其次士复，處理中間一般行：
- 第i行中的字符位于索引 k * （ 2 * numRows - 2 ）+ i 以及（ k + 1）*（2 * numRows - 2 ）- i 處
public static String convert2(String s, int numRows) {
if(numRows == 1) return s;
int len = s.length();
int cycle = 2 * numRows -2;
StringBuilder sBuilder = new StringBuilder(len);
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < len; j += cycle) {
sBuilder.append(s.charAt(j + i));
if (i != 0 && i != numRows - 1 && j + cycle - i < len)
sBuilder.append(s.charAt(j + cycle - i));
}
}
return sBuilder.toString();
}
解法三：按行排序
思路：
遍歷字符串，判斷確定字符屬于Z字形的哪一行翩活，然后放在對于的行阱洪。
算法：
我們可以遍歷一遍字符串便贵，可以使用當前行和當前方向兩個變量來對合適的行進行跟蹤。
只有當我們向上移動到最上面或者向下移動到最下面時冗荸，才會更改方向嫉沽。
public static String convert3(String s, int numRows) {
if(numRows == 1) return s;
List<StringBuilder> rows = new ArrayList<>();
//創(chuàng)建結果行集合（每行元素按照StringBuilder存放）
for(int i = 0; i<Math.min(numRows, s.length());i++) {
rows.add(new StringBuilder());
}
//當前行序號
int curRow = 0;
//direction 為方向，false 為向上俏竞，true為向下。
boolean direction = false;
for (char c : s.toCharArray()) {
rows.get(curRow).append(c);
if(curRow == 0 || curRow == numRows -1 ) {
direction = !direction;
}
//direction為true表示向下堂竟，false表示向上
curRow += direction ? 1 : -1;
}
StringBuffer result = new StringBuffer();
for (StringBuilder row : rows) {
result.append(row);
}
return result.toString();
}
測試類：
package com.company.project.hot100;
import java.util.List;
import java.util.ArrayList;
/*
* 6. Z 字形變換
將一個給定字符串根據給定的行數魂毁，以從上往下、從左到右進行 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
*/
public class Question06 {
/**
* 解法一：利用周期特性
* 根據z字排列的特性郎仆，發(fā)現字符串成周期排列只祠，周期為2 * numRows -2，
* 發(fā)現第n行的元素扰肌，為每個周期的第i個或者第（周期-i）個
* @param s
* @param numRows
* @return
*/
public static String convert1(String s, int numRows) {
if(numRows == 1) return s;
int len = s.length();
int cycle = 2 * numRows -2;
StringBuilder sBuilder = new StringBuilder(len);
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < len; j++) {
if (j % cycle == i || j % cycle == (cycle - i)) {
sBuilder.append(s.charAt(j));
}
}
}
return sBuilder.toString();
}
/**
* 解法二：第一種解法的升級
* 去掉了跳過了許多沒必要的檢測抛寝，省去了大量的時間
*
* 算法：
*
* @param s
* @param numRows
* @return
*/
public static String convert2(String s, int numRows) {
if(numRows == 1) return s;
int len = s.length();
int cycle = 2 * numRows -2;
StringBuilder sBuilder = new StringBuilder(len);
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < len; j += cycle) {
sBuilder.append(s.charAt(j + i));
if (i != 0 && i != numRows - 1 && j + cycle - i < len)
sBuilder.append(s.charAt(j + cycle - i));
}
}
return sBuilder.toString();
}
/**
* 解法三：按行分組
* 我們可以遍歷一遍字符串，可以使用當前行和當前方向兩個變量來對合適的行進行跟蹤曙旭。
* 只有當我們向上移動到最上面或者向下移動到最下面時盗舰，才會更改方向。
* @param s
* @param numRows
* @return
*/
public static String convert3(String s, int numRows) {
if(numRows == 1) return s;
List<StringBuilder> rows = new ArrayList<>();
//創(chuàng)建結果行集合（每行元素按照StringBuilder存放）
for(int i = 0; i<Math.min(numRows, s.length());i++) {
rows.add(new StringBuilder());
}
//當前行序號
int curRow = 0;
//direction 為方向桂躏，false 為向上钻趋，true為向下。
boolean direction = false;
for (char c : s.toCharArray()) {
rows.get(curRow).append(c);
if(curRow == 0 || curRow == numRows -1 ) {
direction = !direction;
}
//direction為true表示向下剂习，false表示向上
curRow += direction ? 1 : -1;
}
StringBuffer result = new StringBuffer();
for (StringBuilder row : rows) {
result.append(row);
}
return result.toString();
}
public static void main(String[] args) {
String s = "LEETCODEISHIRING";
int numRows = 4;
System.out.println(convert3(s, numRows));
}
}
