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

题解 1 (按行排序)

public String convert(String s, int numRows) {
    if (numRows == 1) return s;

    List<StringBuilder> rows = new ArrayList<>();
    for (int i = 0; i < Math.min(numRows, s.length()); i++)
        rows.add(new StringBuilder());

    int curRow = 0;
    boolean goingDown = false;

    for (char c : s.toCharArray()) {
        rows.get(curRow).append(c);  // 按行存值
        if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;  // 转向,很独特的方法,学到了
        curRow += goingDown ? 1 : -1;  // 递增或递减
    }

    StringBuilder ret = new StringBuilder();
    for (StringBuilder row : rows) ret.append(row);  // 拼接字符串
    return ret.toString();
}

复杂度分析

  • 时间复杂度:$O(n)$,其中 $ n==len(s)$
  • 空间复杂度:$O(n)$

题解 2 (按行访问)

public String convert(String s, int numRows) {
    if (numRows == 1) return s;

    StringBuilder ret = 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) {
            ret.append(s.charAt(j + i));
            if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                ret.append(s.charAt(j + cycleLen - i));
        }
    }
    return ret.toString();
}

复杂度分析

  • 时间复杂度:$O(n)$,其中 $n==len(s)$。每个索引被访问一次。
  • 空间复杂度:$O(n)$。

手记

两种方法都不错,尤其是第一种。
可惜我个菜鸡,自己写了半天超内存是最难受的。