主页 / coding / 问题 / 79010903
Accepted
S10000
Asked: 2024-09-22 12:55:03 +0800 CST

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

  • 772

假设我有一个数字num，我想计算范围内[1, n]按字典顺序小于和的正整数的数量num，并且n是某个任意大整数。如果转换后的字符串按字典顺序小于转换后的字符串，则数字按字典顺序x小于数字。我想高效地做到这一点，因为可能很大（例如）。我的想法是使用数字动态规划。ystr(x)str(y)n10^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。有人能帮我吗？

python

1 个回答

  1. Best Answer

    我无法理解你解释的逻辑，但这不需要动态规划。

    本质上，您需要对整数的每个可能宽度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

    因此，在范围的高端必须小心谨慎：当它是第一个参数的正确前缀时，应将其包括在内，如果不是，则应将其排除。当然，对于最后一组（具有最多位数），您应该注意不要超过第二个参数的值。

    您可以按照以下方式编写该逻辑：

    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
    • 1

相关问题