一、题目
1、题目描述
给你两个数字字符串
num1
和num2
,以及两个整数max_sum
和min_sum
。如果一个整数x
满足以下条件,我们称它是一个好整数:
num1 <= x <= num2
min_sum <= digit_sum(x) <= max_sum
.请你返回好整数的数目。答案可能很大,请返回答案对
109 + 7
取余后的结果。注意,
digit_sum(x)
表示x
各位数字之和。
2、接口描述
class Solution {
public:
int count(string num1, string num2, int min_sum, int max_sum) {
}
};
3、原题链接
2719. 统计整数数目
二、解题报告
1、思路分析
数位dp板子题
数位dp详见:数位dp详解,记忆化搜索,递推,OJ精讲-CSDN博客
设计状态f[n][pre][lim]为剩余n位,n位之前的数位和为pre,前面枚举位和给定数字对应位大小关系为lim
那么转移方程为f[n][pre][lim] = Σdfs(n - 1 , pre + i , lim || i < ceil) , 其中ceil = lim ? 9 : d[n]
跑板子即可,确实没什么说的,只要学过数位dp很容易就套板子套出来了
由于给出的数字是高精度字符串,所以对于小的那个数字-1的时候按照高精度的处理方式来,细节处理好文章来源:https://www.toymoban.com/news/detail-798079.html
2、复杂度
时间复杂度: O(n * 9 * n * 9) 空间复杂度:O(n * 9 * n)文章来源地址https://www.toymoban.com/news/detail-798079.html
3、代码详解
class Solution
{
public:
#define N 24
typedef long long ll;
const ll MOD = 1e9 + 7;
ll f[N][N * 9];
int r, l, d[N], len, n1, n2;
Solution() { memset(f, -1, sizeof(f)); }
int count(string num1, string num2, int min_sum, int max_sum)
{
function<int(int, int, bool)> dfs = [&](int n, int pre, bool lim) -> int
{
if (!n)
return pre >= min_sum && pre <= max_sum;
if (lim && ~f[n][pre])
return f[n][pre];
ll res = 0, ceil = lim ? 9 : d[n];
for (int i = 0; i <= ceil; i++)
res = (res + dfs(n - 1, pre + i, lim || i < ceil)) % MOD;
if (lim)
return f[n][pre] = res;
return res;
};
n2 = num2.size(), n1 = num1.size() , len = 0;
while (n2--)
d[++len] = (num2[n2] ^ 48);
r = dfs(len, 0, false);
len = 0;
while (n1--)
d[++len] = (num1[n1] ^ 48);
n1 = 1;
d[1]--;
while (n1 <= len && d[n1] == -1)
d[n1++] += 10, d[n1]--;
l = dfs(len, 0, false);
return (r - l + MOD) % MOD;
}
};
到了这里,关于LeetCode 2719. 统计整数数目,数位dp板子题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!