自学商城网站建设,做网站设计素材,先锋大牌周爆款好价 79元起 查看详情,长春建设银行网站一、题目描述
将一个给定字符串 s 根据给定的行数 numRows #xff0c;以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 PAYPALISHIRING 行数为 3 时#xff0c;排列如下#xff1a;
P A H N
A P L S I I G
Y I R之后#xff0c;你的输出…一、题目描述
将一个给定字符串 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 1000s 由英文字母小写和大写、, 和 . 组成1 numRows 1000
二、题解
2.1 方法一利用二维矩阵模拟
设 n 为字符串 s 的长度 r n u m R o w s rnumRows rnumRows。对于 r 1 r1 r1只有一行或者 r ≥ n r≥n r≥n只有一列的情况答案与 s 相同我们可以直接返回 s。对于其余情况考虑创建一个二维矩阵然后在矩阵上按 Z 字形填写字符串 s最后逐行扫描矩阵中的非空字符组成答案。
根据题意当我们在矩阵上填写字符时会向下填写 r 个字符然后向右上继续填写 r − 2 r−2 r−2 个字符最后回到第一行因此 Z 字形变换的周期 t r r − 2 2 r − 2 trr−22r−2 trr−22r−2每个周期会占用矩阵上的 1 r − 2 r − 1 1r−2r−1 1r−2r−1 列。
因此我们有 ⌈ n t ⌉ \lceil \frac nt \rceil ⌈tn⌉ 个周期最后一个周期视作完整周期乘上每个周期的列数得到矩阵的列数 c ⌈ n t ⌉ ⋅ ( r − 1 ) c \lceil \frac nt \rceil·(r-1) c⌈tn⌉⋅(r−1) 。
创建一个 r r r 行 c c c 列的矩阵然后遍历字符串 s s s 并按 Z 字形填写。具体来说设当前填写的位置为 ( x , y ) (x,y) (x,y)即矩阵的 x x x 行 y y y 列。初始 ( x , y ) ( 0 , 0 ) (x,y)(0,0) (x,y)(0,0)即矩阵左上角。若当前字符下标 i i i 满足 i ⋅ m o d t r − 1 i· mod tr−1 i⋅ mod tr−1则向下移动否则向右上移动。
填写完成后逐行扫描矩阵中的非空字符组成答案。
Python def convert(self, s: str, numRows: int) - str:n, r len(s), numRowsif r 1 or r n:return st r * 2 - 2c (n t - 1) // t * (r - 1)mat [[] * c for _ in range(r)]x, y 0, 0for i, ch in enumerate(s):mat[x][y] chif i % t r - 1:x 1 # 向下移动else:x - 1y 1 # 向右上移动return .join(ch for row in mat for ch in row if ch)C
string convert(string s, int numRows)
{int n s.length(), r numRows;if (r 1 || r n) {return s;}int t r * 2 - 2;int c (n t - 1) / t * (r - 1);vectorstring mat(r, string(c, 0));for (int i 0, x 0, y 0; i n; i) {mat[x][y] s[i];if (i % t r - 1) {x; // 向下移动} else {--x;y; // 向右上移动}}string ans;for (auto row : mat) {for (char ch : row) {if (ch) {ans ch;}}}return ans;
}复杂度分析
时间复杂度 O ( r ⋅ n ) O(r⋅n) O(r⋅n)其中 r n u m R o w s rnumRows rnumRowsn 为字符串 s 的长度。时间主要消耗在矩阵的创建和遍历上矩阵的行数为 r列数可以视为 O ( n ) O(n) O(n)。空间复杂度 O ( r ⋅ n ) O(r⋅n) O(r⋅n)。矩阵需要 O ( r ⋅ n ) O(r⋅n) O(r⋅n) 的空间。
2.2 方法二压缩矩阵空间
方法一中的矩阵有大量的空间没有被使用能否优化呢
注意到每次往矩阵的某一行添加字符时都会添加到该行上一个字符的右侧且最后组成答案时只会用到每行的非空字符。因此我们可以将矩阵的每行初始化为一个空列表每次向某一行添加字符时添加到该行的列表末尾即可。
Python def convert(self, s: str, numRows: int) - str:r numRowsif r 1 or r len(s):return smat [[] for _ in range(r)]t, x r * 2 - 2, 0for i, ch in enumerate(s):mat[x].append(ch)x 1 if i % t r - 1 else -1return .join(chain(*mat))C
string convert(string s, int numRows)
{int n s.length(), r numRows;if (r 1 || r n) {return s;}vectorstring mat(r);for (int i 0, x 0, t r * 2 - 2; i n; i) {mat[x] s[i];i % t r - 1 ? x : --x;}string ans;for (auto row : mat) {ans row;}return ans;
}复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)压缩后的矩阵需要 O ( n ) O(n) O(n) 的空间。。
2.3 方法三 直接构造
我们来研究方法一中矩阵的每个非空字符会对应到 s 的哪个下标记作 i d x idx idx从而直接构造出答案。
由于 Z 字形变换的周期为 t 2 r − 2 t2r−2 t2r−2因此对于矩阵第一行的非空字符其对应的 i d x idx idx 均为 t t t 的倍数即 i d x ≡ 0 ( m o d t ) idx≡0(modt) idx≡0(modt)同理对于矩阵最后一行的非空字符应满足 i d x ≡ r − 1 ( m o d t ) idx≡r−1(modt) idx≡r−1(modt)。
对于矩阵的其余行行号设为 i i i每个周期内有两个字符第一个字符满足 i d x ≡ i ( m o d t ) idx≡i(modt) idx≡i(modt)第二个字符满足 i d x ≡ t − i ( m o d t ) idx≡t−i(modt) idx≡t−i(modt)。
Python def convert(self, s: str, numRows: int) - str:n, r len(s), numRowsif r 1 or r n:return st r * 2 - 2ans []for i in range(r): # 枚举矩阵的行for j in range(0, n - i, t): # 枚举每个周期的起始下标ans.append(s[j i]) # 当前周期的第一个字符if 0 i r - 1 and j t - i n:ans.append(s[j t - i]) # 当前周期的第二个字符return .join(ans)C
string convert(string s, int numRows)
{int n s.length(), r numRows;if (r 1 || r n) {return s;}string ans;int t r * 2 - 2;for (int i 0; i r; i) { // 枚举矩阵的行for (int j 0; j i n; j t) { // 枚举每个周期的起始下标ans s[j i]; // 当前周期的第一个字符if (0 i i r - 1 j t - i n) {ans s[j t - i]; // 当前周期的第二个字符}}}return ans;
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 为字符串 s s s 的长度。 s s s 中的每个字符仅会被访问一次因此时间复杂度为 O ( n ) O(n) O(n)。 空间复杂度 O ( 1 ) O(1) O(1)。返回值不计入空间复杂度。
