2

我正在寻找一种可用于解决此问题的快速算法：给出 A 和 B 整数（在 [0,10^18] 范围内），并给出 N (N<=1000) 个数字子字符串的列表；目标是计算范围 [A,B] 中包含任何 N 个子字符串的所有数字。我们总是 A<=B 并且数字子字符串也是 [0,10^18] 范围内的整数。

示例 1：如果 A=10，B=22，并给出 N=2 个子串={1,10}；计数为 = 11；数数：10->19 和 21。

例2：如果A=175，B=201，给N=3个子串={55,0,200}；计数为 = 4；数数：180、190、200 和 201。

直接的方法是依次分析 [A,B] 范围内的每个整数，但这不是解决方案，因为范围可能很大（直到 10^18 个整数）。

我为降低问题复杂性所做的第一件事是从 N 个子字符串的原始列表中删除一些无用的子字符串，这样“没有子字符串包含在另一个子字符串中”。例如：{1,10} 变为 {1}，{55,0,200} 变为 {55,0}。这不会改变最终计数。

接下来，即使假设我们可以得到 [A,B] 范围内的一个子字符串的计数，我们仍然不能将此计数与列表中其他子字符串的计数相加，因为一个数字可以包含许多子字符串，并且计数不应超过一次。

有什么想法可以解决问题并获得想要的数量吗？

4

1 回答 1

1

我认为这更像是一个组合问题。

  1. 计算 A 和 B 之间数字的可能位数。例如 2 和 2000 之间，位数可以是 1、2、3 或 4。对于 1 位，您需要计算大于 2 和 4 位的数字，你必须计算小于 2000 的数字，即从 1 开始。

  2. 如果位数是 k，并且您必须说找到包含子字符串 234 的数字，然后选择放置该子字符串的位置（以 k-2 种方式），然后找到所有可能剩余数字的排列数（i以 10 ^ (k-3) 种方式思考）。当然，您必须为前导零等打折。

  3. 对所有子字符串重复此操作。

  4. 现在您必须减去包含多个子字符串的那些。对所有子字符串组合重复上述过程，并从计算值中减去它。

于 2013-09-29T16:29:54.653 回答