难度:中等
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/zigzag-conversion/
1. 问题描述
将一个给定字符串 s
根据给定的行数 numRows
,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING"
行数为 3
时,之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"
。
2. 分析与解答
思路:矩阵模拟。分为两步:
- 向下遍历
- 向右上遍历
class Solution {
public:
string convert(string s, int numRows) {
// 模拟
int n = s.length();
if (numRows == 1 || numRows >= n) {
return s;
}
vector<vector<char>> vec(numRows, vector<char>(n));
int i = 0, j = 0, k = 0;
// 向下走
while (k < n) {
while (i < numRows-1 && k < n) {
vec[i][j] = s[k];
i ++;
k ++;
}
while (i > 0 && k < n) {
vec[i][j] = s[k];
i --;
j ++;
k ++;
}
}
string res = "";
for (int x = 0; x < numRows; x++) {
for (int y = 0; y < n; y++) {
if (vec[x][y]) res += vec[x][y];
}
}
return res;
}
};