[模拟|字符串] leetcode 6 Z字形变换
1.题目
题目链接
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：
L C I RE T O E S I I GE D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。
示例1：
输入: s = "LEETCODEISHIRING", numRows = 3输出: "LCIRETOESIIGEDHN"
示例2：
输入: s = "LEETCODEISHIRING", numRows = 4输出: "LDREOEIIECIHNTSG"解释:LDRE O E I IE C I H NTSG
2.分析
2.1.结果存储
输入给出的是一维的顺序字符串，而输出的字符串是建立在“Z字型”这样一个二维结构上的。因此可以首先考虑建立一个二维数组来存储这个Z字形结构。
由于字符串本质上是一个一维的字符数组，因此我们建立一个字符串数组便可以模拟这一二维结构：
string convert(string s, int numRows) {if (numRows == 1) {//输出也是一行的话则直接返回原字符串return s;}//行数比字符串长度大的话,实际上只有一列vector<string> rows(min(numRows, int(s.size())));//......}
2.2.遍历顺序
“Z字型”(或者看起来更像"N字型")遍历，本质上是先往下，再往上，再往下…因此我们需要判断好什么时候调整遍历的方向。
而只有在两种情况下需要调整方向：遍历到第0行(方向需调整至向下)，遍历到最后一行(方向需调整至向上)。
int curRow = 0; //当前行bool goingDown = false; //是否向下for (char c : s) {rows[curRow] += c; //将该字符存入对应的结果行中if (curRow == 0 || curRow == numRows - 1) {//反向goingDown = !goingDown;}curRow += goingDown ? 1 : -1; //根据方向调整行数}
实际上本题到这里就几乎做完了。以示例2为例，表面上我们要存储的输出为：
LDRE O E I IE C I H NTSG
实际上存储的是：
L D RE O E I IE C I H NT S G
按行展开后依然为LDREOEIIECIHNTSG，因为我们并不关心每行之间的空格。
3.代码
class Solution {public:string convert(string s, int numRows) {//输出也是一行的话则直接返回原字符串if (numRows == 1) {return s;}//行数比字符串长度大的话,实际上只有一列vector<string> rows(min(numRows, int(s.size())));int curRow = 0;//当前行bool goingDown = false;//是否向下for (char c : s) {rows[curRow] += c;//将该字符存入对应的结果行中if (curRow == 0 || curRow == numRows - 1) {//反向goingDown = !goingDown;}curRow += goingDown ? 1 : -1;//根据方向调整行数}string res;for (string row : rows) {res += row;}return res;}};
