统计强大整数的数目

题目

100163. 统计强大整数的数目

---

给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。

如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。

请你返回区间 [start..finish] 内强大整数的 总数目 。

如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。

示例 1：

输入：start = 1, finish = 6000, limit = 4, s = "124"
输出：5
解释：区间 [1..6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。
这个区间内总共只有这 5 个强大整数。

示例 2：

输入：start = 15, finish = 215, limit = 6, s = "10"
输出：2
解释：区间 [15..215] 内的强大整数为 110 和 210 。这些整数的各个数位都 <= 6 且 "10" 是它们的后缀。
这个区间总共只有这 2 个强大整数。

示例 3：

输入：start = 1000, finish = 2000, limit = 4, s = "3000"
输出：0
解释：区间 [1000..2000] 内的整数都小于 3000 ，所以 "3000" 不可能是这个区间内任何整数的后缀。

提示：

• 1 <= start <= finish <= 10^15
• 1 <= limit <= 9
• 1 <= s.length <= floor(log10(finish)) + 1
• s 数位中每个数字都小于等于 limit 。
• s 不包含任何前导 0 。

题解

方法一：

思路

dp[p][a][b]代表着 “填充到了第p位(p从0开始)，a为前i位是否为n的前缀，b为前i位是否全部为0，
第i位及之后的位数可以任意构造，最终构造的数范围在0到n，各个位数小于limit” 的个数。

设当前构造的数字前缀为num，我们需要保证num最后再拼接一个s满足范围在0到n。
所以我们只需要构造|n|-|s|位数字就可以得到一个构造结果了。

一种特殊情况，最大1234567尾缀为568。如果我们构造的num是1234后面拼接568，得到的构造结果1234568>1234567，所以我们需要再判断上界a，若a=1并且n的末|s|位小于等于s则当前构造不可行。

代码

class Solution {
public:
    using ll = long long;
    string num;
    string sf;
    ll lm;
    ll dp[18][2][2];
    ll dfs(int p, int a, int b) {
        // cout << p << " " << a << " " << b << " " << endl;   
        if (p + sf.size() == num.size()) {
            if (a && stoll(num.substr(num.size()-sf.size())) < stoll(sf)) return 0;
            return 1;
        }
        if (dp[p][a][b] != -1) return dp[p][a][b]; //遇到计算过的状态直接返回
        ll res = 0;
        if (b == 1)  {
            res += dfs(p+1, 0, 1);
        }

        for (int i=(b?1:0); i<=(a?num[p]-'0':9); i++) {
            if (i<=lm) {
                res += dfs(p+1, a&&(i==num[p]-'0'), 0); 
            }
            
        }
        return dp[p][a][b] = res;
    }
    ll cnt_pre(ll n) {
        num = to_string(n);
        if (stoll(sf) > n) return 0;
        memset(dp, -1, sizeof(dp));
        return dfs(0, 1, 1);
    }
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string suf) {
        sf = suf;
        lm = limit;
        ll a = cnt_pre(finish);
        ll b = cnt_pre(start-1);
        return a - b;
    }
    
};