【模拟】N 字形变换（medium）

题⽬链接：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

解法（模拟 + 找规律）：

算法思路：

找规律，⽤ row 代替⾏数，row = 4 时画出的 N 字形如下：
0 2row - 2 4row - 4
1 2row - 3 2row - 1 4row - 5 4row - 3
2 2row-4 2row 4row - 6 4row - 2
3 2row + 1 4row - 1
不难发现，数据是以 2row - 2 为⼀个周期进⾏规律变换的。将所有数替换成⽤周期来表⽰的变量：
第⼀⾏的数是：0, 2row - 2, 4row - 4；
第⼆⾏的数是：1, (2row - 2) - 1, (2row - 2) + 1, (4row - 4) - 1, (4row - 4) + 1；
第三⾏的数是：2, (2row - 2) - 2, (2row - 2) + 2, (4row - 4) - 2, (4row - 4) + 2；
第四⾏的数是：3, (2row - 2) + 3, (4row - 4) + 3。
可以观察到，第⼀⾏、第四⾏为差为 2row - 2 的等差数列；第⼆⾏、第三⾏除了第⼀个数取值为⾏数，每组下标为(2n - 1, 2n)的数围绕（2row - 2）的倍数左右取值。
以此规律，我们可以写出迭代算法。

算法代码：

class Solution{public String convert(String s, int numRows) {// 处理⼀下边界情况if(numRows == 1) return s;int d = 2 * numRows - 2, n = s.length();StringBuilder ret = new StringBuilder();// 1. 处理第⼀⾏for(int i = 0; i < n; i += d)ret.append(s.charAt(i));// 2. 处理中间⾏for(int k = 1; k < numRows - 1; k++) { // 依次枚举中间⾏ for(int i = k, j = d - i; i < n || j < n; i += d, j += d){if(i < n) ret.append(s.charAt(i));if(j < n) ret.append(s.charAt(j));}}// 3. 处理最后⼀⾏for(int i = numRows - 1; i < n; i += d)ret.append(s.charAt(i));return ret.toString();}
}