JAVA 牛牛

6. Z 字形变换

  • May 14, 2020
  • 0 views
  • 难度：中等
  • 本题涉及算法：
  • 思路：
  • 类似题型:

6. Z 字形变换

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

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

L   C   I   R
E T O E S I I G
E   D   H   N

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

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

string convert(string s, int numRows);

示例 1:

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

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

方法一

解题思路

  • 题目理解：
    • 字符串 s 按照 Z 形状排列字符串，最后按照行打印
    • 我们假设 numRows 对应的行是 $r_1,r_2…r_n$ , 排序顺序异常是按照 从上到下 $r_1,r_2 …r_n$ 再从下到上 $r_i …r_2,r_1$ ,反复进行
    • 因此我们的解题思路是：模拟这个行的变化，在遍历 s 的同时，把每个字符串添加到对应的行 res[i]
  • 算法流程：按照顺序遍历 s;
    1. res[i] += c： 把每个字符 c 填入对应行 $r_i$；
    2. i += flag： 更新当前字符 c 对应的行索引；
    3. flag = - flag： 在达到 $Z$ 字形转折点时，执行反向。
  • 复杂度分析：
    • 时间复杂度 $O(N)$ ：遍历一遍字符串 s；
    • 空间复杂度 $O(N)$ ：各行字符串共占用 $O(N)$ 额外空间。

代码

python

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows < 2:
            return s
        res = ['' for _ in range(numRows)]
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i==0 or i == numRows - 1 : flag = -flag
            i += flag
        return ''.join(res)

java

class Solution {
    public String convert(String s, int numRows) {
        if (numRows < 2)
            return s;
        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < numRows; i++)
        rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for(char c:s.toCharArray()){
            rows.get(i).append(c);
            if (i==0 || i==numRows-1)
                flag = -flag;
            i += flag;
        }
        StringBuilder  res = new StringBuilder();
        for(StringBuilder str :rows)
            res.append(str);
        return res.toString();
    }
}
  • 如果你觉得本文对你有帮助，请点赞👍支持
  • 如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出
Search