2999.统计强大整数的数目：上下界数位DP

【LetMeFly】2999.统计强大整数的数目：上下界数位DP

力扣题目链接：https://leetcode.cn/problems/count-the-number-of-powerful-integers/

给你三个整数 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 <= 1015
• 1 <= limit <= 9
• 1 <= s.length <= floor(log10(finish)) + 1
• s 数位中每个数字都小于等于 limit 。
• s 不包含任何前导 0 。

解题方法：上下界数位DP

我们可以从前往后一位一位地构造。在构造的过程中，要保证构造出来的数在start和finish之间（先不考虑limit和后缀s）。

例如start = 123，finish = 456的话：

• 假如我们构造的整数第一位为1，那么第二位最小为2（可以为2、3、4、...），但不能为0和1。
• 假如我们构造的整数第一位为2，那么第二位可以取0 - 9的任意数。
• 假设我们构造的整数第一位为3，那么第二位可以取0 - 9的任意数。
• 假设我们构造的整数第一位为4，那么第二位最大为5（可以为...、3、4、5），但不能为6 - 9。

也就是说，我们可以使用一个函数dfs(i, limitLow, limitHigh)来表示：(当前应该构造第i位、这一位的最小值是否需要限制为start[i]、这一位的最大值是否需要限制为finish[i])。

• 在构造下一位时，如果limitLow为true且构造的这一位为start[i]，则构造下一位时limitLow仍需为true。
• 在构造下一位时，如果limitHigh为true且构造的这一位为finish[i]，则构造下一位时limitHigh仍需为true。

然后就是考虑一下题目的额外两个限制limit和s。

构造过程中，任何一个元素不能超过limit；

构造过程中，若在构造最后的len(s)个元素，则当前元素最多有一种选择s[对应下标]。

最后就是需要记忆化一下。

记忆化的时候，记录(i, limitLow, limitHigh)三个变量可能有些麻烦，我们也可以只记录i这一个变量，并且在limitLow和limitHigh都为false时再使用记忆化。（因为有true的话不会被再次调用）

• 时间复杂度$O(\log finish\times D)$，其中$D=10$
• 空间复杂度$O(\log finish)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-04-13 11:03:19
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-04-13 11:56:04
 */
typedef long long ll;

class Solution {
private:
    int limit, n, nonFixed;
    string suffix, start, finish;
    unordered_map<int, ll> cache;

    ll dfs(int i, bool limitLow, bool limitHigh) {
        if (i == n) {
            return 1;
        }
        if (!limitLow && !limitHigh && cache.count(i)) {
            return cache[i];
        }
        int low = limitLow ? start[i] - '0' : 0;  // 这一位的有效范围时[log, high]
        int high = limitHigh ? finish[i] - '0' : 9;
        ll ans = 0;
        if (i < nonFixed) {
            for (int d = low; d <= min(high, limit); d++) {  // 构造这一位
                ans += dfs(i + 1, limitLow && d == low, limitHigh && d == high);
            }
        } else {
            int x = suffix[i - nonFixed] - '0';  // 构造这一位
            if (low <= x && x <= high) {  // 题目限制一定小于limit
                ans = dfs(i + 1, limitLow && x == low, limitHigh && x == high);
            }
        }
        if (!limitLow && !limitHigh) {
            cache[i] = ans;
        }
        return ans;
    }
public:
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        this->limit = limit;
        suffix = move(s);
        this->finish = to_string(finish);
        n = this->finish.size();
        this->start = to_string(start);
        this->start = string(n - this->start.size(), '0') + this->start;  // 原始范围时[1, 200]的话，将其变成[001, 200]
        nonFixed = n - this->suffix.size();

        return dfs(0, true, true);
    }
};

Python

'''
Author: LetMeFly
Date: 2025-04-12 22:20:48
LastEditors: LetMeFly.xyz
LastEditTime: 2025-04-12 22:37:40
'''
from functools import cache

class Solution:
    @cache
    def dfs(self, n: int, limitLow: bool, limitHigh: bool) -> int:
        if n == self.n:
            return 1
        low = self.start[n] if limitLow else 0
        high = self.finish[n] if limitHigh else 9
        ans = 0
        if n < self.free:  # 什么都可以
            for d in range(low, min(high, self.limit) + 1):
                ans += self.dfs(n + 1, limitLow and d == low, limitHigh and d == high)
        else:
            x = self.s[n - self.free]
            if low <= x <= high:
                ans = self.dfs(n + 1, limitLow and x == low, limitHigh and x == high)
        return ans
        
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        self.finish = list(map(int, str(finish)))
        self.n = len(self.finish)
        self.start = list(map(int, str(start).zfill(self.n)))
        self.limit = limit
        self.free = self.n - len(s)
        self.s = list(map(int, s))
        return self.dfs(0, True, True)

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-04-13 13:00:58
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-04-13 13:37:04
 * @Description: AC,70.30%,86.73%
 */
import java.util.Arrays;

class Solution {
    private int n, nonFixed, limit;
    private String start, finish, suffix;
    private long[] cache;

    private long dfs(int i, boolean limitLow, boolean limitHigh) {
        if (i == n) {
            return 1;
        }
        if (!limitLow && !limitHigh && cache[i] != -1) {
            return cache[i];
        }
        int low = limitLow ? start.charAt(i) - '0' : 0;
        int high = limitHigh ? finish.charAt(i) - '0' : 9;
        long ans = 0;
        if (i < nonFixed) {
            for (int d = low; d <= Math.min(limit, high); d++) {
                ans += dfs(i + 1, limitLow && d == low, limitHigh && d == high);
            }
        } else {
            int x = suffix.charAt(i - nonFixed) - '0';
            if (low <= x && x <= high) {
                ans = dfs(i + 1, limitLow && x == low, limitHigh && x == high);
            }
        }
        if (!limitLow && !limitHigh) {
            cache[i] = ans;
        }
        return ans;
    }
    
    public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
        this.finish = String.valueOf(finish);
        n = this.finish.length();
        this.start = String.valueOf(start);
        this.start = "0".repeat(n - this.start.length()) + this.start;
        this.limit = limit;
        nonFixed = n - s.length();
        cache = new long[n];
        Arrays.fill(cache, -1);
        suffix = s;
        return dfs(0, true, true);
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-04-13 13:38:32
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-04-13 14:00:33
 */
package main

import (
    "strconv"
    "strings"
)

func dfs2999(i int, limitLow, limitHigh bool, start, finish string, nonFixed int, cache []int64, limit int, suffix string) (ans int64) {
    if i == len(start) {
        return 1
    }
    if !limitLow && !limitHigh && cache[i] != -1 {
        return cache[i]
    }

    var low, high int
    if limitLow {
        low = int(start[i]) - int('0')
    } else {
        low = 0
    }
    if limitHigh {
        high = int(finish[i]) - int('0')
    } else {
        high = 9
    }
    if i < nonFixed {
        for d := low; d <= min(high, limit); d++ {
            ans += dfs2999(i + 1, limitLow && d == low, limitHigh && d == high, start, finish, nonFixed, cache, limit, suffix)
        }
    } else {
        d := int(suffix[i - nonFixed]) - int('0')
        if low <= d && d <= high {
            ans = dfs2999(i + 1, limitLow && d == low, limitHigh && d == high, start, finish, nonFixed, cache, limit, suffix)
        }
    }
    if !limitLow && !limitHigh {
        cache[i] = ans
    }
    return ans
}

func numberOfPowerfulInt(start int64, finish int64, limit int, s string) int64 {
    finish_str := strconv.FormatInt(finish, 10)
    cache := make([]int64, len(finish_str) + 1)
    for i := range cache {
        cache[i] = -1
    }
    start_str := strconv.FormatInt(start, 10)
    start_str = strings.Repeat("0", len(finish_str) - len(start_str)) + start_str
    nonFixed := len(finish_str) - len(s)
    return dfs2999(0, true, true, start_str, finish_str, nonFixed, cache, limit, s)
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源