2024-1-16
文章目录
- [2719. 统计整数数目](https://leetcode.cn/problems/count-of-integers/)
- 思路：
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，并减去 1f = 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;}点击移步博客主页，欢迎光临~
