LeetCode

题目描述：The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) （之字形转换）

input：s = "PAYPALISHIRING", numRows = 3 output："PAHNAPLSIIGYIR" P A H N A P L S I I G Y I R input：s = "PAYPALISHIRING", numRows = 4 output："PINALSIGYAHRPI" P I N A L S I G Y A H R P I

第一种方法：就样例标准来看，输出的图形是有规律的，string的每个组成所在的行是周期分布，该周期为T=numRows+numRows-2；就numRows=4来说，周期为6，分别是0，1，2，3，2，1；可以按照这个规律分别保存string的每个组成的行和列，然后再按行添加的一个新的string中 代码：

string convert(string s, int numRows) { if (s.size() <= numRows||numRows==1) { return s; } else { //result保存结果，result.first保存string的元素下标，result.second保存该下标的行和列 vector<pair<int, pair<int, int>>> result; vector<int> get_row; string ret; for (int i = 0; i != numRows; ++i) { get_row.push_back(i); } for (int i = numRows - 2; i != 0; --i) { get_row.push_back(i); } int t = get_row.size(); int row, col = 0, pos = 0; for (int i = 0; i != s.size(); ++i) { pos = i % t; row = get_row[pos]; if (pos > numRows - 1) { col = (col + 1); } if ((i / t) != 0 && pos == 0) col++; result.push_back({ i,{row,col} }); } //按照行的顺序排列，即0行的在前面，依次排列 std::sort(result.begin(), result.end(), [](pair<int, pair<int, int>>& a, pair<int, pair<int, int>>& b)->bool {return a.second.first < b.second.first; }); for (auto i : result) { ret.push_back(s[i.first]); } return ret; } }

分析：该算法的时间复杂度为O（s.size（）），空间复杂度很高，所以memory limit exceeded,不推荐使用

第二种方法：观察每行的string的下标和T发现，第一行都为i%T==0的，第二行与T的余数都和周期相差1（以numRows=4为例，第二行余数为1或5，在周期上和6均差1），依次； 代码：

string convert(string s, int numRows) { if(numRows==1) { return s; } else { string ret; int T = numRows + numRows - 2; for (int i = 0; i != numRows; i++) { for (int j = 0; j != s.size(); j++) { if (j%T == i || T - j % T == i) { ret.push_back(s[j]); } } } return ret; } }

分析：时间复杂度（numRows*n），空间复杂度O（n）；

第三种方法（官方）

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 ret; for (string row : rows) ret += row; return ret; }

curRow保存当前要处理的行，goingDown控制向下进行还是向上进行，向下进行的条件为curRow==0（在第一行），向上进行的条件为curRow=numRows-1（在最后一行），所以当进行到这两行时，goingDown翻转一次，时间复杂度O（n），空间复杂度O（n）；