【每日一题】2719. 统计整数数目-2024.1.16

发布时间:2024年01月16日

题目;

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

解答:

v1.0 模板视频讲解

v2.0 模板视频讲解?

代码:

class Solution {
    private static final int MOD=1_000_000_007;
    public int count(String num1, String num2, int min_sum, int max_sum) {
        int ans=calc(num2,min_sum,max_sum)-calc(num1,min_sum,max_sum)+MOD;//避免负数
        int sum=0;
        for(char c:num1.toCharArray()){
            sum+=c-'0';
        }
        if(min_sum<=sum&&sum<=max_sum){
            ans++;//num1是合法的,补回来
        }
        return ans%MOD;
    }
    private int calc(String s,int min_sum,int max_sum){
        int n=s.length();
        int[][] memo=new int[n][Math.min(9*n,max_sum)+1];
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        return dfs(0,0,true,s.toCharArray(),min_sum,max_sum,memo);
    }
    private int dfs(int i,int sum,boolean isLimit,char[] s,int min_sum,int max_sum,int[][] memo){
        if(sum>max_sum){//非法
            return 0;
        }
        if(i==s.length){
            return sum>=min_sum?1:0;
        }
        if(!isLimit&&memo[i][sum]!=-1){
            return memo[i][sum];
        }
        int up=isLimit?s[i]-'0':9;
        int res=0;
        for(int d=0;d<=up;d++){//枚举当前数据填d
            res=(res+dfs(i+1,sum+d,isLimit&&(d==up),s,min_sum,max_sum,memo)) % MOD;
        }
        if(!isLimit){
            memo[i][sum]=res;
        }
        return res;
    }
}

结果:

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