统计整数数目
难度:
标签:
题目描述
You are given two numeric strings num1 and num2 and two integers max_sum and min_sum. We denote an integer x to be good if:
num1 <= x <= num2min_sum <= digit_sum(x) <= max_sum.
Return the number of good integers. Since the answer may be large, return it modulo 109 + 7.
Note that digit_sum(x) denotes the sum of the digits of x.
Example 1:
Input: num1 = "1", num2 = "12", min_sum = 1, max_sum = 8
Output: 11
Explanation: There are 11 integers whose sum of digits lies between 1 and 8 are 1,2,3,4,5,6,7,8,10,11, and 12. Thus, we return 11.
Example 2:
Input: num1 = "1", num2 = "5", min_sum = 1, max_sum = 5
Output: 5
Explanation: The 5 integers whose sum of digits lies between 1 and 5 are 1,2,3,4, and 5. Thus, we return 5.
Constraints:
1 <= num1 <= num2 <= 10221 <= min_sum <= max_sum <= 400
代码结果
运行时间: 44 ms, 内存: 17.9 MB
/*
* Solution using Java Stream to count the number of 'good integers' between num1 and num2.
* This solution leverages the use of streams for cleaner code and functional style.
* The definition of a 'good integer' and the required conditions remain the same.
*/
import java.math.BigInteger;
import java.util.stream.Stream;
public class GoodIntegersStream {
private static final int MOD = 1_000_000_007;
public int countGoodIntegers(String num1, String num2, int min_sum, int max_sum) {
BigInteger lower = new BigInteger(num1);
BigInteger upper = new BigInteger(num2);
return Stream.iterate(lower, n -> n.compareTo(upper) <= 0, n -> n.add(BigInteger.ONE))
.mapToInt(this::getDigitSum)
.filter(sum -> sum >= min_sum && sum <= max_sum)
.map(sum -> 1)
.reduce(0, (a, b) -> (a + b) % MOD);
}
private int getDigitSum(BigInteger number) {
return number.toString().chars().map(c -> c - '0').sum();
}
}解释
方法:
The solution uses a digit dynamic programming approach to efficiently count numbers within a specific range whose digit sum falls between given bounds. It considers two main functions: 1) 'ndn(n, dsum)', which calculates how many n-digit numbers have a digit sum exactly equal to 'dsum'. 2) 'ddn(num, max_sum)', which calculates the count of numbers up to 'num' that have a digit sum of at most 'max_sum'. The main idea is to count the numbers satisfying the conditions up to 'num2' and subtract the count of numbers up to 'num1' - 1 (thus counting numbers between 'num1' and 'num2'), and adjust this for the specified digit sum range.
时间复杂度:
O(D^2 * 10 * max_sum) where D is the number of digits in 'num2'. This complexity stems from the iteration over all possible first digits and recursive processing for each subsequent digit.
空间复杂度:
O(D * max_sum), which accounts for the maximum depth of recursion multiplied by the range of digit sums cached.
代码细节讲解
🦆
在解决方案中，`ndn(n, dsum)`函数的基本情况是什么意义，为什么当`n == 0`时返回1？
▷🦆
对于`ddn(num, max_sum)`函数，如何确保所有可能的数位组合都被正确考虑，特别是在处理数字的最高位时？
▷🦆
解释为什么需要在计算`num1`对应的好整数时，将`num1`减去1，并在后续处理中如何确保这种调整的正确性？
▷🦆
在`ddn`函数中，递归调用遇到的边界条件`max_sum < 0`是如何影响结果的，为什么返回0？
▷