Z字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

1
string convert(string s, int numRows);

示例 1：

1
2
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

1
2
3
4
5
6
7
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

1
2
输入：s = "A", numRows = 1
输出："A"
1
2
3
4
5
6
7
int n=numRows
 行
 0 |P    | I    N
 1 |A   L| S  I G
 2 |Y A  | H R
 3 |P    | I

圈起来的这部分是一个周期，周期长度是n+n-2==2*n-2。设周期长度为len.

一个周期可以分为左边的竖直部分和右边的斜上部分。

如果序列里的第i个元素在竖直部分，则对应的列数为i%len。非常明显

如果序列里的第i个元素在斜上部分，显然i%len>n-1,那么这个元素比最底部的元素高i%len-(n-1)，所以这个元素所在的行为行高-上述式子，即n-1-[i%len-(n-1)]化简得2*n-2-i%len.

设置两层循环，第一层循环每一行，第二层循环整个序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string convert(string s, int numRows) {
        int n=numRows;
        if(n==1) return s;
        int len=s.size();
        string ans="";
        for(int i=0;i<n;i++){
            for(int j=0;j<len;j++){
                if(j%(2*n-2)==i || 2*n-2-j%(2*n-2)==i)
                ans+=s[j];
            }
        }
        return ans;
    }
};