将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
class Solution {
public String convert(String s, int numRows) {
return m2(s, numRows);
}
// 我的思路，失败, 只通过部分用例
public static String m1(String s, int numRows) {
int n = s.length();
int r = numRows;
if(s == null || r == 1 || r >=n){
return s;
}
StringBuffer sb = new StringBuffer();
// 基准点个数
int len = s.length() / numRows;
int[] index = new int[len];
// 首行间隔，及时第一行的间隔， 首行就是一个周期
// 貌似我这个也是周期
int d = 2 * numRows - 2;
Set<Integer> set = new HashSet<>();
// 基准点
for (int i = 0; i < len; i++) {
index[i] = i * d;
}
// 遍历每一行的基准点
for (int i = 0; i <= numRows; i++) {
for(int j = 0; j < len; j++) {
int k = index[j] - i;
if (k >= 0 && k < s.length() && !set.contains(k)) {
sb.append(s.charAt(k));
set.add(k);
}
int g = index[j] + i;
if (g >= 0 && g < s.length() && !set.contains(g)) {
sb.append(s.charAt(g));
set.add(g);
}
}
}
return sb.toString();
}
// 方法二 利用二维矩阵模拟：
public static String m2(String s , int numRows) {
int n = s.length();
int r = numRows;
if (r == 1 || r >= n){
return s;
}
// 周期
int t = r + r - 2;
// 每个周期占用列数
int l = 1 + r - 2;
// 总列数
int c = (n + t - 1) / t * (r - 1);
char[][] d = new char[r][c];
for (int i = 0, x = 0, y = 0; i < n; ++i) {
d[x][y] = s.charAt(i);
// 索引下标，相对位置
if (i % t < r - 1) {
++x; // 向下移动
} else {
--x;
++y; // 向右上移动
}
}
StringBuffer sb = new StringBuffer();
for (char[] row : d) {
for (char i : row) {
if (i != 0) {
sb.append(i);
}
}
}
return sb.toString();
}
// 方法三：直接构造
class Solution:
def convert(self, s: str, numRows: int) -> str:
n, r = len(s), numRows
if r == 1 or r >= n:
return s
t = r * 2 - 2
ans = []
for i in range(r): # 枚举矩阵的行
for j in range(0, n - i, t): # 枚举每个周期的起始下标
ans.append(s[j + i]) # # 当前周期的第一个字符,j就是一个相对位置，从哪开始
if 0 < i < r - 1 and j + t - i < n:
ans.append(s[j + t - i]) # 当前周期的第二个字符
return ''.join(ans)
}
方法三说明：
我们来研究方法一中矩阵的每个非空字符会对应到 s 的哪个下标（记作idx），从而直接构造出答案。
由于 Z 字形变换的周期为 t=2r-2t=2r?2，因此对于矩阵第一行的非空字符，其对应的 \textit{idx}idx 均为 tt 的倍数，即 idx≡0(modt)；同理，对于矩阵最后一行的非空字符，应满足 idx≡r?1(modt)。
对于矩阵的其余行（行号设为 ii），每个周期内有两个字符，第一个字符满足idx≡i(modt)，第二个字符满足 idx ≡t?i(modt)。就是取余
