【一起刷LeetCode】Z字形变换

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

题目描述

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

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

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

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

string convert(string s, int numRows);

示例1:

输入: s = "LEETCODEISHIRING", numRows = 3

输出: "LCIRETOESIIGEDHN"

示例2:

输入: s = "LEETCODEISHIRING", numRows = 4

输出: "LDREOEIIECIHNTSG"

解释:

题解思路

根据题意描述，按照从上到下，从左到右逐个读取Z字形图案的顺序访问字符串。

公式推导法

思路分析：

首先访问第0行中的所有字符串，接着访问第1行，然后第2行.......

对于所有整数n，

  • 行 0 中的字符索引位置：n * (2 * numRows - 2)；

  • 行 i 中的字符索引位置：n * (2 * numRows - 2) - i 和 (n + 1) * (2 * numRows - 2) - i；

  • 行 numRows - 1 中的字符索引位置：n * (2 * numRows - 2) + numRows - 1;

  • 注意：下标n不能超过len(s)-1;

代码示例：

public String convert(String s, int numRows) {
    if (s == null || s.length() == 0 || numRows == 1) return s;
    StringBuilder sb = new StringBuilder();
    int n = s.length();
    int cycleLen = 2 * numRows - 2;
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j + i < n; j += cycleLen) {
            sb.append(s.charAt(j + i));
            if (i != 0 && i != numRows - 1 && j + cycleLen - i < n) {
                sb.append(s.charAt(j + cycleLen - i));
            }
        }
    }
    return sb.toString();
}

复杂度分析：

  • 时间复杂度：O(n), n==len(s)。每个索引都被访问一次。

  • 空间复杂度：O(n)

  • 写作不易，转载请注明出处，喜欢的小伙伴可以关注公众号查看更多喜欢的文章。

  • 联系方式：4272231@163.com

  • QQ:95472323

  • 微信:ffj2000

以上是 【一起刷LeetCode】Z字形变换 的全部内容， 来源链接： utcz.com/z/512120.html

回到顶部