力扣-6. Z字变换（ZigZag Conversion）

最后编辑于2025-5-26

6. Z字变换（ZigZag Conversion）

Medium

将字符串 s 按给定行数 numRows 以之字形排列，然后逐行读取得到新的字符串并返回。

示例 1：

输入： s = "PAYPALISHIRING", numRows = 3
输出： "PAHNAPLSIIGYIR"

示例 2：

输入： s = "PAYPALISHIRING", numRows = 4
输出： "PINALSIGYAHRPI"
解释：

1
2
3
4
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入： s = "A", numRows = 1
输出： "A"

约束：

  • 1 <= s.length <= 1000
  • s 由大小写英文字母、, 和 . 组成
  • 1 <= numRows <= 1000

问题分析

将字符串按 numRows 行以之字形排列，观察各行字符在原串中的下标规律可以发现：

  • 当 numRows == 1 时，原串即为结果。
  • 用 cycle = 2 * numRows - 2 表示一个完整纵向+斜向的周期（首尾行没有斜向元素）。
  • 对于首行和尾行，相邻两个字符在原串中的下标差为 cycle。
  • 对于中间行（i 行，0 < i < numRows-1），每个周期会出现两个字符：一个在 j（基于首个周期偏移）的黑色位置，另一个在 j + cycle - 2*i 的红色位置（若该位置存在）。

根据上述规律可以有两类解法：按数学规律直接计算下标（一次拼接即可），或模拟之字形把字符填到每一行的字符串数组，最后合并各行。

方法一：按下标规律直接拼接（一次遍历每一行）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) return s;
        string res;
        int cycle = 2 * numRows - 2;
        int n = s.size();
        for (int i = 0; i < numRows; ++i) {
            for (int j = i; j < n; j += cycle) {
                res += s[j];
                int pos = j + cycle - 2 * i; // 中间斜向元素的位置
                if (i != 0 && i != numRows - 1 && pos < n) res += s[pos];
            }
        }
        return res;
    }
};
  • 时间复杂度： O(n)
  • 空间复杂度： O(1)（不含返回字符串）

要点： 直接按行计算字符在原串中的下标，不做额外模拟，速度快且代码简洁。

方法二：模拟之字形（更直观）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) return s;
        int n = s.size();
        vector<string> rows(min(numRows, n));
        int cur = 0; // 当前行
        bool goingDown = false; // 方向
        for (char c : s) {
            rows[cur] += c;
            if (cur == 0 || cur == numRows - 1) goingDown = !goingDown;
            cur += goingDown ? 1 : -1;
        }
        string res;
        for (auto &row : rows) res += row;
        return res;
    }
};
  • 时间复杂度： O(n)
  • 空间复杂度： O(n)

要点： 使用 numRows 个字符串来模拟每一行的字符，按“竖 + 斜”方向切换填充，最后拼接即可，代码直观易懂。

复杂度与选择建议

  • 两种方法时间复杂度同为 O(n)，但方法一更节省额外空间且常数项更小；方法二更直观，易于实现和理解。
  • 当 numRows 很大接近 s.length() 时，方法二仍然稳定；当追求极致性能时推荐方法一。

作者想说的话：
Z 字变换题主要考察对下标规律的观察与字符串拼接能力。先写模拟法通过样例，再补充按下标的 O(1) 空间解法会更稳妥。