知名网站建设推荐,深圳定制巴士怎么预约,高端定制网站开发,做购物网站能否生存LeetCode
2719.统计整数数目
2719. 统计整数数目 - 力扣#xff08;LeetCode#xff09;
题目描述
给你两个数字字符串 num1 和 num2 #xff0c;以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件#xff0c;我们称它是一个好整数#xff1a;
num1 LeetCode
题目描述
给你两个数字字符串 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
思路
无思路、cv大法 看题解的思路是数位DP 代码
C
static constexpr long long mod 1e9 7;
using LL long long;
class Solution {public:int Min_sum, Max_sum;LL calc(string s) {LL m s.size();vector memo(25, vectorLL(450, -1));functionLL(LL, LL, bool, bool) dfs [](LL i, LL cnt, bool is_limit, bool is_num) - LL {if (i m) return cnt Min_sum and cnt Max_sum;if (!is_limit and is_num and memo[i][cnt] ! -1) return memo[i][cnt];LL res 0;if (!is_num) {res dfs(i 1, cnt, false, false);res % mod;}int up is_limit ? s[i] - 0 : 9;int low is_num ? 0 : 1;for (int d low; d up; d) {res dfs(i 1, cnt d, is_limit and d up, true);res % mod;}if (!is_limit and is_num) memo[i][cnt] res;return res;};return dfs(0, 0, true, false);}bool check(string s) {int cnt 0;for (char c : s) cnt c - 0;return cnt Min_sum and cnt Max_sum;}int count(string num1, string num2, int min_sum, int max_sum) {Max_sum max_sum;Min_sum min_sum;LL ans calc(num2) - calc(num1) check(num1);return (ans % mod mod) % mod;}
};Java
class Solution {
static final long mod 1000000007;int Min_sum, Max_sum;public long calc(String s) {int m s.length();long[][] memo new long[25][450];for (int i 0; i 25; i) {Arrays.fill(memo[i], -1);}return dfs(0, 0, true, false, s, m, memo);}private long dfs(int i, int cnt, boolean is_limit, boolean is_num, String s, int m, long[][] memo) {if (i m) return cnt Min_sum cnt Max_sum ? 1 : 0;if (!is_limit is_num memo[i][cnt] ! -1) return memo[i][cnt];long res 0;if (!is_num) {res dfs(i 1, cnt, false, false, s, m, memo);res % mod;}int up is_limit ? s.charAt(i) - 0 : 9;int low is_num ? 0 : 1;for (int d low; d up; d) {res dfs(i 1, cnt d, is_limit d up, true, s, m, memo);res % mod;}if (!is_limit is_num) memo[i][cnt] res;return res;}public boolean check(String s) {int cnt 0;for (char c : s.toCharArray()) cnt c - 0;return cnt Min_sum cnt Max_sum;}public int count(String num1, String num2, int min_sum, int max_sum) {Max_sum max_sum;Min_sum min_sum;long ans calc(num2) - calc(num1) (check(num1) ? 1 : 0);return (int) ((ans % mod mod) % mod);}
}
