c++ - 查找多少数字满足范围内的约束

Question

给定2个整数l和r，计算[l，r]中有多少个数字满足这些约束

1)该数字应被7整除

2)该数字至少包含三位数7

3)该数字包含的数字7比数字4多

777，774746满足这些约束，而7771，77，747474则不符合。

使用蛮力可以很容易地找到答案，但是当范围很大时，可能要花费很多时间。

我认为动态编程可以帮助解决此问题，但我想不出解决方案

有人可以给我一些指导吗？

Answer 1

从原始的暴力版本中获取:

Iterate with i over numbers between [l,r]
    Use modulo to check if i is divisible by 7
    Use modulo and division to get counts of digits in i
    digit_count(7) >= 3
    digit_count(7) > digit_count(4)

这是我想出的一些想法...
1.仅使用7的倍数，隐式地满足第一个条件:
这真的很简单。我们可以改进它，使其仅使用 i可除的 7。如果我给您一个数字 x并要求您生成可被 n整除的数字，直到达到 y，那么您最好这样做:

for (auto i = x + x % n; i < y; i += n)

因此，对于 7和 l之间 r的倍数的情况，您需要做的就是运行 for (auto i = l + l % 7; i < r; i += 7)循环，这会将您的暴力版本提高7倍。
2.记住数字计数
无需执行大量除法和模运算即可获得所经过的每个数字的位数。由于您知道增加多少，因此您也知道哪些数字变为什么数字。这样，您只需要将起始号码(例如 l % 7 + l)分割成数字即可。
现在，我们要存储的不是数字计数，而是实际上非常类似于BCD的东西-一个数字数组，代表我们当前使用的数字。然后，您将得到类似于 std::vector<int>的表达式，该表达式表示数字 [7, 7, 2, 4, 5, 7]的 772457数组。现在，您需要做的就是每次增加循环计数器(即 [7, 7, 2, 4, 5, 7] + 6 = [7, 7, 2, 4, 6, 3])时在数组内使用BCD算法。
我们需要存储的另一件事是两个 int s- sevens和 fours。在初始化阶段，一旦将第一个数字“分解”为数组，就可以遍历该序列，并为每个 sevens递增 7，为每个 fours递增 4。而且您只需保持此数字为最新:每次更新数组时，您要为带走的每个 fours减少 4，并为在数组中创建的每个 4递增。与 7编号相同。然后，您可以比较 sevens> = 3 && sevens> fours并快速知道结果。
有趣的是，这在理论上并没有给您带来任何复杂性上的改进，并且可能无法正常工作，但是我怀疑它应该...有很多代码，因此我将不提供它。您可能最终会倒置BCD数组，或者从迭代范围的 r末尾开始工作，因此不需要调整数组的大小。也许您可以提出更多改进和调整。但是，我强烈怀疑这种解决方案可以使渐近简化。
3.更多的想法
现在，这根本不是动态编程。还是吗？如果您考虑一下，我有一种直觉，那就是将数字数组作为BCD的想法现在可以转换为一个问题，您需要查找包含给定组合的排列。您可以从中制作图表并进行搜索。这就是您要动态发展的地方。但是，我担心这会花更长的时间...
但是我已经对此有了第一个怀疑，那就是将除数除以7，然后将其应用于图中找到的所有数字(该图的性质仅支持准则2和3，并得出包含组合)。因此，最后，归结为这些范围内算法应支持的范围大小和满足第一个条件的数字之比以及满足第二个和第三个条件的数字之比。
编辑:
从那以后，我发现计算符合条件的数字计数的想法是错误的。一些小的比较表:

|   range    |      numbers f/ c2     | c2_groups | c2_total | c1_total |
|   0 - 1k   |         777            |         1 |        1 |     ~143 |
|  1k - 10k  | _777, 7_77, 77_7, 777_ |         4 |       40 |    ~1286 |
| 10k - 100k |   __777, _7_77, ...    |        10 |     1000 |   ~12857 |

其中 numbers f/ c2是满足条件2的数字， c2_groups是该数字中任意数字和7的可能组合的计数， cx_total是该范围内满足条件x的数字的总数。
有了这一点，是否首先根据数字位数标准进行过滤是否有效就显得很成问题。我想这将需要进行一些数学分析，而所需时间将比实现解决方案还要长。
空间搜索
具有与方法2等效的状态，可以在数字范围内执行DFS。而不是增加7，它会存储一个数字 vector ，并根据可移动的偏移量(例如，

increment [1, 0, 7, _] -> [1, 0, 8, _]
                 ^               ^

这就是算法将在核心循环中执行的操作。然后，您可以检查当前的数字 vector 设置是否可以满足条件-例如 [0, p, _, _]可以实现它们，而 [0, 0, p, _]无法实现( p是所指向的元素)。这样，您将不断增加最高位数，而跳过许多数字。每当有可能满足要求时，您将增加偏移量并重复该过程:

push [7, 7, _, _] -> [7, 7, 0, _]
         ^                  ^

一旦达到最低有效数字位置，您还将开始检查每个候选人的7分频。您可以尝试将数字转换为 int并使用模或使用某种除数算法(这些使用数字，这是令人愉快的巧合)。
这样，您将获得一个通过所有条件的数字并将其返回。现在，您可能会遇到耗尽给定数字范围内所有数字的情况。在这种情况下，您需要将偏移量移回一个位置:

pop [7, 7, 7, 9] -> [7, 7, 7, _]
              ^            ^

现在，您将使用 increment，看到 [7, 7, 8, _]可以满足条件，并且再次满足 push。然后遍历 0， 1， 2，...序列，直到您进入 7为止，看到 7787可以使用第二和第三条件都可以，但是无法通过 7进行除法。等等...
您还需要检查您是否尚未超过 r限制。我想可以通过将 r也拆分为数字并与最高有效数字进行比较来以一种理智的方式完成。
鉴于我们没有为此进行数学分析，并且仍然要处理很多数字(尤其是在7是最低有效数字的情况下)，我想知道这是否真的值得实现。但这也不是什么 super 复杂的东西。祝好运!