【LeetCode】6、Z字形变换
6、Z字形变换
题目:
将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时,排列如下:
P A H NA P L S I I GY I R
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:“PAHNAPLSIIGYIR”。
请你实现这个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
示例1:
输入:s = "PAYPALISHIRING", numRows = 3输出:"PAHNAPLSIIGYIR"
示例·2:
输入:s = "PAYPALISHIRING", numRows = 4输出:"PINALSIGYAHRPI"解释:P I NA L S I GY A H RP I
示例3:
输入:s = "A", numRows = 1输出:"A"
提示:
1 <= s.length <= 1000s 由英文字母(小写和大写)、',' 和 '.' 组成1 <= numRows <= 1000
解题思路:
看到Z字形变换,脑海里首先想到的就是矩阵了。那我们今天就先用二维矩阵来解一下题。
根据题意,我们会先从第一行开始向下填写 r 个字符(因为 r 行嘛),然后再向右上填写 r -2
个字符,再次回到第一行,此时可以认为一个周期结束。
因此,Z字形变换一个周期所需要的字符为: t = r + r -2 = 2r -2
,每个周期会占用矩阵的列数为: c = 1+r -2 = r-1
列。
结论:Z字变换总共有 n / t
个周期,矩阵的总列数为:z = (n / t)*(r-1)
。
模拟解题:
- 先创建一个二维矩阵,r 行 c列
- 遍历字符串 s 并按 Z 字形填写
- 对于 r=1(只有一行)或者 r≥n(只有一列)的情况,答案与 s 相同,我们可以直接返回 s
- 设当前填写的位置为 (x,y),即 x 行 y列
- 初始 (x,y)=(0,0)
- 若当前字符下标 i 满足
i mod t<r-1
,则向下移动,否则向右上移动。
具体代码:
class Solution { public 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); char[][] mat = new char[r][c]; for (int i = 0, x = 0, y = 0; i < n; ++i) { mat[x][y] = s.charAt(i); if (i % t < r - 1) { ++x; // 向下移动 } else { --x; ++y; // 向右上移动 } } StringBuffer ans = new StringBuffer(); for (char[] row : mat) { for (char ch : row) { if (ch != 0) { ans.append(ch); } } } return ans.toString(); }}
复杂度分析:
时间复杂度:O(r⋅n),其中 r=numRows,n 为字符串 s 的长度。时间主要消耗在矩阵的创建和遍历上,矩阵的行数为 r,列数可以视为 O(n)。
空间复杂度:O(r⋅n)。矩阵需要O(r⋅n) 的空间。