2719.統計整數數目

給你兩個數字字符串 num1 和 num2，以及兩個整數 max_sum 和 min_sum. 如果一個整數滿足一下條件，我們稱它是一個好整數：

  • num1 <= x <= num2
  • min_sum <= digit_sum(x) <= max_sum

請你返回好整數的數目。答案可能很大，請返回答案對 10^9+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 <= 10^22
  • 1 <= min_sum <= max_sum <= 400

Related Topics

  • 數學
  • 字符串
  • 動態規劃

题目链接: link

解答

先分析題目，題目翻譯一下就是要找 [num1, num2] 之間有多少個數的各位數之和在 min_sum 和 max_sum 之間。那我們爲了簡化問題可以轉而求 [1, num] 之間有多少個各位數之和在min_sum 和 max_sum 之間，然後轉爲求 [1, num2]-[1,num1] ，因爲這裏得到的區間是 (num1, num2] ，因此還需要再單獨判斷num1 的各位數之和，或者直接求 [1,num2] - [1,num1-1], 看你覺得哪個更方便了。

按理來説題目範圍内各位數之和最大的數應該是 10^22-1 一共22個9，最大不會超過當前字符串長度的9倍。 max_sum 根本不會達到 400，因此如果要用到數組存每個好證書對應的 digit_sum(x), 那麽這個長度只需要 min(9*n, max_sum) 即可。

然後自己分析了一大通，最後過了三分之一的測試用例，結果一分析，自己就是寫了一坨，前前後後搞了三個小時，直接選擇看題解。

下面學習一下別人的題解。

class Solution {
    private static final int MOD = 1_000_000_007;

    public int count(String num1, String num2, int minSum, int maxSum) {
        // 這邊的思路就是 [1,num2] - [1,num1] 然後單獨判斷 num1 部分
        int ans = calc(num2, minSum, maxSum) - calc(num1, minSum, maxSum) + MOD; // 避免负数
        // 這裏是因爲可能出現那種 前面已經取過余了，導致後面更小的情況。下面就是單獨判斷的代碼
        int sum = 0;
        for (char c : num1.toCharArray()) {
            sum += c - '0';
        }

        if (minSum <= sum && sum <= maxSum) {
            ans++; // num1 是合法的，补回来
        }
        return ans % MOD;
    }

    // 這裏就是計算 [1, num]
    private int calc(String s, int minSum, int maxSum) {
        int n = s.length();
        // 和前面説的一樣，節約空間
        int[][] memo = new int[n][Math.min(9 * n, maxSum) + 1];
        // 全部初始化一遍為 -1 表示未知
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(0, 0, true, s.toCharArray(), minSum, maxSum, memo);
    }
    // sum應該是當前求和的值
    // i 表示 num 字符串的索引, [0, s.length-1]
    private int dfs(int i, int sum, boolean isLimit, char[] s, int minSum, int maxSum, int[][] memo) {
        if (sum > maxSum) { // 非法
            return 0;
        }
        
        if (i == s.length) {
            return sum >= minSum ? 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
            // 就是假設當前位是d，然後填後面的，如果當前位不是到達限制位，那就後面隨便就行
            res = (res + dfs(i + 1, sum + d, isLimit && (d == up), s, minSum, maxSum, memo)) % MOD;
        }

        // 如果沒有限制就存起來
        if (!isLimit) {
            memo[i][sum] = res;
        }
        return res;
    }
}

代碼直觀地理解就是，我先根據當前數字的長度畫一樣長度的綫。

以 “23456” 舉例

_ _ _ _ _
第一位肯定是有限制的，畢竟第一位不能超過2嘛至少，因此一開始啓動dfs的時 isLimit=true, 那麽此時的 up=2, 那麽從0開始，這時候就是 0 _ _ _ _ _, 此時第二位是多少都OK了，因此此時 isLimit=false, 然後庫庫填，因爲對於 x x x _ _ _ 如果此時沒有限制，且留下的位數一樣的話, 那麽 後面三位其實能填的範圍都是 0-9, 因此如果此時當前填寫位數一樣且前面位和也一樣，其實兩者狀態一樣，因此可以節省後面三位的重複計算直接存起來。如果第一位到了2, 那麽此時下一位就有限制了, 至少不能超過3嘛， 接下來的都差不多.

看題解原來這種叫數位DP，下次做做相似的題目鞏固一下。

動態規劃是我的大薄弱項, 狠狠學！