按顺序计算包含数字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

我没有看到任何自己的尝试解决，所以我只给出线索：

您有包含数字序列2,0,1,8的9位数字（小数字可能表示为000002018）。 将它们命名为“好”的。 让我们从右到左表示从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的地方。我们可以在那里放任何数字，但是有剩下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：有很多种类 1xx8（9 * 9 = 81这样的数字）， 1x8x（9 * 10 = 90个数字）， 18xx（100个数字）， 所以81 + 90 + 100 = 271 总体而言：81 + 171 + 271 = 523

Answer 2

这实际上是一个相对较小的问题集。如果数字更大，我会选择使用优化技术来生成符合条件的所有数字（包含该顺序中的数字的数字），而不是生成所有可能的数字并检查每个数字以确保其符合标准。

然而，蛮力方法在大约十秒内完成你的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)