将一个给定字符串 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 <= 1000s由英文字母（小写和大写）、','和'.'组成1 <= numRows <= 1000
解题思路
这道题其实是可以直接模拟的，我们可以先创建一个 n * len 大小的二维数组，这里的 n 表示题目给的行数，len 表示字符串的长度，然后根据题目要求，先向下遍历数组，然后再往右上角遍历，不断执行这个操作直到字符串遍历完毕！如下图所示：
但是这样子其实时间复杂度和空间复杂度都是比较大的，都是 O(len * n)，所以我们需要进行优化一下！对于这种模拟题来说，我们只能找找题目的规律进行入手。
下面我们以一个 n=4 行数为例，然后将字符串中每个字符的下标根据 N 字形映射到矩阵中，看看有什么规律：
可以看到第一行和最后一行好像有点规律，就是它们几个数之间的差值都是 6，而这个差值是怎么来的呢❓❓❓
仔细观察就能看出，这个差值就是二维数组中前三列包含的元素个数，我们可以把图中的下标 5 放到第二列中，我们就能得到一个差值公式：2n - 2，如下图所示：
然后对于第一行和最后一行来说，我们可以直接查找该差值下标处对应的所有字符，而不需要去模拟了！
但是对于中间的其它行来说，好像规律不太一样，我们再仔细观察其实也可以发现是有规律的！比如第二行中 1 和 5，其实它们加起来就等于上面求出来的差值 6，而第三行的 2 和 4 也是如此。
而我们拿第二行为例，对应的二维数组下标就是 i = 1，又此时差值 d = 6，我们就能得到第一组**（1，5）其实就是（i，d-i），而第二组的（7，11）其实就是（i+d，d-i+d），对应起来就是（1+6，6-1+6）**，后面也是如此……
所以我们就能得出中间每行的规律：（i + 0*d，d-i + 0*d）、（i + 1*d，d-i + 1*d）、（i + 2*d，d-i + 2*d）……
这对于 n 等于其它值来说也是同样成立的。
只不过有一个特殊情况，就是 n = 1 的时候，此时差值 2*n - 2 得到是 0，代码中其实会陷入死循环，所以我们需要对 n = 1 的情况进行特殊处理！
class Solution {
public:
string convert(string s, int n) {
if(n == 1)
return s; // 处理特殊情况
int d = 2*n - 2; // 求出差值
string ret;
// 先处理第一行
for(int i = 0; i < s.size(); i += d)
ret += s[i];
// 然后处理中间行
for(int k = 1; k < n - 1; k++)
{
// 对中间每一行进行处理
// 下面的条件中必须使用||而不是&&，因为i和j其中有一个满足不越界的，就要插入到ret中
for(int i = k, j = d - k; i < s.size() || j < s.size(); i += d, j += d)
{
if(i < s.size())
ret += s[i];
if(j < s.size())
ret += s[j];
}
}
// 最后处理最后一行
for(int i = n - 1; i < s.size(); i += d)
ret += s[i];
return ret;
}
};