526互联

力扣6.N 字形变换（压缩矩阵）

发布时间 2023-09-21 13:02:53作者: Coder何

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

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

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

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

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

string convert(string s, int numRows);

 

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

 

示例 2： 
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

 

示例 3：

输入：s = "A", numRows = 1
输出："A"

 

 

提示：

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、',' 和 '.' 组成
  • 1 <= numRows <= 1000

二维矩阵暴力模拟：

 1 class Solution {
 2 public:
 3     char map[1000][1000]; //Z排列
 4     int x=0,y=0; //Z排列中当前坐标
 5     int index=0; //字符串中当前下标
 6     void up(int row,string s){
 7         for (int i=0;i<row-1&&index<s.length();++i){
 8             map[x][y]=s[index];
 9             //更新数据
10             x--;
11             y++;
12             index++;
13         }
14     }
15     void down(int row,string s){
16         for (int i=0;i<row-1&&index<s.length();++i){
17             map[x][y]=s[index];
18             //更新数据
19             x++;
20             index++;
21         }
22     }
23     string convert(string s, int numRows) {
24         string result;
25         memset(map,0,sizeof(map));
26         if (numRows==1||s.length()<=numRows){
27             return s;
28         }
29         while (index<s.length())
30         {
31             down(numRows,s);
32             up(numRows,s);
33         }
34         for (int i=0;i<numRows;++i){
35             for (int j=0;j<=y;++j){
36                 if (map[i][j]){
37                     result.push_back(map[i][j]);
38                 }
39             }
40         }
41         return result;
42     }
43 };

 

该题可以通过压缩矩阵来节省大量空间和遍历时间：

 1 class Solution {
 2 public:
 3     int x=0; //Z排列中当前行号
 4     vector<string> map; 
 5     int index=0; //字符串中当前下标
 6     void up(int row,string s){
 7         for (int i=0;i<row-1&&index<s.length();++i){
 8             map[x].push_back(s[index]);
 9             x--;
10             index++;
11         }
12     }
13     void down(int row,string s){
14         for (int i=0;i<row-1&&index<s.length();++i){
15             map[x].push_back(s[index]);
16             x++;
17             index++;
18         }
19     }
20     string convert(string s, int numRows) {
21         string result;
22         map.resize(numRows);
23         if (numRows==1||s.length()<=numRows){
24             return s;
25         }
26         while (index<s.length())
27         {
28             down(numRows,s);
29             up(numRows,s);
30         }
31         for (int i=0;i<numRows;++i){
32             result.append(map[i]);
33         }
34         return result;
35     }
36 };