leetcode2719. 统计整数数目

发布时间:2024年01月16日

Problem: 2719. 统计整数数目

题目

给你两个数字字符串 num1 和 num2 ,以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件,我们称它是一个好整数:

num1 <= x <= num2
min_sum <= digit_sum(x) <= max_sum.
请你返回好整数的数目。答案可能很大,请返回答案对 109 + 7 取余后的结果。

注意,digit_sum(x) 表示 x 各位数字之和。

示例 1:

输入:num1 = “1”, num2 = “12”, min_num = 1, max_num = 8
输出:11
解释:总共有 11 个整数的数位和在 1 到 8 之间,分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。
示例 2:

输入:num1 = “1”, num2 = “5”, min_num = 1, max_num = 5
输出:5
解释:数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。

提示:

1 <= num1 <= num2 <= 1022
1 <= min_sum <= max_sum <= 400

思路

我们编写一个函数,计算所有小于high且满足所有位的和小于max_sum的数的个数
将num1和num2分别带入这个函数,得到a和b,我们目前的答案就是 b - a;

注意,此时我们还没有处理num1,这个数,我们需要额外计算一下他是否满足好整数

对于计算出现次数的函数,我们的最终目的是构造一个满足大于等于min_sum且小于等于max_sum的数s,我们最终统计构造了多少次

我们申明三个参数:

  • i : 构造第i位
  • s:当前构造的数
  • is_limit: 是否受到前一位的制约

在递归过程中,当s大于max_sum时,说明这个s不可能被取到了,返回

当i递归到末尾,此时s满足好整数,则加1

我们判断下当前要填入的数的最大值有没有受前一位影响,如果被影响了,就只能填high[i],否则可以填0-9所有数,(eg:123,如果第一位我构造为0,则第二位只能填0,1,2,如果第一位构造为0,第二位可以填入0-9)

我们开始构造下一位数字

返回结果

复杂度

时间复杂度:

时间复杂度: O ( n m D ) O(nmD) O(nmD)

空间复杂度:

O ( m n ) O(mn) O(mn)

Code

class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        def calc(high):
            @cache 
            def dfs(i,s,is_limit):
                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):
                    res += dfs(i+1,s+d,is_limit and d==up)
                return res
            return dfs(0,0,True)

        ans =( calc(num2) - calc(num1) ) % 1_000_000_007
        x = 0
        for i in range(len(num1)):
            x += int(num1[i])
        if min_sum<= x <= max_sum:
            ans+=1

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