0. 题目

题目链接：【0006】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

1. 参考答案一（官方）

链接

1.1 方法一：利用二维矩阵模拟（未搞懂）

class Solution {
public:string convert(string s, int numRows) {int n = s.length(), r = numRows;if (r == 1 || r >= n) {return s;}/* fyo: 因此 Z 字形变换的周期占用字符数 t=r+r-2=2r−2	*//* fyo: 每个周期会占用矩阵上的 1+r-2=r-1 列	*/int t = r * 2 - 2;/* fyo: 此处有疑问，个人认为c应当是完整周期的个数 *//* fyo: 因此 c = n / t * (r - 1) */int c = (n + t - 1) / t * (r - 1);vector<string> mat(r, string(c, 0));	// fyo: 得注意for (int i = 0, x = 0, y = 0; i < n; ++i) {mat[x][y] = s[i];if (i % t < r - 1) {++x;	//向下移动}else {--x;	//向上移动++y;	//向右移动}}string ans;for (auto& row : mat) {		/ fyo: 求解释 */for (char ch : row) {	/ fyo: 求解释 */if (ch) {			/ fyo: 求解释 */ans += ch;		/ fyo: 求解释 */}					}}return ans;}
};

1.2 方法二：压缩矩阵空间（未搞懂）

class Solution {
public:string convert(string s, int numRows) {int n = s.length(), r = numRows;if (r == 1 || r >= n) {return s;}vector<string> mat(r);for (int i = 0, x = 0, t = r * 2 - 2; i < n; ++i) {mat[x] += s[i];i % t < r - 1 ? ++x : --x;}string ans;for (auto &row : mat) {ans += row;}return ans;}
};

1.3 方法三：直接构造（未搞懂）

class Solution {
public:string convert(string s, int numRows) {int n = s.length(), r = numRows;if (r == 1 || r >= n) {return s;}string ans;int t = r * 2 - 2;for (int i = 0; i < r; ++i) { // 枚举矩阵的行for (int j = 0; j + i < n; j += t) { // 枚举每个周期的起始下标ans += s[j + i]; // 当前周期的第一个字符if (0 < i && i < r - 1 && j + t - i < n) {ans += s[j + t - i]; // 当前周期的第二个字符}}}return ans;}
};

2. 参考答案二

链接

2.1 思路1（未搞懂）

class Solution {
public:string convert(string s, int numRows) {if (numRows == 1) return s;vector<string> rows(min(numRows, int(s.size()))); // 防止s的长度小于行数int curRow = 0;bool goingDown = false;for (char c : s) {rows[curRow] += c;if (curRow == 0 || curRow == numRows - 1) {// 当前行curRow为0或numRows -1时，箭头发生反向转折goingDown = !goingDown;}curRow += goingDown ? 1 : -1;}string ret;for (string row : rows) {// 从上到下遍历行ret += row;}return ret;}
};

2.2 思路2（未搞懂）

class Solution {
public:string convert(string s, int numRows) {if (numRows == 1) return s;int step = numRows * 2 - 2; // 间距int index = 0;// 记录s的下标int len = s.length();int add = 0; // 真实的间距string ret;for (int i = 0; i < numRows; i++) // i表示行号{index = i;add = i * 2;while (index < len)//超出字符串长度计算下一层{ret += s[index]; // 当前行的第一个字母add = step - add;// 第一次间距是step -2*i，第二次是2*i, index += (i == 0 || i == numRows-1) ? step : add; // 0行和最后一行使用step间距，其余使用add间距}}return ret;}
};