6. Z 字形变换
将一个给定字符串 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
My Thoughts
数据结构
构造一个二维数组，用来存放这个 Z 字形，然后按照行遍历即可
算法
为了构造这个 Z 字形，我们必须找到索引 i 和二维字符数组行 r 以及列 c 之间的关系。
通过观察可以发现 Z 字形具有周期性，比如上面的例子可以分为下面三段：
P I N
A L S I G
Y A H R
P I
很明显的每一个周期有多少字符和给定的 numRows 相关。
通过观察可以发现，\(每一个周期的字符数 = 2*numRows - 2\)，由此我们可以进行取模运算，进行规约。进行取模运算后，我们就可以得到索引 i 在这个周期中的序号数 t。我们将根据这个序号数 t 求得 r 和 c。
我们可以发现每个周期的第一列比较特殊，一共有 numRows 个字符，所以我们由此为分界点。
- 如果
t <= numRows - 1，那么r = t，每一个周期有numRows - 1列，因此c = (i/(2*numRows - 2))*(numRows-1)。 - 否则，
r = 2*numRows - 2 - t;c = (i/(2*numRows-2))*(numRows-1) + i%(2*numRows-2)-(numRows-1);
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
char a[1005][1005];
// cout << a[0][0] << "--" << endl;
memset(a, 0, sizeof a);
int n = s.size();
for (int i = 0; i < n; i++) {
int t = i % (2*numRows - 2);
int c, r;
if (t <= numRows - 1) {
c = (i / (2*numRows - 2))*(numRows-1);
r = t;
} else {
c = (i / (2*numRows-2))*(numRows-1) + i%(2*numRows- 2)-numRows+1;
r = 2*numRows - 2 - t;
}
// cout << "str:" << s[i] << " r:" << r << " c:" <<c <<endl;
a[r][c] = s[i];
}
// cout << a[0][6] << "---" <<endl;
string res;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j <= 1003; j++) {
if (a[i][j] != 0) res.push_back(a[i][j]);
}
}
return res;
}
};
优化
我们可以不用构造二维字符数组，只需要构造一个 vector<string> 就够了。因此我们也不需要求列数，所以代码得到了极大的优化。
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
int n = s.size();
vector<string> v(numRows);
for (int i = 0; i < n; i++) {
int t = i % (2*numRows - 2);
if (t > numRows - 1) t = 2 * numRows - 2 - t;
v[t].push_back(s[i]);
}
string res;
for (int i = 0; i < numRows; i++) {
res += v[i];
}
return res;
}
};
官方版本
根据索引直接找到下一个周期的该行的位置
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
int n = s.size();
string res;
int cycle = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycle) {
res += s[j + i];
if (i != 0 && i != numRows - 1 && j + cycle - i < n) {
res += s[j + cycle - i];
}
}
}
return res;
}
};