统计强大整数的数目

难度: Hard

给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个正整数。

如果一个正整数 x 末尾部分是 s （换句话说，s 是 x 的后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。

请你返回区间 [start..finish] 内强大整数的 总数目 。

如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。

示例 1：

输入：start = 1, finish = 6000, limit = 4, s = "124"
输出：5
解释：区间 [1..6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。
这个区间内总共只有这 5 个强大整数。

示例 2：

输入：start = 15, finish = 215, limit = 6, s = "10"
输出：2
解释：区间 [15..215] 内的强大整数为 110 和 210 。这些整数的各个数位都 <= 6 且 "10" 是它们的后缀。
这个区间总共只有这 2 个强大整数。

示例 3：

输入：start = 1000, finish = 2000, limit = 4, s = "3000"
输出：0
解释：区间 [1000..2000] 内的整数都小于 3000 ，所以 "3000" 不可能是这个区间内任何整数的后缀。

提示：

1 <= start <= finish <= 10¹⁵
1 <= limit <= 9
1 <= s.length <= floor(log₁₀(finish)) + 1
s 数位中每个数字都小于等于 limit 。
s 不包含任何前导 0 。

Submission

运行时间: 32 ms

内存: 16.8 MB

class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        def count(num: int) -> int:
            res, num = 0, str(num)
            power = pow(limit, len(num)-l)
            for c in num[:-l]:
                if int(c) >= limit:
                    res += power
                    return res
                power //= limit
                res += int(c)*power
            res += (int(num[-l:]) >= s)
            return res

        l, s, limit = len(s), int(s), limit+1
        return count(finish) - count(start-1)

Explain

题解首先定义了一个内部函数 count(num)，用于计算从 1 到 num 范围内所有强大整数的数量。该函数通过将数字 num 转换为字符串，并从高位到低位逐位检查，确定每位数字是否满足小于等于 limit 的条件。对于每一位，如果大于 limit，后续的所有数字组合均不符合条件，直接返回当前计数结果；如果小于等于 limit，则继续检查下一位。该函数的核心在于逐位确定数字的范围，特别是对于最后的 l 位（s 的长度），需要检查是否恰好等于 s 来决定是否增加计数。整体解法通过计算 count(finish) - count(start-1) 来得到区间 [start, finish] 内强大整数的数量，利用了前缀和的思想。

时间复杂度: O(m) where m is the number of digits in the largest number between start and finish.

空间复杂度: O(1)

class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        def count(num: int) -> int:
            # 初始化结果变量和将数字转为字符串
            res, num = 0, str(num)
            # 计算权重，由高位到低位递减
            power = pow(limit, len(num)-l)
            # 逐位检查，直到倒数第 l 位
            for c in num[:-l]:
                if int(c) >= limit:
                    res += power
                    return res
                power //= limit
                res += int(c)*power
            # 检查最后 l 位数字是否等于 s
            res += (int(num[-l:]) >= s)
            return res

        # 初始化 l, s, 和 limit
        l, s, limit = len(s), int(s), limit+1
        # 计算区间 [start, finish] 内强大整数的个数
        return count(finish) - count(start-1)

Explore

在`count(num)`函数中，增加`limit`值的1是用来将数字的最大可能值（即`limit`）纳入计算范围内。因为在计算数字组合的可能性时，我们需要考虑所有小于等于`limit`的数字（包括`limit`本身）。例如，如果`limit`是5，我们需要考虑的数字是0到5，共6个数字。将`limit`加1是为了方便使用0到`limit`这`limit+1`个数字进行组合的计算，避免在循环和条件判断中进行额外的边界处理。

`len(num)-l`代表的是在检查数字`num`时，除去末尾`s`长度`l`之后的数字位数。`power`在这里表示每一位数字（从最高位到`s`开始的位置）可以代表的数值范围。例如，如果`num`是123456，且`s`的长度是3，则`len(num)-l`计算的是123这三个数字的位数。`pow(limit, len(num)-l)`计算的是从最高位到`s`开始的位置，每一位数字可以变化的总数，即每位数字都可以从0至`limit`变化，共有`pow(limit, len(num)-l)`种可能。

在`count`函数中，`int(c)*power`的计算是为了计算当前数字位`c`对总数的贡献。这里，`power`表示当前位后面的每一位数字可以取的所有可能值的总数（即权重）。例如，如果当前位是百位，且`limit`为5，那么每增加1百（如从100到200），后面的两位数字可以有`pow(limit, 2)`种可能的组合。当当前位的数字`c`小于`limit`时，表示该位可以自由取值，而且每增加1，后面的组合数就增加`power`次。这种计算逻辑确保了从当前位开始到最低位的所有可能的数字组合都被正确计算，从而确保了总数的正确性。