class Solution {
public:
int count(string num1, string num2, int min_sum, int max_sum) {
}
};
6396. 统计整数数目
给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：
num1 <= x <= num2min_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 <= 10221 <= min_sum <= max_sum <= 400原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 4.6 MB, 提交时间: 2024-01-16 17:41:03
func count(num1, num2 string, minSum, maxSum int) int {
const mod = 1_000_000_007
n := len(num2)
num1 = strings.Repeat("0", n-len(num1)) + num1 // 补前导零，和 num2 对齐
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, min(9*n, maxSum)+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(int, int, bool, bool) int
dfs = func(i, sum int, limitLow, limitHigh bool) (res int) {
if sum > maxSum { // 非法
return
}
if i == n {
if sum >= minSum { // 合法
return 1
}
return
}
if !limitLow && !limitHigh {
p := &memo[i][sum]
if *p >= 0 {
return *p
}
defer func() { *p = res }()
}
lo := 0
if limitLow {
lo = int(num1[i] - '0')
}
hi := 9
if limitHigh {
hi = int(num2[i] - '0')
}
for d := lo; d <= hi; d++ { // 枚举当前数位填 d
res = (res + dfs(i+1, sum+d, limitLow && d == lo, limitHigh && d == hi)) % mod
}
return
}
return dfs(0, 0, true, true)
}
cpp 解法, 执行用时: 32 ms, 内存消耗: 8.2 MB, 提交时间: 2024-01-16 17:40:29
class Solution {
public:
int count(string num1, string num2, int min_sum, int max_sum) {
int n = num2.length();
num1 = string(n - num1.length(), '0') + num1; // 补前导零，和 num2 对齐
vector<vector<int>> memo(n, vector<int>(min(9 * n, max_sum) + 1, -1));
function<int(int, int, bool, bool)> dfs = [&](int i, int sum, bool limit_low, bool limit_high) -> int {
if (sum > max_sum) { // 非法
return 0;
}
if (i == n) {
return sum >= min_sum;
}
if (!limit_low && !limit_high && memo[i][sum] != -1) {
return memo[i][sum];
}
int lo = limit_low ? num1[i] - '0' : 0;
int hi = limit_high ? num2[i] - '0' : 9;
int res = 0;
for (int d = lo; d <= hi; d++) { // 枚举当前数位填 d
res = (res + dfs(i + 1, sum + d, limit_low && d == lo, limit_high && d == hi)) % 1'000'000'007;
}
if (!limit_low && !limit_high) {
memo[i][sum] = res;
}
return res;
};
return dfs(0, 0, true, true);
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 42.3 MB, 提交时间: 2024-01-16 17:40:02
class Solution {
public int count(String num1, String num2, int minSum, int maxSum) {
int n = num2.length();
num1 = "0".repeat(n - num1.length()) + num1; // 补前导零，和 num2 对齐
int[][] memo = new int[n][Math.min(9 * n, maxSum) + 1];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(0, 0, true, true, num1.toCharArray(), num2.toCharArray(), minSum, maxSum, memo);
}
private int dfs(int i, int sum, boolean limitLow, boolean limitHigh, char[] num1, char[] num2, int minSum, int maxSum, int[][] memo) {
if (sum > maxSum) { // 非法
return 0;
}
if (i == num2.length) {
return sum >= minSum ? 1 : 0;
}
if (!limitLow && !limitHigh && memo[i][sum] != -1) {
return memo[i][sum];
}
int lo = limitLow ? num1[i] - '0' : 0;
int hi = limitHigh ? num2[i] - '0' : 9;
int res = 0;
for (int d = lo; d <= hi; d++) { // 枚举当前数位填 d
res = (res + dfs(i + 1, sum + d, limitLow && d == lo, limitHigh && d == hi,
num1, num2, minSum, maxSum, memo)) % 1_000_000_007;
}
if (!limitLow && !limitHigh) {
memo[i][sum] = res;
}
return res;
}
}
python3 解法, 执行用时: 176 ms, 内存消耗: 18.1 MB, 提交时间: 2024-01-16 17:39:29
# 一次记忆化搜搜
class Solution:
def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
n = len(num2)
num1 = num1.zfill(n) # 补前导零，和 num2 对齐
@cache
def dfs(i: int, s: int, limit_low: bool, limit_high: bool) -> int:
if s > max_sum: # 非法
return 0
if i == n:
return s >= min_sum
lo = int(num1[i]) if limit_low else 0
hi = int(num2[i]) if limit_high else 9
res = 0
for d in range(lo, hi + 1): # 枚举当前数位填 d
res += dfs(i + 1, s + d, limit_low and d == lo, limit_high and d == hi)
return res
return dfs(0, 0, True, True) % 1_000_000_007
cpp 解法, 执行用时: 64 ms, 内存消耗: 9.9 MB, 提交时间: 2024-01-16 17:38:45
// 两次记忆化搜索
class Solution {
const int MOD = 1'000'000'007;
int calc(string &s, int min_sum, int max_sum) {
int n = s.length();
vector<vector<int>> memo(n, vector<int>(min(9 * n, max_sum) + 1, -1));
function<int(int, int, bool)> dfs = [&](int i, int sum, bool is_limit) -> int {
if (sum > max_sum) { // 非法
return 0;
}
if (i == n) {
return sum >= min_sum ? 1 : 0;
}
if (!is_limit && memo[i][sum] != -1) {
return memo[i][sum];
}
int up = is_limit ? s[i] - '0' : 9;
int res = 0;
for (int d = 0; d <= up; d++) { // 枚举当前数位填 d
res = (res + dfs(i + 1, sum + d, is_limit && d == up)) % MOD;
}
if (!is_limit) {
memo[i][sum] = res;
}
return res;
};
return dfs(0, 0, true);
}
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) {
sum += c - '0';
}
ans += min_sum <= sum && sum <= max_sum; // num1 是合法的，补回来
return ans % MOD;
}
};
golang 解法, 执行用时: 12 ms, 内存消耗: 6.3 MB, 提交时间: 2023-06-05 09:48:40
func count(num1, num2 string, minSum, maxSum int) int {
const mod int = 1e9 + 7
f := func(s string) int {
memo := make([][]int, len(s))
for i := range memo {
memo[i] = make([]int, min(9*len(s), maxSum)+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(p, sum int, limitUp bool) int
dfs = func(p, sum int, limitUp bool) (res int) {
if sum > maxSum { // 非法
return
}
if p == len(s) {
if sum >= minSum { // 合法
return 1
}
return
}
if !limitUp {
ptr := &memo[p][sum]
if *ptr >= 0 {
return *ptr
}
defer func() { *ptr = res }()
}
up := 9
if limitUp {
up = int(s[p] - '0')
}
for d := 0; d <= up; d++ { // 枚举要填入的数字 d
res = (res + dfs(p+1, sum+d, limitUp && d == up)) % mod
}
return
}
return dfs(0, 0, true)
}
ans := f(num2) - f(num1) + mod // 避免负数
sum := 0
for _, c := range num1 {
sum += int(c - '0')
}
if minSum <= sum && sum <= maxSum { // x=num1 是合法的，补回来
ans++
}
return ans % mod
}
func min(a, b int) int { if b < a { return b }; return a }
java 解法, 执行用时: 11 ms, 内存消耗: 42.3 MB, 提交时间: 2023-06-05 09:47:49
class Solution {
private static final int MOD = (int) 1e9 + 7;
private int minSum, maxSum;
public int count(String num1, String num2, int minSum, int maxSum) {
this.minSum = minSum;
this.maxSum = maxSum;
int ans = count(num2) - count(num1) + MOD; // 避免负数
int sum = 0;
for (char c : num1.toCharArray()) sum += c - '0';
if (minSum <= sum && sum <= maxSum) ans++; // x=num1 是合法的，补回来
return ans % MOD;
}
private int count(String S) {
var s = S.toCharArray();
int n = s.length;
var memo = new int[n][Math.min(9 * n, maxSum) + 1];
for (int i = 0; i < n; i++)
Arrays.fill(memo[i], -1); // -1 表示没有计算过
return f(s, memo, 0, 0, true);
}
private int f(char[] s, int[][] memo, int i, int sum, boolean isLimit) {
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 res = 0;
int up = isLimit ? s[i] - '0' : 9;
for (int d = 0; d <= up; ++d) // 枚举要填入的数字 d
res = (res + f(s, memo, i + 1, sum + d, isLimit && d == up)) % MOD;
if (!isLimit) memo[i][sum] = res;
return res;
}
}
python3 解法, 执行用时: 308 ms, 内存消耗: 17.4 MB, 提交时间: 2023-06-05 09:47:37
'''
数位dp通用模板，f(i, sum, is_limit)
'''
class Solution:
def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
MOD = 10 ** 9 + 7
def f(s: string) -> int:
@cache # 记忆化搜索
def f(i: int, sum: int, is_limit: bool) -> int:
if sum > max_sum: # 非法
return 0
if i == len(s):
return int(sum >= min_sum)
res = 0
up = int(s[i]) if is_limit else 9
for d in range(up + 1): # 枚举要填入的数字 d
res += f(i + 1, sum + d, is_limit and d == up)
return res % MOD
return f(0, 0, True)
ans = f(num2) - f(num1) + (min_sum <= sum(map(int, num1)) <= max_sum)
return ans % MOD