6. N 字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
例子
示例 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"
提示：
1 <= s.length <= 1000
s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成
1 <= numRows <= 1000
V1-简单思路
思路
将其看做一个二维数组。
什么是 Z 字型？
ABCDEFGHI
三个：
1 2 3 4 5
A E I
B D F H J
C G K
四个：
1 2 3 4 5
A G
B F H
C E I K
D J
java 实现
public String convertBasic(String s, int numRows) {
if(s.length() <= 1 || numRows <= 1) {
return s;
}
// 这里的多少列是个技术活，需要思考一下。
final int length = s.length();
char[][] zChars = new char[numRows][length];
char[] chars = s.toCharArray();
int rowIndex = 0;
int colIndex = 0;
boolean isDown = true;
// 第一个位置
zChars[rowIndex][colIndex] = chars[0];
for(int i = 1; i < length; i++) {
char c = s.charAt(i);
// 第一行时，从上到下
if(rowIndex == 0) {
isDown = true;
} else if(rowIndex == numRows-1) {
isDown = false;
}
// 处于向下的过程
if(isDown) {
rowIndex++;
} else {
// 处于向上的过程
// 最后一行时，从下到上，从左到右
colIndex++;
rowIndex--;
}
zChars[rowIndex][colIndex] = c;
}
// 空元素 '\0'
// 从左到右，从上到下遍历。
StringBuilder stringBuilder = new StringBuilder(length);
for(int i = 0; i < numRows; i++) {
for(int j = 0; j < length; j++) {
char currentChar = zChars[i][j];
if(currentChar != '\0') {
stringBuilder.append(currentChar);
}
}
}
return stringBuilder.toString();
}
效果
Runtime: 49 ms, faster than 9.25% of Java online submissions for ZigZag Conversion.
Memory Usage: 41.7 MB, less than 19.65% of Java online submissions for ZigZag Conversion.
性能一般，怎么优化呢？
列的改进
我们上面实现列的时候
// 这里的多少列是个技术活，需要思考一下。
final int length = s.length();
char[][] zChars = new char[numRows][length];
实际上没必要和 s 长度一样，因为要 Z 字形，可以调整为：
// 这里的多少列是个技术活，需要思考一下。
final int numCols = (length+1) >> 1;
char[][] zChars = new char[numRows][numCols];
不过这个优化效果一般。
V2-拼接优化
思路
拼接的时候其实在同一行的可以直接添加，没必要 O(N^2) 次遍历。
这就涉及到如何在插入的时候完成拼接。
优化点：数组替代LIST，append String 替代 buffer
java 实现
public String convert(String s, int numRows) {
//fast-return
final int length = s.length();
if(s.length() <= 1 || numRows <= 1 || numRows >= length) {
return s;
}
// 这里使用 buffer 替代。
StringBuilder[] stringBuilderList = new StringBuilder[numRows];
for(int i = 0; i < numRows; i++) {
StringBuilder builder = new StringBuilder(length);
stringBuilderList[i] =builder;
}
int rowIndex = 0;
boolean isDown = true;
// 第一个位置
stringBuilderList[0].append(s.charAt(0));
for(int i = 1; i < length; i++) {
char c = s.charAt(i);
// 第一行时，从上到下
if(rowIndex == 0) {
isDown = true;
} else if(rowIndex == numRows-1) {
isDown = false;
}
// 处于向下的过程
if(isDown) {
rowIndex++;
} else {
// 处于向上的过程
// 最后一行时，从下到上，从左到右
rowIndex--;
}
// 只需要关心属于对应的行即可
// 行在变化，但是列肯定是在增长的。
stringBuilderList[rowIndex].append(c);
}
// 按照行拼接
StringBuilder stringBuilder = new StringBuilder(length);
for(StringBuilder part : stringBuilderList) {
// 这里直接拼接字符串其实更快。
stringBuilder.append(part.toString());
}
return stringBuilder.toString();
}
效果
Runtime: 9 ms, faster than 43.72% of Java online submissions for ZigZag Conversion.
Memory Usage: 40.5 MB, less than 24.44% of Java online submissions for ZigZag Conversion.
V3-实现策略优化
思路
Visit all characters in row 0 first, then row 1, then row 2, and so on...
For all whole numbers kk,
Characters in row 0 are located at indexes k(2⋅numRows−2)
Characters in row numRows−1 are located at indexes k(2⋅numRows−2)+numRows−1
Characters in inner row i are located at indexes k(2⋅numRows−2)+i and (k+1)(2⋅numRows−2)−i.
这种一般比较难想到，相当于找到每一个规律。
java 实现
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
int n = s.length();
StringBuilder ret = new StringBuilder(n);
// 每一行的循环长度（这是一个规律） k(2⋅numRows−2)
int cycleLen = (numRows << 1) - 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();
}
当然，我们也可以把 StringBuilder 改为 char[]，不过性能差别不大。
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
int n = s.length();
char[] chars = new char[n];
int cycleLen = (numRows << 1) - 2;
int charIndex = 0;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
chars[charIndex++] = s.charAt(j + i);
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n) {
chars[charIndex++] = s.charAt(j + cycleLen - i);
}
}
}
return new String(chars);
}
效果
Runtime: 2 ms, faster than 99.85% of Java online submissions for ZigZag Conversion.
Memory Usage: 39.1 MB, less than 99.38% of Java online submissions for ZigZag Conversion.
小结
这一题的第二种算法并不算难理解，第 3 种的话，就需要对 Z 字形元素排列有很强的的规律认识。
本质上而言，已经变成了一个数学问题。
开源地址
为了便于大家学习，所有实现均已开源。欢迎 fork + star~
参考资料
https://leetcode.cn/problems/zigzag-conversion/
