C++ 中的看数数序列

在本文中，我们将讨论 Look-and-Say 序列，包括其不同方法、示例、时间复杂度和空间复杂度。

什么是 Look-and-Say 序列？

Look-and-say 序列（也称为“数数说序列”）是一个整数序列，其中初始项之后的每一项都使用一系列连续数字来描述前一项。该模式涉及读取当前项的数字，计算每个数字连续出现的次数，然后说出该数字后面的计数。重复此过程以生成后续的每一项。

示例：1, 11, 21, 1211, 111221, 312211, 13112221,…

Look-and-Say 序列的结构

• 在 Look-and-Say 序列中，“1”是第一项。
• 由于第一个“1”只有一个，因此通过将第一个项解释为“一个 1”来生成第二项“11”。
• 将第二项读作“两个 1”，生成第三项“21”。
• “1211”是第四项，它是通过将第三项解释为“一个 2，一个 1”而产生的。
• 通过读取前一项的计数和数字来创建下一项，并以此类推。

方法 1：简单方法

示例

让我们以一个例子来说明 C++ 中的 Look-and-Say 序列。

输出

Enter the term number for the Look-and-Say sequence: 5
The 5th term in the Look-and-Say sequence is: 111221   

复杂度分析

• 时间复杂度：O(n^2)
• 辅助空间： O(1)

说明

此 C++ 程序 使用用户输入生成 Look-and-Say 序列的第 N 个短语。通过从第三项迭代到第 N 项，函数 generateLookAndSay(int n) 通过读取和计数前面的数字来构建每一项。为了构建下一项，内部循环计算每个数字的出现次数，而外部循环则遍历每一项。一旦构建了所需的项，程序就会输出它。

方法 2：使用 STL

在 “Look-and-Say” 序列中，目标是通过利用 unordered_map 来快速跟踪连续数字的数量，同时创建后续序列。此方法迭代当前序列，计算每个数字出现的次数，然后使用计数构建后续序列。

示例

让我们再举一个使用 STL 在 C++ 中说明 Look-and-Say 序列的例子。

输出

Enter the value of num: 5
The 5-th term in the Count and Say sequence is: 111221   

说明

此 C++ 程序生成 Look-and-Say 序列的第 n 个短语。首先，generateLookAndSay 方法处理 n == 1 和 n == 2 的基本情况，分别返回“1”和“11”。对于较大的 n 值，它通过检查连续相同的数字集、计算它们的出现次数，然后将计数和数字附加起来以创建后续项来迭代地构建序列，从“11”开始。使用一个名为 currentTerm 的字符串来存储当前序列，一个名为 nextTerm 的字符串来构建后续序列，循环继续直到达到目标项。在读取整数输入 n 后，main 函数运行 generateLookAndSay(n) 并输出其结果。

方法 3：使用动态规划

为了避免重复计算并提高效率，Look-and-Say 序列是使用动态规划生成的，它通过将所有中间行存储在字符串向量中来简化过程。使用此方法，每一项都从前一项派生，通过计算每个字符的连续出现次数，从而利用序列的自引用特性。如果已经计算出第 i 行，则可以通过检查第 i 行并计算连续字符来构建第 i+1 行。此方法通过避免对早期行进行重复计算来降低时间复杂度。

按照以下步骤实现上述方法

1. 要存储中间结果，请初始化一个字符串向量。作为 Look-and-Say 模式的第一行，将向量的第一个元素设置为“1”。
2. 使用 for 循环生成 Look-and-Say 模式的每一行，从第二行（i = 1）到第 n 行（i < n）。
3. 为每个循环创建一个空字符串 temporary，以保存下一个 Look-and-Say 模式行。
4. 模式的当前行存储在向量的 (i-1) 个元素中，可以使用 for 循环进行迭代。
5. 在循环内使用 while 循环来计算同一字符在当前行中出现的次数。
6. 当 while 循环结束时，将当前字符和连续出现的次数添加到 temporary 字符串。
7. 内部循环完成后，将 temporary 字符串作为第 i 个元素添加到向量中，这表示 Look-and-Say 模式的下一行。
8. 外部循环完成后，返回向量的第 n 个元素，其中包含 Look-and-Say 序列的第 n 行。

示例

让我们以一个例子来说明 C++ 中的 Look-and-Say 序列。

输出

Enter the term number for the Look-and-Say sequence: 5
The 5th term in the Look-and-Say sequence is: 111221   

复杂度分析

• 时间复杂度： O(n*m)
• 空间复杂度： O(n*m)

说明

此 C++ 程序生成用户指定单词之前的 Look-and-Say 序列。为了保存中间短语，函数 generateLookAndSaySequence 初始化一个 vector 字符串，第一个术语为“1”。对于每个术语，它计算前一个术语中连续相同字符的计数，并将计数和字符相加以创建当前术语。继续这样做直到计算出所需的术语。main 函数在从用户那里接收术语号后调用该函数，并返回序列中匹配的术语。

方法 4：使用堆栈

在此方法中，使用堆栈计算 Look-and-Say 序列的连续数字出现次数。当前，如果数字为空，则将其推入堆栈。如果当前数字与堆栈顶部的数字匹配，则将当前数字也推入堆栈以维护序列。如果当前数字不同，则将堆栈顶部的数字和堆栈的长度（代表连续数字的计数）合并到一个 字符串 中（计数 + 数字）。清空堆栈后，将当前数字推入堆栈以便继续处理。为了构建序列，此技术有效地跟踪连续数字集。

示例

让我们再举一个使用 C++ 说明 Look-and-Say 序列的例子。

输出

Enter the term number for the Look-and-Say sequence: 5
The 5th term in the Look-and-Say sequence is:111221   

复杂度分析

• 时间复杂度： O(kn)
• 辅助空间： O(kn)

说明

此 C++ 程序递归地生成 Look-and-Say 序列。函数 generateLookAndSay 通过检查前一项，使用堆栈计算连续相同的数字，然后通过附加计数和数字来构造结果来计算每一项。main 函数在从用户那里接收项号后输出匹配的序列项。