2024-1-16
2719. 统计整数数目
思路:
- 在类中定义了一些私有属性,包括模数
mod
,用于缓存计算结果的二维数组f
,输入的数字字符串num
,最小和min
和最大和max
。 - 实现了一个
count
方法,用于计算满足条件的方案数。方法接受两个数字字符串num1
和num2
,以及最小和min_sum
和最大和max_sum
作为参数。方法返回一个整数,表示满足条件的方案数。 - 在
count
方法中,首先将min_sum
和max_sum
分别赋值给min
和max
。 - 然后将
num2
赋值给num
,并初始化缓存数组f
。 - 调用
dfs
方法计算num
的方案数,并将结果赋值给a
。 - 接着,将
num1
转为BigInteger
类型,并减去 1,然后将结果转为字符串,并赋值给num
。 - 重置缓存数组
f
。 - 再次调用
dfs
方法计算num - 1
的方案数,并将结果赋值给b
。 - 返回
(a - b + mod) % mod
,即满足条件的方案数。 - 实现了一个私有的
dfs
方法,用于递归计算方案数。该方法接受三个参数,分别是当前遍历到的位置pos
、当前的和s
和是否限制边界limit
。方法返回一个整数,表示方案数。 - 在
dfs
方法中,首先判断递归结束的条件,即当遍历到num
字符串的末尾时,如果当前和在min
和max
范围内,返回 1,否则返回 0。 - 接着,判断是否限制边界并且该状态是否已经计算过,如果是,则直接返回缓存结果。
- 定义一个变量
ans
用于记录方案数,默认值为 0。 - 根据限制边界来确定当前位置的上界,如果限制边界,则取当前位置的字符转为数字,否则取 9。
- 使用循环遍历当前位置的所有可能取值,从 0 到上界。
- 在循环中,递归调用
dfs
方法计算下一位的方案数,并将结果累加到ans
中,同时考虑当前位是否达到上界,更新限制边界。 - 如果不限制边界,则将计算结果缓存起来。
- 返回
ans
,即当前状态的方案数。
import java.math.BigInteger;
private final int mod = (int) 1e9 + 7;
private Integer[][] f; // 用于缓存计算结果,避免重复计算
private String num; // 输入的数字字符串
private int min; // 最小和
private int max; // 最大和
//2719. 统计整数数目
public int count(String num1, String num2, int min_sum, int max_sum) {
min = min_sum;
max = max_sum;
num = num2;
f = new Integer[23][220]; // 初始化缓存数组,其中 23 是 num 字符串的最大长度,220 是可能的最大和的范围
int a = dfs(0, 0, true); // 计算 num 的方案数
num = new BigInteger(num1).subtract(BigInteger.ONE).toString(); // 将 num 转为 BigInteger,并减去 1
f = new Integer[23][220]; // 重置缓存数组
int b = dfs(0, 0, true); // 计算 num - 1 的方案数
return (a - b + mod) % mod; // 返回两个方案数之差,并对 mod 取模
}
private int dfs(int pos, int s, boolean limit) {
if (pos >= num.length()) {
// 递归结束条件,当遍历到 num 字符串末尾时
return s >= min && s <= max ? 1 : 0; // 如果当前和在 min 和 max 范围内,返回 1,否则返回 0
}
if (!limit && f[pos][s] != null) {
// 如果不限制边界并且已经计算过该状态,直接返回缓存结果
return f[pos][s];
}
int ans = 0;
int up = limit ? num.charAt(pos) - '0' : 9; // 根据限制边界来确定当前位的上界
for (int i = 0; i <= up; ++i) {
// 遍历当前位的所有可能取值
ans = (ans + dfs(pos + 1, s + i, limit && i == up)) % mod; // 递归求解下一位的方案数,并累加到结果中
}
if (!limit) {
// 如果不限制边界,则将计算结果缓存起来
f[pos][s] = ans;
}
return ans;
}