6. ZigZag Conversion

题面

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)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

样例

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I
 //思路1:
//完全按照样例来模拟过程
//时间:O(n2)
//空间:O(n2)
1
class Solution { 2 public: 3 string convert(string s, int numRows) { 4 int len = s.length(); 5 if(len < 3) 6 return s; 7 char ans[len][len];
       //记忆化数组初始化为'#'
8 for (int i = 0; i < len; i++) 9 { 10 for (int j = 0; j < len; j++) 11 { 12 ans[i][j] = '#'; 13 } 14 } 15 int i = 0, col = 0; 16 while (i < len) 17 {
         //竖列
18 for (int j = 0; j < numRows; j++) 19 { 20 ans[j][col] = s[i++]; 21 if (i >= len) 22 break; 23 }
         //斜列
24 for (int j = numRows - 2; j >= 1; j--) 25 { 26 if (i >= len) 27 break; 28 ans[j][++col] = s[i++]; 29 } 30 col++; 31 if (i >= len) 32 break; 33 } 34 s = "";
       //行遍历,得结果
35 for (int i = 0; i < len; i++) 36 { 37 for (int j = 0; j < len; j++) 38 { 39 if (ans[i][j] != '#') 40 s += ans[i][j]; 41 } 42 } 43 return s; 44 } 45 };
 //思路2:官方题解
//1. 把每一行当作一个字符串进行处理,vector<string> 当作容器;
//2. 遍历字符串,为各行字符串添加元素;
//3. 行序号的变换(+1/-1)依靠一个bool变量控制,每当到达第一行/最后一行,bool变量取反
//时间:O(n)
//空间:O(n)
1
class Solution { 2 public: 3 string convert(string s, int numRows) { 4 if(numRows == 1) 5 return s; 6 int len = s.length(); 7 vector<string> rows(min(numRows, len)); 8 bool change = false; 9 int currow = 0;
       //C++ 11的写法
10 for(char c : s) 11 { 12 rows[currow] += c; 13 if(currow == 0 || currow == numRows-1) 14 change = !change; 15 currow += (change) ? 1 : -1; 16 } 17 s = ""; 18 for(string per : rows) 19 s += per; 20 21 return s; 22 } 23 };
//真的🐮!