leetcode-2719统计证书数目

发布时间:2024年01月16日

题目链接

2719. 统计整数数目 - 力扣(LeetCode)

解题思路

  • 题目实际上求的是[num1,...num2]中,数位和在[min_sum,...max_sum]的数的个数。对于这种区间[l,...r]的问题,我们可以考虑转化为求[1,...r]和[1,...l-1]的答案,然后相减
  • 对于[1,...r]的答案,我们可以使用DP数位来求解。我们设计一个函数dfs(pos,s,limit)表示处理到第pos位,数位和为s,当前数是否有上界限制limit的方案数。其中pos从高到低枚举。
  • 对于dfs(pos,s,limit),我们可以枚举当前数位i的值,然后递归计算dfs(pos+l,s+i,limit^(i==up)),其中up表示当前数位的商界。如果limit为真,那么up就是当前数位的上界,否则up表示为9。如果pos大于等于num的长度,那么我们就可以判断s是否在[min_sum,...max_sum]的范围内,如果在就返回1,否则返回0。

实话实说,真看不懂。

解题代码

class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        def calc(high: str) -> int:
            @cache
            def dfs(i: int, s: int, is_limit: bool) -> int:
                if s > max_sum:  # 非法
                    return 0
                if i == len(high):
                    return s >= min_sum
                res = 0
                up = int(high[i]) if is_limit else 9
                for d in range(up + 1):  # 枚举当前数位填 d
                    res += dfs(i + 1, s + d, is_limit and d == up)
                return res
            return dfs(0, 0, True)

        is_num1_good = min_sum <= sum(map(int, num1)) <= max_sum
        return (calc(num2) - calc(num1) + is_num1_good) % 1_000_000_007

文章来源:https://blog.csdn.net/weixin_53908842/article/details/135629930
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。