0038. Count and Say
===================
题目信息
--------
:题号: 0038. 外观数列
:难度: Medium
:主题: 字符串、游程编码、递推
:原题: `LeetCode 0038 `_
:重点: 从保存完整序列,推导到按最大连续段生成下一项,并只保留当前字符串
题目重述
--------
定义字符串序列 ``countAndSay``:
* 第 ``1`` 项为 ``"1"``;
* 第 ``n`` 项通过从左到右描述第 ``n-1`` 项得到。
描述一个字符串时,把相邻且相同的字符划分为最大连续段。对于每一段,依次写出“该段的字符数量”和“该字符”。
给定整数 ``n``,返回序列的第 ``n`` 项。
这里处理的是字符串而不是整数运算。例如 ``"21"`` 表示“一个 ``2``、一个 ``1``”,因此下一项为
``"1211"``。``n`` 位于 ``[1, 30]``。
自建示例
--------
* ``n = 1`` 时返回 ``"1"``,这是序列定义给出的初始项;
* ``n = 4`` 时返回 ``"1211"``,因为第三项 ``"21"`` 包含一个 ``2`` 和一个 ``1``;
* ``n = 6`` 时返回 ``"312211"``,因为第五项 ``"111221"`` 被划分为 ``"111"``、``"22"``、
``"1"``,分别描述为 ``"31"``、``"22"``、``"11"``;
* 描述 ``"1211"`` 时,开头的 ``'1'`` 与末尾两个 ``'1'`` 不能合并,中间的 ``'2'`` 将它们分成
不同连续段。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
std::string describe(const std::string& current) {
std::string next;
next.reserve(current.size() * 2);
int start = 0;
while (start < static_cast(current.size())) {
int end = start + 1;
while (end < static_cast(current.size()) &&
current[end] == current[start]) {
++end;
}
next += std::to_string(end - start);
next.push_back(current[start]);
start = end;
}
return next;
}
std::string buildWholeSequence(int n) {
std::vector sequence(n);
sequence[0] = "1";
for (int index = 1; index < n; ++index) {
sequence[index] = describe(sequence[index - 1]);
}
return sequence.back();
}
std::string rollingGeneration(int n) {
std::string current = "1";
for (int index = 2; index <= n; ++index) {
current = describe(current);
}
return current;
}
public:
std::string countAndSay(int n) {
return rollingGeneration(n);
}
};
题解
----
完整序列基线
~~~~~~~~~~~~
按照定义,可以保存从第一项到第 ``n`` 项的全部字符串:
.. code-block:: text
sequence[0] = "1"
sequence[i] = describe(sequence[i - 1])
``buildWholeSequence`` 直接实现这条递推,因此不会跳过任何中间项。它的问题在于,第 ``i`` 项生成完成后,后续只会
读取这一项;更早的字符串已经失去用途,继续保存它们只是额外空间开销。
描述操作的局部性
~~~~~~~~~~~~~~~~
下一项并不统计整个字符串中每种字符的总数,而是依次描述最大连续相同字符段。例如:
.. code-block:: text
"1211" = "1" | "2" | "11"
三段分别生成 ``"11"``、``"12"`` 和 ``"21"``,合并得到 ``"111221"``。开头与末尾的 ``'1'``
虽然字符相同,却被 ``'2'`` 分隔,不能合并计数。
这说明生成下一项只需从左到右确定连续段的边界,无需建立全局字符频次表,也无需回看已经描述的部分。
最大连续段
~~~~~~~~~~
令 ``start`` 指向尚未处理部分的首字符,``end`` 从 ``start + 1`` 开始向右移动。只要
``current[end] == current[start]``,当前字符仍属于同一段;遇到不同字符或到达末尾时停止。
停止后,半开区间 ``[start, end)`` 满足:
* 区间内字符全部等于 ``current[start]``;
* 区间长度为 ``end - start``;
* ``end`` 已越界,或 ``current[end]`` 与段字符不同。
因此它正是从 ``start`` 开始的最大连续段。把 ``end - start`` 和段字符写入 ``next`` 后,令
``start = end``,下一轮从第一个未处理字符继续。
每轮至少处理一个字符,且新区间从上一段末尾开始,所以所有字符恰好被覆盖一次。每一段的结束位置又由第一个不同
字符唯一决定,因此生成结果也唯一。
单轮生成不变量
~~~~~~~~~~~~~~
每轮开始时保持:
* ``current[0..start-1]`` 已被完整描述;
* ``next`` 恰好等于这段已处理前缀的描述结果;
* ``current[start..]`` 尚未处理。
找到 ``[start, end)`` 后,追加该段的数量和字符,便得到前缀 ``current[0..end-1]`` 的完整描述;再令
``start = end``,不变量继续成立。
当 ``start == current.size()`` 时,整个输入都已按顺序分段并描述,``next`` 就是唯一的下一项。使用
``std::to_string(end - start)``,而不是假设段长度只有一位,也使 ``describe`` 对任意连续段长度都成立。
状态演化
~~~~~~~~
描述 ``"111221"`` 时,各轮状态为:
.. list-table::
:header-rows: 1
* - ``start``
- ``end``
- 连续段
- 写入片段
- 累计结果
* - 0
- 3
- ``"111"``
- ``"31"``
- ``"31"``
* - 3
- 5
- ``"22"``
- ``"22"``
- ``"3122"``
* - 5
- 6
- ``"1"``
- ``"11"``
- ``"312211"``
滚动递推
~~~~~~~~
序列只有一阶依赖:
.. math::
term_i = describe(term_{i-1})
生成新字符串后,旧项不再参与后续计算。因此 ``rollingGeneration`` 只维护 ``current``,每轮用
``describe(current)`` 的结果替换它。
第 ``i`` 轮开始时,``current`` 与完整序列方法中的第 ``i-1`` 项相同;应用同一个 ``describe`` 后,新值便等于
第 ``i`` 项。逐轮保持这一关系,最终返回的正是第 ``n`` 项。
``n = 1`` 时循环不会执行,直接返回初始项 ``"1"``。单字符输入和末尾连续段都由 ``end`` 的越界条件正常结束,
无需额外哨兵。
方法演进
~~~~~~~~
``buildWholeSequence`` 保存全部历史项,完整体现递推定义,但保留了后续不再使用的字符串。
``describe`` 把一轮转换缩减为最大连续段扫描,每个输入字符只属于一个分组。``rollingGeneration`` 再利用一阶依赖,
删除历史数组,只保留当前项和正在构造的下一项。公开入口采用该滚动方法。
复杂度分析
~~~~~~~~~~
设第 ``i`` 项长度为 ``L_i``。生成第 ``i+1`` 项时,需要读取 ``L_i`` 个字符,并写出长度为 ``L_{i+1}`` 的结果,
因此生成第 ``n`` 项的总时间为:
.. math::
O\left(\sum_{i=1}^{n-1}(L_i+L_{i+1})\right)
= O\left(\sum_{i=1}^{n}L_i\right)
``buildWholeSequence`` 保存全部项,额外空间为 ``O(\sum L_i)``。滚动方法在一轮转换中只同时持有当前项与下一项,
工作空间为 ``O(L_{n-1}+L_n)``,与最大单项长度同阶。