LeetCode 6.z字形变换

LeetCode 6.z字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 LEETCODEISHIRIG 行数为 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDH”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:
输入: s = “LEETCODEISHIRIG”, numRows =
输出: “LCIRETOESIIGEDH”

示例 2:
输入: s = “LEETCODEISHIRIG”, numRows = 4
输出: “LDREOEIIECIHTSG”

解释:

L     D     R
E   O E   I I
E C   I H   
T     S     G

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 思路解析

创建一个字符串数组，用来表示转化后每行的字符串，遍历字符串，把每个字符添加到对应位置。

• 代码

class Solution {
public:string convert(string s, int numRows) {if(numRows==1)return s;int len=s.size();vector<string> sa(numRows);int count=0;int tag=0;for(int i=0;i<len;i){if(count==0)tag=1;if(count==numRows-1) tag=0;if(tag==1){sa[count]=s[i];}else if(tag==0){sa[count--]=s[i];}}string st;for(int i=0;i<numRows;i){st=sa[i];}return st;}
};

• 结果分析

时间复杂度O(n)
空间复杂度O(n)