> 文档中心 > 【LeetCode】6、Z字形变换

【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) 的空间。

【LeetCode】6、Z字形变换

字库吧