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 };
//真的🐮!