按顺序计算包含数字 2018 的最多 n 个整数

Question

给定一个介于 0 和 10,0000,0000 之间的整数 n，计算包含数字的小于 n 的整数的个数[2,0,1,8] 顺序。

例如数字 9,230,414,587 应该被计算在内，因为删除数字 [9,3,4,4,5,7] 剩下 [2,0,1,8]。

示例输入和输出：

n = 2018      ->  count =     1
n = 20182018  ->  count = 92237

我一般的想法是：n的最大长度是10，最坏的情况是我们要在[2,0,1,8]中插入6位并删除重复项和大于 n.

的数字

Answer 1

这其实是一个比较小的问题集。如果数字大得多，我会选择使用优化技术来生成所有符合您标准的数字（那些包含该顺序的数字）而不是生成 all 可能的数字和检查每一项以确保其符合标准。

但是，蛮力方法可以在大约十秒内完成您的 20182018 变体，并在不到八分钟的时间内完成整个 1,000,000,000 范围。

因此，除非您需要比这更快的速度，否则您可能会发现蛮力方法绰绰有余：

import re

num = 1000000000 # or 20182018 or something else.

lookfor = re.compile("2.*0.*1.*8")
count = 0
for i in range(num + 1):
    if lookfor.search(str(i)) is not None:
        count += 1
        #print(count, i) # For checking.
print(count)

Answer 2

我没有看到任何自己尝试解决的问题，所以我只提供线索：

您有一个包含数字序列 2,0,1,8 的 9 位数字（小数可能表示为 000002018）。
将它们命名为 'good' 个。
让从右到左表示从 1 到 9 的数字位：

     number     532705183
digits     5  3  2  7  0  5  1  8  3
index      9  8  7  6  5  4  3  2  1

最左边的'2'位可以占4到9位。第k位第一个2的好数有多少？让函数 F2(l, k) 为好数字的数量，其中 2 指的是数字 2，l 是数字长度，k 是最左边数字的位置。

 .   .   .   .  2   .   .   .   .
                ^ 
                | 
 left part      k     right part should contain 0 1 8 sequence
 without 2's

 F2(9, k) = 9^(9-k) * Sum(F0(k-1, j) for j=1..k-1)

对于所有可能的 k，好号码的总数是 F2(9, k) 的总和。

GoodCount = Sum(F2(9, k) for k=4..9)

解释：

左边有9-k个地方。我们可以把除 2 之外的任何数字放在那里，所以有 9^(9-k) 个可能的左边部分。

现在我们可以将 0 放在正确的部分并计算 018 个子序列的可能变体。 F0(...) 当然取决于 F1(...) 而 F1 将取决于 F8(...) 以获得较短的数字。

因此，请逐步填写 F8, F0, F1 值的表格，最后计算数字 2 的结果。

包含子序列 1 8 和 k = 第一个“1”的位置的 4 位数字的手工示例：
k=2: 有 81 个数 xx18
k=3：有种类数 x1x8 和 x18x
有 9 个子数 x8，10 个子数 8x，所以 (10+9)*9=171
k=4: 有 kind
个数 1xx8(9*9=81这样的数),
1x8x (9*10=90 个数字),
18xx（100 个号码），
所以 81+90+100=271
总体：81+171+271=523

按顺序计算包含数字 2018 的最多 n 个整数

Count integers up to n that contain the digits 2018 in order

algorithm

integer

digits

subsequence