265 字
1 分钟
LeetCode 面试经典150题 [22/150 Z字型变化]
题目描述
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H NA P L S I I GY I R之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);示例 1：
输入：s = "PAYPALISHIRING", numRows = 3输出："PAHNAPLSIIGYIR"示例 2：
输入：s = "PAYPALISHIRING", numRows = 4输出："PINALSIGYAHRPI"解释：P I NA L S I GY A H RP I示例 3：
输入：s = "A", numRows = 1输出："A"个人C++解答
class Solution {public: string convert(string s, int numRows) { if (numRows <= 1 || numRows >= s.length()) { return s; } vector<vector<char>> str(numRows, vector<char>(s.length(), ' ')); int str_i = 0, str_j = 0; str[0][0] = s[0]; for (int i = 1; i < s.length(); i++) { int temp = i % (2 * numRows - 2); cout << temp << endl; if (0 < temp && temp < numRows) { str_i++; }else{ str_i--; str_j++; } str[str_i][str_j] = s[i]; } string result; for (const auto& row : str) { for (char c : row) { if (c != ' ') result.push_back(c); }cout << endl; } return result; }};官方题解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; }}; 分享
如果这篇文章对你有帮助，欢迎分享给更多人！
LeetCode 面试经典150题 [22/150 Z字型变化]
https://ericonline.cn/posts/leetcode-面试经典150题-22-150-z字型变化/ 部分信息可能已经过时
相关文章 智能推荐