Leetcode算法系列| 6. Z 字形变换

发布时间:2023年12月26日

1.题目

将一个给定字符串 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

2.题解

C# 解法一:利用二维矩阵模拟

1

public 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][];
        for (int i = 0; i < r; ++i) {
            mat[i] = new char[c];
        }
        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; // 向右上移动
            }
        }
        StringBuilder ans = new StringBuilder();
        foreach (char[] row in mat) {
            foreach (char ch in row) {
                if (ch != 0) {
                    ans.Append(ch);
                }
            }
        }
        return ans.ToString();
    }
}

1

  • 时间复杂度:O(r?n)
    • 其中 r=numRows,n 为字符串 s 的长度。时间主要消耗在矩阵的创建和遍历上,矩阵的行数为 r,列数可以视为 O(n)
  • 空间复杂度:O(r?n)
    • 使矩阵需要 O(r?n) 的空间。

C# 解法二:压缩矩阵空间

  • 方法一中的矩阵有大量的空间没有被使用,能否优化呢?
    注意到每次往矩阵的某一行添加字符时,都会添加到该行上一个字符的右侧,且最后组成答案时只会用到每行的非空字符。因此我们可以将矩阵的每行初始化为一个空列表,每次向某一行添加字符时,添加到该行的列表末尾即可。
public class Solution {
    public string Convert(string s, int numRows) {
        int n = s.Length, r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        StringBuilder[] mat = new StringBuilder[r];
        for (int i = 0; i < r; ++i) {
            mat[i] = new StringBuilder();
        }
        for (int i = 0, x = 0, t = r * 2 - 2; i < n; ++i) {
            mat[x].Append(s[i]);
            if (i % t < r - 1) {
                ++x;
            } else {
                --x;
            }
        }
        StringBuilder ans = new StringBuilder();
        foreach (StringBuilder row in mat) {
            ans.Append(row);
        }
        return ans.ToString();
    }
}

2

  • 时间复杂度:O(n)。
  • 空间复杂度:O(n)
    • 压缩后的矩阵需要 O(n) 的空间。

Python3 解法三:直接构造

3

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        n, r = len(s), numRows
        if r == 1 or r >= n:
            return s
        t = r * 2 - 2
        ans = []
        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)

3

  • 时间复杂度:O(n)
    • 其中 n 为字符串 s 的长度。s 中的每个字符仅会被访问一次,因此时间复杂度为 O(n)。
  • 空间复杂度:O(1)
    • 使返回值不计入空间复杂度。
文章来源:https://blog.csdn.net/backlighting2015/article/details/135174479
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。