LeetCode

2719.统计整数数目

2719. 统计整数数目 - 力扣（LeetCode）

题目描述

给你两个数字字符串 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

思路

无思路、cv大法

看题解的思路是数位DP

代码

C++

static constexpr long long mod = 1e9 + 7;
using LL = long long;
class Solution {
   public:
    int Min_sum, Max_sum;
    LL calc(string s) {
        LL m = s.size();
        vector memo(25, vector<LL>(450, -1));
        function<LL(LL, LL, bool, bool)> dfs = [&](LL i, LL cnt, bool is_limit, bool is_num) -> LL {
            if (i == m) return cnt >= Min_sum and cnt <= Max_sum;
            if (!is_limit and is_num and memo[i][cnt] != -1) return memo[i][cnt];
            LL res = 0;
            if (!is_num) {
                res += dfs(i + 1, cnt, false, false);
                res %= mod;
            }
            int up = is_limit ? s[i] - '0' : 9;
            int low = is_num ? 0 : 1;
            for (int d = low; d <= up; ++d) {
                res += dfs(i + 1, cnt + d, is_limit and d == up, true);
                res %= mod;
            }
            if (!is_limit and is_num) memo[i][cnt] = res;
            return res;
        };
        return dfs(0, 0, true, false);
    }
    bool check(string s) {
        int cnt = 0;
        for (char c : s) cnt += c - '0';
        return cnt >= Min_sum and cnt <= Max_sum;
    }
    int count(string num1, string num2, int min_sum, int max_sum) {
        Max_sum = max_sum;
        Min_sum = min_sum;
        LL ans = calc(num2) - calc(num1) + check(num1);
        return (ans % mod + mod) % mod;
    }
};

Java

class Solution {
static final long mod = 1000000007;
    int Min_sum, Max_sum;

    public long calc(String s) {
        int m = s.length();
        long[][] memo = new long[25][450];
        for (int i = 0; i < 25; i++) {
            Arrays.fill(memo[i], -1);
        }

        return dfs(0, 0, true, false, s, m, memo);
    }

    private long dfs(int i, int cnt, boolean is_limit, boolean is_num, String s, int m, long[][] memo) {
        if (i == m) return cnt >= Min_sum && cnt <= Max_sum ? 1 : 0;
        if (!is_limit && is_num && memo[i][cnt] != -1) return memo[i][cnt];
        long res = 0;

        if (!is_num) {
            res += dfs(i + 1, cnt, false, false, s, m, memo);
            res %= mod;
        }

        int up = is_limit ? s.charAt(i) - '0' : 9;
        int low = is_num ? 0 : 1;

        for (int d = low; d <= up; ++d) {
            res += dfs(i + 1, cnt + d, is_limit && d == up, true, s, m, memo);
            res %= mod;
        }

        if (!is_limit && is_num) memo[i][cnt] = res;
        return res;
    }

    public boolean check(String s) {
        int cnt = 0;
        for (char c : s.toCharArray()) cnt += c - '0';
        return cnt >= Min_sum && cnt <= Max_sum;
    }

    public int count(String num1, String num2, int min_sum, int max_sum) {
        Max_sum = max_sum;
        Min_sum = min_sum;
        long ans = calc(num2) - calc(num1) + (check(num1) ? 1 : 0);
        return (int) ((ans % mod + mod) % mod);
    }
}