LeetCode 6. Z 字形变换

约 5 分钟
文章信息 12 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 需加强 20-50 字节跳动 美团 快手 百度 华为 面试经典 150 题
标签
字符串
目录

题目描述

✅ 6. Z 字形变换

image-20230311200513009

image-20230311200554018

题意分析

题目描述的是一种书写方式：把字符串按给定行数从上往下逐个写下来，写到最后一行后拐弯斜着往上走，回到第一行再重新向下，如此往复形成 Z 字形轨迹；写完后从第一行开始逐行从左往右读，把读到的字符依次拼起来就是答案。

需要看清的是，题目问的只是最终拼接出的字符串，而不是那张排布图本身。排布图里的空位从头到尾都不会出现在答案中，所以真正需要确定的信息只有一条：每个字符属于第几行。至于它在行内的横坐标，由于同一行的字符在答案里的先后顺序与它们在原串中的先后顺序完全一致，压根不需要计算。

约束上，字符串长度在千级，行数不超过字符串长度的量级，一次线性扫描绰绰有余。边界要留意两处：行数为 1 时轨迹是一条直线，永远不拐弯，输出就是原串；行数大于等于字符串长度时每个字符独占一行，逐行读取的结果同样是原串。字符集包含大小写字母、逗号和点号，但本题不对字符内容做任何区分。

解法：按行模拟方向变化

核心思路

最直观的二维矩阵会保存列坐标和大量空位，但最终答案只按行读取；真正需要维护的只有“当前字符属于哪一行”。为每一行准备一个缓冲区，扫描原串时把字符追加到对应行，最后自上而下拼接即可。

行号在 0 到 numRows - 1 之间往返。例如三行时依次为 0, 1, 2, 1, 0, ...。用 row 表示当前行、direction 表示下一步方向：到首行后向下，到末行后向上，再执行 row += direction。

循环不变量是：处理每个字符前，row 就是它在 Z 字形中的正确行号，并且始终位于合法范围内。追加字符后在边界行调整方向，所以下一个字符的行号也正确；归纳可知所有字符都进入正确的行。每行内部按原串顺序追加，最终按行拼接正好就是题目要求的读取顺序。

解题步骤

  1. 若 numRows == 1 或 numRows >= s.length()，直接返回原串；此时不会发生有效折返。
  2. 创建 numRows 个行缓冲区，初始化 row = 0、direction = 1。
  3. 从左到右扫描字符串，把当前字符追加到 rows[row]。
  4. 当前位于首行时令方向向下，位于末行时令方向向上，再更新 row。
  5. 按第 0 行到最后一行的顺序拼接所有缓冲区。

以 "PAYPALISHIRING"、numRows = 3 为例，行号序列为 0,1,2,1,...，三行分别得到 PAHN、APLSIIG、YIR，拼接结果为 "PAHNAPLSIIGYIR"。

代码实现

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1 || numRows >= s.length()) {
            return s;
        }

        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }

        int row = 0;
        int direction = 1;
        for (int i = 0; i < s.length(); i++) {
            rows[row].append(s.charAt(i));
            if (row == 0) {
                direction = 1;
            } else if (row == numRows - 1) {
                direction = -1;
            }
            row += direction;
        }

        StringBuilder ans = new StringBuilder(s.length());
        for (StringBuilder builder : rows) {
            ans.append(builder);
        }
        return ans.toString();
    }
}

func convert(s string, numRows int) string {
    if numRows == 1 || numRows >= len(s) {
        return s
    }

    rows := make([][]byte, numRows)
    row, direction := 0, 1
    for i := 0; i < len(s); i++ {
        rows[row] = append(rows[row], s[i])
        if row == 0 {
            direction = 1
        } else if row == numRows-1 {
            direction = -1
        }
        row += direction
    }

    ans := make([]byte, 0, len(s))
    for i := range rows {
        ans = append(ans, rows[i]...)
    }
    return string(ans)
}

复杂度分析

  • 时间复杂度：$O(n)$。每个字符追加一次，最终拼接时再复制一次。
  • 空间复杂度：$O(n)$。各行缓冲区合计保存 $n$ 个字符；不计返回值仍需这些缓冲区。

关键点总结

  • 只记录答案需要的行号，不必构造带空位的二维排布。
  • direction 表示“下一步往哪走”，因此应在当前位置判断是否到达边界，再移动行号。
  • numRows == 1 时首行和末行重合，必须提前返回。
  • 面试中先写按行模拟最稳；周期下标法同为线性复杂度，但分支更多，除非被追问无需主动增加风险。

易错点总结

  • 漏掉单行特判：s = "AB"、numRows = 1 时，更新行号后会访问越界。
  • 先执行 row += direction 再判断边界，会让 row 短暂越过首行或末行。
  • 扫描时直接追加到同一个答案串只会得到原字符串；必须先按行归类，再逐行拼接。
  • Java 的 StringBuilder[] 创建后元素仍是 null，必须逐个初始化。
  • Go 代码按字节处理是因为题目字符均为单字节 ASCII；若输入扩展到 Unicode，应改为遍历 []rune。

相似题目

题目 难度 考察点
54. 螺旋矩阵 中等 二维边界收缩的转向模拟，方向切换由边界相遇触发
59. 螺旋矩阵 II 中等 反向填充螺旋序列，考察构造而非读取时的转向控制
498. 对角线遍历 中等 斜向往复遍历，转向发生在四条边界上，分支比本题更多
剑指 Offer 29. 顺时针打印矩阵 简单 螺旋遍历的入门版，适合先练顺时针方向数组的写法