algorithm - 查找范围 [L, R] 中其二进制表示包含给定模式的所有数字

Question

令L 和R 代表两个正整数，那么我们需要找出[L,R] 中的所有数字，即L 和R，包括L 和R，它们的二进制表示形式为101。例如，让 L = 3 和 R = 20，那么 5(101) 和 13(1101) 就是两个这样的数字。

约束

1 <= L <= R <= 10^18

我的做法——

一种明显的方法是从 L 遍历到 R 并获得每个数字的二进制表示并检查它是否包含 101，但考虑到约束，这将花费太多时间。另一种方法可以使用数字动态规划，更正式地说，如果我们可以计算一个函数 F(x)，其中 x 是一个非负整数，F(x) 表示小于或等于 x 的 +ve 整数个数，满足问题中给出的条件（即它的二进制表示包含 101），如果我们假设 F(0) = 0，那么问题简单地归结为 F(R) - F(L - 1)。我已经解决了一些数字 DP 问题，但无法制定这个问题，或者可能有其他方法？

标签： algorithmdynamic-programming

Answer 1

最简单的解决方案可能是将您的号码分成两部分 - 给定的模式和休息位。假设最大的数字是 5 位长，给定的模式是 3 - '101'，所以剩下的部分是 2 位。然后枚举 2 位的所有变体并使用它们创建数字并与所有变体的目标模式连接 -

00 gives you '00 101' '0 101 0' '101 00'
01 gives you '01 101' '0 101 0' '101 01'
10 gives you '10 101' '1 101 0' '101 10'
11 gives you '11 101' '1 101 1' '101 11'

那么您只需消除重复项并限制范围。