13

来自SPOJ 上的 STRSEQ：

给定一串数字，找到在给定字符串中不作为子序列出现的最小非负整数。

我尝试了一种方法，在该方法中我逐渐从 0 中找到数字。但我的方法是O(answer * length of the string). 有O(length of string)解决这个问题的方法吗？

例子：

输入

  • 9876543210
  • 21698921085321984125
  • 12345678901

输出

  • 11
  • 7
  • 22
4

1 回答 1

8

该算法所需的数据结构：

  • 位集数组，每个输入字符串元素一个位集（最后还有一个空位集），每个数字一位（每个位集的大小为 10）
  • 10 组位置 - 每个数字（可选）
  • 计数器（计算答案中的数字）

算法：

  1. 向后扫描输入字符串，将当前位置压入该位置的数字对应的堆栈，从前一个位置复制bitset并设置当前位置的数字对应的位。当当前位集中的所有位都被设置时，递增计数器并清除位集。
  2. 如果计数器仍然为零，则获取当前位集中的最低有效位，并使用与该位对应的单个数字来构造结果数。
  3. 如果唯一未设置的位是“零”，则结果数字被构造为“10”，然后是步骤 4 的结果（其中初始数字“0”是预先确定的）。
  4. 获取当前bitset中最低有效0位（但第一次执行此步骤时，忽略“0”对应的位），将其作为结果的下一位，弹出该位对应的堆栈（直到你得到位置不小于当前位置），并将当前位置设置为此堆栈中的索引加一。获取当前位置对应的bitset并重复第4步。此步骤应执行“counter+1”次或直到尝试弹出空堆栈。

替代算法：

另一种选择是将大多数计算从第 4 步移到第 1 步。在这种情况下，我们需要更简单的数据结构，而不是 bitset 数组和 10 个堆栈。

解释和例子：

该算法的步骤 1 确定包含任何一位数作为子序列的最短后缀。然后它找到与此后缀相邻且还包含任何一位数的最短子字符串。它们一起给出包含任何两位数的最短后缀。对于 3 位、4 位后缀等，继续此过程。此外，此预处理步骤确定哪些数字可以写入这些 n 位数字的左侧，以便相应的子序列存在于输入字符串的某些后缀中（此信息包含在位集中）。

例如，对于输入字符串，12345678901此步骤确定从索引“1”开始的后缀包含任何可能的单位数。它还以以下方式填充位集：

index: bitset:
10     0000000010
9      0000000011
8      1000000011
7      1100000011
6      1110000011
5      1111000011
4      1111100011
3      1111110011
2      1111111011
1      0000000000
0      0000000010

步骤 2,3 处理一些极端情况。

第 4 步首先检查位置“0”处的位集，以找到可能的最小起始数字。在我们的示例中，设置了位“1”，这意味着我们不能以“1”开始我们的 2 位数字（所有这些数字都已经在字符串中）。我们也不能以“0”开头。下一个未设置位是“2”，所以我们将以“2”开始数字。

我们可以使用相应的堆栈或只是顺序搜索字符串以到达第一个数字“2”的位置。我们号码的剩余数字应该在数字“2”之后的后缀中。这个后缀的起始位置的位组是“1111111011”，这意味着这个后缀中唯一未使用的数字是“2”。我们应该在这里停下来，因为“counter+1”是 2，我们刚刚用完了第 4 步的 2 次迭代。所以答案是“22”。

这是其他时间复杂度较低的算法O(answer + length of the string)。

对于每个数字（从 0 到 9）准备一个索引数组，其中每个索引指向给定位置或右侧最近数字的出现。例如：

For string     216989210...
and digit "1": 11777777...

这可以通过向后扫描输入数组来实现，一旦我们看到适当的数字，就开始将其索引写入索引数组。对于上面的示例，这意味着我们在位置 7 处看到最右边的数字“1”，并用 7 填充索引数组，直到在索引 1 处再次出现数字“1”。然后我们用这个索引填充剩余的位置。

现在我们可以轻松地将 OP 中提到的算法的复杂度从 降低O(answer * length of the string)到O(answer + length of the string). 只需按照其中一个索引数组提供的链接来获取当前数字中下一个数字的最近位置。

例如，我们可以先尝试 61 个非负数，然后对于数字“61”，我们在索引数组的第一个位置检查“6”以找到索引“2”（这实际上没有必要，因为这个索引已经找到在处理“60”时），然后我们在下一个位置（2+1）检查索引数组中的“1”以找到索引“7”。这意味着“61”出现在给定的字符串中，我们可以继续使用“62”......

于 2013-10-29T14:24:51.710 回答