2719-统计整数数目

https://leetcode.cn/problems/count-of-integers/description/

求解

暴力遍历

class Solution {
protected:
    long long _SumofEvery(long long input){
        int res=0;
        while(input){
            res+=input%10;
            input/=10;
        }
        return res;
    }
public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        long long left = stoll(num1),right = stoll(num2);
        int sum=0;
        for(long long i=left;i<=right;++i){
            int res = _SumofEvery(i);
            if(res>=min_sum&&res<=max_sum){
                sum+=1;
            }
        }
        int MOD = 1e9 + 1;
        return sum%MOD;
    }
};

时间复杂度太高

数位DP

class Solution {
    static constexpr int N = 23;
    static constexpr int M = 401;
    static constexpr int MOD = 1e9 + 7;
    int d[N][M];
    string num;
    int min_sum;
    int max_sum;

    int dfs(int i, int j, bool limit) {
        if (j > max_sum) {
            return 0;
        }
        if (i == -1) {
            return j >= min_sum;
        }
        if (!limit && d[i][j] != -1) {
            return d[i][j];
        }
        int res = 0;
        int up = limit ? num[i] - '0' : 9;
        for (int x = 0; x <= up; x++) {
            res = (res + dfs(i - 1, j + x, limit && x == up)) % MOD;
        }
        if (!limit) {
            d[i][j] = res;
        }
        return res;
    }

    int get(string num) {
        reverse(num.begin(), num.end());
        this->num = num;
        return dfs(num.size() - 1, 0, true);
    }

    // 求解 num - 1，先把最后一个非 0 字符减去 1，再把后面的 0 字符变为 9
    string sub(string num) {
        int i = num.size() - 1;
        while (num[i] == '0') {
            i--;
        }
        num[i]--;
        i++;
        while (i < num.size()) {
            num[i] = '9';
            i++;
        }
        return num;
    }
public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        memset(d, -1, sizeof d);
        this->min_sum = min_sum;
        this->max_sum = max_sum;
        return (get(num2) - get(sub(num1)) + MOD) % MOD;
    }
};

代码解释

这段代码实现了一个 Solution 类，用于解决特定的计数问题：给定两个数（以字符串形式表示的 num1 和 num2），计算在 [num1, num2] 范围内所有数的个位数之和在 [min_sum, max_sum] 范围内的数的总数。

类成员和方法

静态常量

• N 和 M 分别代表数字的最大长度和个位数之和的最大值。
• MOD 是取模运算使用的大素数（10^9 + 7）。

成员变量

• d[N][M]：一个二维数组，用于动态规划中的记忆化搜索。
• num：一个字符串，用于存储当前处理的数字。
• min_sum 和 max_sum：个位数之和的最小值和最大值。

方法

• dfs：深度优先搜索函数，用于计算数字的个位数之和在指定范围内的数的数量。
• get：处理字符串表示的数字，调用 dfs 函数。
• sub：将给定的数字减去 1，处理数字中的 0。
• count：主函数，计算在 [num1, num2] 范围内的数的个位数之和在 [min_sum, max_sum] 范围内的数的总数。

详细解释

dfs 函数

dfs 函数是一个记忆化

的递归函数，用于计算满足条件的数字数量。

1. 基本情形：

   • 如果当前的数字之和 j 超过了 max_sum，返回 0（无效情况）。
   • 如果已经处理完所有位（i == -1），检查 j 是否至少为 min_sum。如果是，返回 1（有效情况），否则返回 0。

2. 记忆化：

   • 如果当前不受限制（即 limit 为 false），并且 d[i][j] 已经有计算过的值，则直接返回这个值。

3. 遍历当前位可能的数字：

   • 根据 limit 决定当前位能取的最大数字 up。如果受限制，则 up 是 num[i] 对应的数字，否则是 9（无限制情况）。
   • 对于 0 到 up 的每个数字 x，递归调用 dfs 来处理下一位，并更新结果 res。

4. 更新记忆化数组：

   • 如果当前不受限制，将计算结果存入 d[i][j]。

get 函数

用于获取给定数字以下的满足条件的数字总数。

1. 反转数字：为了从最低位开始处理，反转数字字符串。
2. 调用 dfs：从最高位开始，调用 dfs 函数进行计算。

sub 函数

用于将数字字符串减去 1。主要用于处理 num1 - 1 的情况。

1. 处理末尾的 0：从字符串末尾开始，将每个 ‘0’ 变成 ‘9’，直到遇到第一个非 ‘0’ 字符。
2. 减去 1：将第一个非 ‘0’ 字符减去 1。

count 函数

主函数，用于计算 [num1, num2] 范围内满足条件的数字

总数。

1. 初始化动态规划数组：使用 memset 函数将 d 数组的所有元素初始化为 -1，表示这些元素尚未被计算。

2. 设置 min_sum 和 max_sum：将类的成员变量 min_sum 和 max_sum 设置为给定的最小和最大个位数之和。

3. 计算范围内的数字数量：

   • 使用 get(num2) 计算 num2 及以下的满足条件的数字总数。
   • 使用 get(sub(num1)) 计算 num1 - 1 及以下的满足条件的数字总数。
   • 计算这两个值的差，再加上 MOD（确保结果为正数），然后对 MOD 取模，得到 [num1, num2] 范围内满足条件的数字总数。

代码逻辑总结

此代码通过动态规划和深度优先搜索（DFS）的方法，有效地计算了一个数字范围内满足特定条件（个位数之和在给定范围内）的数字数量。它首先预处理数字，然后对每一位数字进行递归计算，同时使用记忆化技术提高效率。这种方法对处理大范围内的计数问题特别有效。

数位DP学习

https://www.acwing.com/file_system/file/content/whole/index/content/9199630/