计算字典顺序小于特定数字的正整数的数量

Question

假设我有一个数字

num

，我想计算

[1, n]

范围内的正整数的数量，这些正整数按字典顺序小于

num

，并且

n

是某个任意大整数。如果转换后的字符串

x

按字典顺序小于转换后的字符串

y

，则数字

str(x)

按字典顺序小于数字

str(y)

。我想有效地做到这一点，因为

n

可能很大（例如

10^9

）。我的想法是使用数字动态规划。

基本上我的想法是，

[1,n]

范围内的每个数字都可以表示为一串

len(str(n))

槽。在每个槽中，上限要么是

num

最后位置的数字（这是针对我们选择尾随零的情况），要么是

n

最后位置的数字。这是因为，如果前一个数字已经小于

num

中的相应数字，那么我们可以自由选择

n

中相应数字之前的任何数字。下面是我的 Python 代码，尝试执行此操作

from functools import cache

def count(num, n):
    num = str(num)
    n = str(n)
    max_length = len(n)
    @cache
    def dp(indx, compare_indx, tight, has_number):
        if indx == max_length:
           return int(has_number)
        ans = 0
        upper_bound = int(num[compare_indx]) if tight else int(n[indx])
        for digit in range(upper_bound + 1):
            if digit == 0 and not has_number:
               ans += dp(indx + 1, compare_indx, tight and (digit == upper_bound), False)
            else:
               ans += dp(indx + 1, min(compare_indx + 1, len(num) - 1), tight and (digit == upper_bound), True)
        return ans
    return dp(0, 0, True, False)

但是，

count(7, 13)

输出的35是不正确的，因为

[1, 13]

的字典顺序是[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]所以

 count(7, 13)

应该是

10

。有人可以帮我吗？

Answer 1

我无法理解你解释中的逻辑，但这不需要动态编程。

本质上，您希望对整数的每个可能的width进行单独的计数。例如，当调用

count(7, 13)

时，您想要计数：

• 一位数的整数：[1, 6] = 6 个整数
• 两位数的整数：[10, 13] = 4 个整数

结果是总和：6 + 4 = 10

以

count(86, 130)

作为另一个例子，其中第一个参数有多个数字：

• 一位数的整数：[1, 8] = 8 个整数（注意包括 8）
• 两位数的整数：[10, 85] = 76 个整数（注意不包括 86）
• 三位数整数：[100, 130] = 31 个整数

总计：115

因此，在范围的高端必须要小心：当它是第一个参数的正确前缀时，它应该是 included，如果不是，它应该是 excluded。当然，对于最后一组（具有最大位数），您应该注意不要超过第二个参数的值。

以下是编写该逻辑的方法：

def count(num, n):
    strnum = str(num)
    lennum = len(strnum)
    max_length = len(str(n))
    strnum += "0" * (max_length - lennum)  # pad with zeroes at the right

    count = 0
    low = 1
    for width in range(1, max_length + 1):
        high = int(strnum[:width])
        addone = width < lennum and n >= high
        count += min(high, n + 1) - low + addone
        low *= 10
        
    return count