0006. Zigzag Conversion
=======================
题目信息
--------
:题号: 0006. Z 字形变换
:难度: Medium
:主题: 字符串、模拟、周期、索引映射
:原题: `LeetCode 0006 `_
:重点: 从往返行轨迹提取周期,再按最终行序直接访问原字符串,删除中间行缓冲区
题目重述
--------
给定字符串 ``s`` 和正整数 ``numRows``,依次把字符写入若干行:先从第 0 行向下移动到最后一行,再沿斜线向上移动回第 0 行,如此反复。完成排列后,按照从上到下、每行从左到右的顺序连接所有字符并返回。
排版中的空白位置不属于结果,每个输入字符必须恰好出现一次。字符串长度和 ``numRows`` 均位于 ``[1, 1000]``;字符串只包含英文字母、逗号和句点。
自建示例
--------
* 三行经典排列:``s = "PAYPALISHIRING"``、``numRows = 3``,各行为 ``"PAHN"``、``"APLSIIG"``、``"YIR"``,返回 ``"PAHNAPLSIIGYIR"``;
* 四行未完整周期:``s = "ABCDEFGHIJK"``、``numRows = 4``,各行为 ``"AG"``、``"BFH"``、``"CEIK"``、``"DJ"``,返回 ``"AGBFHCEIKDJ"``;
* 两行排列:``s = "ABCDE"``、``numRows = 2``,行号交替为 ``0, 1, 0, 1, 0``,返回 ``"ACEBD"``;
* 单行退化:``s = "CODE"``、``numRows = 1``,返回 ``"CODE"``;
* 行数不少于字符数:``s = "HI"``、``numRows = 5``,返回 ``"HI"``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
std::string simulatePath(const std::string& s, int numRows) {
if (numRows == 1 || numRows >= static_cast(s.size())) {
return s;
}
std::vector rows(numRows);
int row = 0;
int direction = 1;
for (char ch : s) {
rows[row].push_back(ch);
if (row == 0) {
direction = 1;
} else if (row == numRows - 1) {
direction = -1;
}
row += direction;
}
std::string result;
result.reserve(s.size());
for (const std::string& current : rows) {
result += current;
}
return result;
}
std::string groupByCycle(const std::string& s, int numRows) {
const int length = static_cast(s.size());
if (numRows == 1 || numRows >= length) {
return s;
}
const int cycle = 2 * numRows - 2;
std::vector rows(numRows);
for (int index = 0; index < length; ++index) {
const int offset = index % cycle;
const int row = offset < numRows ? offset : cycle - offset;
rows[row].push_back(s[index]);
}
std::string result;
result.reserve(s.size());
for (const std::string& current : rows) {
result += current;
}
return result;
}
std::string readByCycle(const std::string& s, int numRows) {
const int length = static_cast(s.size());
if (numRows == 1 || numRows >= length) {
return s;
}
const int cycle = 2 * numRows - 2;
std::string result;
result.reserve(s.size());
for (int row = 0; row < numRows; ++row) {
for (int vertical = row; vertical < length; vertical += cycle) {
result.push_back(s[vertical]);
const int diagonal = vertical + cycle - 2 * row;
if (row > 0 && row < numRows - 1 && diagonal < length) {
result.push_back(s[diagonal]);
}
}
}
return result;
}
public:
std::string convert(std::string s, int numRows) {
return readByCycle(s, numRows);
}
};
题解
----
路径模拟
~~~~~~~~
最直接的做法不需要创建带空格的二维图形,只要为每一行保存一个字符串。扫描输入时维护当前行 ``row`` 和移动方向 ``direction``:向下时为 ``1``,向上时为 ``-1``。
字符写入当前行后,只有两个转向点需要处理:到达第 0 行后只能向下,到达最后一行后只能向上。于是行号依次变化为:
``0, 1, 2, ..., numRows - 1, numRows - 2, ..., 1, 0, ...``
``simulatePath`` 直接复现这条轨迹,每个字符只写入一个行缓冲区。最后连接全部行即可得到答案。这一版已经把二维排版压缩为“字符属于哪一行”,但仍需保存所有中间行,并维护会在端点翻转的方向状态。
周期行号
~~~~~~~~
往返轨迹会重复。设行数为 ``r``,从第 0 行到第 ``r - 1`` 行需要 ``r - 1`` 次移动,再回到第 0 行还需要 ``r - 1`` 次,因此一个完整周期包含:
.. math::
cycle = 2r - 2
个字符位置。
对于输入下标 ``index``,令 ``offset = index % cycle``。周期的前 ``r`` 个位置属于下降阶段,行号与偏移相同;其余位置属于上升阶段,行号关于周期末端对称:
.. math::
row =
\begin{cases}
offset, & offset < r \\
cycle - offset, & offset \ge r
\end{cases}
例如 ``r = 4`` 时,周期偏移 ``0, 1, 2, 3, 4, 5`` 对应行号 ``0, 1, 2, 3, 2, 1``。
``groupByCycle`` 用这个公式替换 ``row`` 和 ``direction`` 的逐步更新。方向翻转、端点判断和行号累加全部消失,每个字符可以直接计算所属行。不过代码仍然需要 ``rows`` 保存分组结果,最终再连接一次。
按行读取
~~~~~~~~
题目最终需要的是“先读第 0 行,再读第 1 行”,因此还可以跳过字符分组,直接计算每一行在原字符串中的下标。
固定一行 ``row``。每个周期的下降阶段都会在该行出现一次,对应下标为:
.. math::
vertical = row + k \cdot cycle
其中 ``k = 0, 1, 2, ...``。这些是代码中的 ``vertical`` 位置。
第一行和最后一行在每个周期中只出现一次。中间行还会在上升阶段出现一次,其周期内偏移为 ``cycle - row``。由当前下降位置可得:
.. math::
diagonal = vertical + cycle - 2 \cdot row
因此中间行的读取顺序是 ``vertical``、``diagonal``、下一个周期的 ``vertical``。对于 ``0 < row < numRows - 1``:
.. math::
vertical_k < diagonal_k < vertical_{k+1}
所以这正是该行从左到右的字符顺序。第一行和最后一行跳过 ``diagonal``,避免把下一周期位置或当前竖列位置重复加入。
索引推演
~~~~~~~~
以 ``s = "ABCDEFGHIJK"``、``numRows = 4`` 为例,``cycle = 6``:
* 第 0 行读取下标 ``0, 6``,得到 ``AG``;
* 第 1 行读取下标 ``1, 5, 7``,得到 ``BFH``;
* 第 2 行读取下标 ``2, 4, 8, 10``,得到 ``CEIK``;
* 第 3 行读取下标 ``3, 9``,得到 ``DJ``。
连接各行得到 ``AGBFHCEIKDJ``。最后一个周期不完整时,``vertical < length`` 和 ``diagonal < length`` 会自然忽略越界位置。
任意输入下标都能唯一写成 ``k * cycle + offset``。下降阶段位置由某一行的 ``vertical`` 公式读取,上升阶段位置由某一中间行的 ``diagonal`` 公式读取;两个转向点只属于第一行或最后一行。于是每个字符都被覆盖,并且不会重复。
代码演进
~~~~~~~~
``simulatePath`` 按输入顺序逐字符移动,保存 ``row``、``direction`` 和全部行缓冲区。它直接对应题目描述,但方向变化属于运行时状态。
``groupByCycle`` 发现行号序列具有固定周期,用 ``index % cycle`` 直接计算行号。方向状态、端点翻转和逐步移动被删除,仍保留行缓冲区以完成最终重排。
``readByCycle`` 进一步从“每个字符属于哪一行”改为“每一行包含哪些原始下标”。``rows``、逐字符行号计算和最后的行连接全部消失,代码直接按答案顺序向 ``result`` 追加字符。
三种实现时间复杂度相同,优化重点不是减少字符访问次数,而是逐步删除中间状态和临时存储。公开入口采用 ``readByCycle``。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 主要状态
* - 方向模拟
- ``O(n)``
- ``O(n)``
- 当前行、方向、行缓冲区
* - 周期分组
- ``O(n)``
- ``O(n)``
- 周期偏移、行缓冲区
* - 周期直读
- ``O(n)``
- ``O(1)``
- 当前行、竖列和斜线下标
三种方法都恰好处理 ``n`` 个输入字符。空间复杂度不计返回字符串:前两种方法的各行合计保存 ``n`` 个字符,周期直读只维护常数个整数。
边界处理
~~~~~~~~
* ``numRows = 1`` 时周期公式会得到 ``0``,必须在计算周期前直接返回原字符串;
* ``numRows >= s.size()`` 时每个字符至多占一行,按行读取顺序与输入顺序相同;
* ``numRows = 2`` 时没有中间行,算法只读取竖列位置,不会追加斜线字符;
* 最后一个周期可以不完整,所有候选下标都经过长度检查;
* 返回结果预留 ``s.size()`` 容量,避免追加字符时反复扩容。