题目

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 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);

思路

没思路，看完发现自己也能看懂，可就是想不起来， NND ，看来还是练习的少

解法一

  1. 创建Math.min(numRows, s.length()数目个行数
  2. 遍历整个字符串，然后放入到相应的行数中，字符和行数都跟着改变
  3. 只有向上移动到最上面或者向下移动到最下面，当前方向才会改变。
  4. 合并输出之前创建的行数即可
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 result = new StringBuilder();
    for (StringBuilder row : rows) {
        result.append(row.toString());
    }

    return result.toString();
}

复杂度分析

  • 时间复杂度：O(n)，其中 n=len(s)
  • 空间复杂度：O(n)

解法二

其实每行都是又规律可循的，这个规律就是

  1. 起始下标都是行号
  2. 第 0 层和第numRows-1层的下标间距总是step
  3. 中间层的下标间距总是step-2行数，2行数交替。
  4. 下标不能超过len(s)-1
  5. setp 等于2*rowNums-2
public String convert(String s, int numRows) {
    if (numRows == 1) {
        return s;
    }
    StringBuilder ret = new StringBuilder();
    int step = 2 * numRows - 2;
    int index = 0;//记录 s 的下标
    int add = 0;//真实的间距
    int len = s.length();

    for (int i = 0; i < numRows; i++) {//i 表示行号
        index = i;
        add = i * 2;
        while (index < len) {//超出字符串长度计算下一行
            ret.append(s.charAt(index));//当前行第一个字符
            add = step - add;//第一次间距是setp-2*i,第二次是2*i
            index += (i == 0 || i == numRows - 1) ? step : add;//0行和最后一行使用 step 间距，其余使用 add 间距
        }
    }
    return ret.toString();
}

找到规律，就好解了。

路漫漫其修远兮，吾将上下而刷题。
— 搬运地址：

Z 字形变换 官方街题