gpt4 book ai didi

计算数值范围内子串的算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:01:16 26 4
gpt4 key购买 nike

我正在寻找一种可用于解决此问题的快速算法:给出 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] 范围内的一个子串的计数,我们仍然不能将这个计数与列表中其他子串的计数相加,因为一个数字可以包含多个子串,不应该是数了不止一次。

有什么解决问题并获得所需数量的想法吗?

最佳答案

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

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

  2. 如果数字的个数是 k,你必须说找到包含子字符串 234 的数字,然后选择你将放置该子字符串的位置(以 k-2 种方式),然后找到所有的排列数可能的剩余数字(我认为有 10 ^ (k-3) 种方式)。当然,您必须对前导零等打折。

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

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

关于计算数值范围内子串的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19079947/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com