题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为"LEETCODEISHIRING"行数为 3 时，排列如下：

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

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

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

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG"

解释:

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

解题思路

1.二维数组排列

直接的方法就是使用一个二维数组来进行题目描述的排列。

class Solution { public: string convert(string s, int numRows) { string res; auto len = s.length(); if(len == 0)return s; if(numRows <=1)return s; int maxcols = 0; maxcols = len/(numRows*2-2)*(1+numRows-2); int mod = len % (numRows*2-2); if(mod>0)maxcols++; if(mod > numRows) maxcols+=(mod-numRows); vector<vector<char>> matrix(numRows,vector<char>(maxcols,0)); int state = 0; int row = 0,col = 0; for(auto c:s) { if(state == 0) { matrix[row++][col] = c; if(row == numRows) { if(numRows>2) state = 1; row-=2; col++; } } else { matrix[row--][col++] = c; if(row == 0) state = 0; } } for(auto& i:matrix) { for(auto j:i) { if(j!=0)res.push_back(j); } } return res; } }; //计算行数花费了很多操作，但是不考虑内存占用的话，可以直接设置列数为len

2.字符数组

考察二维数组的排列方式，我们可以看到，其实我们不需要那么复杂的去排列字符的位置。我们只需要记录下每一行的字符的先后顺序即可，因为我们最终输出的是从左往右的字符序列。 可以总结出，我们只需要``numRows```个字符串（$s_0...s_{numRows-1}$，对输入字符串的每个字符，依次添加到$s_0....s_{numRows-1}$然后反序，再正序…如此往复即可。

class Solution { public: string convert(string s, int numRows) { string res; vector<string>strs(numRows); int row = 0; int inc = 1; for(auto c:s) { strs[row].push_back(c); if(row == numRows-1)inc=-1; if(row == 0)inc=1; row=(row+inc)%numRows; } for(auto c :strs) { res+=c; } return res; } };