2999. 统计强大整数的数目

Hard

题目描述

给你三个整数 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 没有前导零

解题思路

这是一道数位动态规划（Digit DP）的经典题目。

核心思路：

强大整数必须以字符串 s 作为后缀，且每个数字不超过 limit
使用数位 DP 计算区间 [1, x] 内满足条件的数字个数
答案为 count(finish) - count(start-1)

数位 DP 状态设计：

dp(pos, tight, lead) 表示从第 pos 位开始填数字的方案数
tight：当前是否受到上界限制
lead：当前是否还在前导零状态

关键观察： 由于数字必须以 s 为后缀，我们可以将问题分为两部分：

前缀部分：可以自由填充，但每位数字不超过 limit
后缀部分：必须是字符串 s

算法流程：

对于长度小于 s.length 的数字，无法构成强大整数
对于长度等于 s.length 的数字，只需检查 s 本身是否在范围内
对于长度大于 s.length 的数字，使用数位 DP 计算前缀可能的方案数

这种方法避免了直接枚举，时间复杂度为 O(log n)，其中 n 为数字的位数。

代码实现

class Solution {
public:
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        return count(finish, limit, s) - count(start - 1, limit, s);
    }
    
private:
    long long count(long long x, int limit, const string& s) {
        if (x < 0) return 0;
        
        string num = to_string(x);
        int n = num.length();
        int m = s.length();
        
        if (n < m) return 0;
        if (n == m) return stoll(s) <= x ? 1 : 0;
        
        // 检查s是否满足limit条件
        for (char c : s) {
            if (c - '0' > limit) return 0;
        }
        
        vector<vector<long long>> memo(n, vector<long long>(2, -1));
        
        function<long long(int, bool)> dp = [&](int pos, bool tight) -> long long {
            if (pos == n - m) {
                // 检查剩余部分是否能匹配s
                string remaining = num.substr(pos);
                return (tight ? remaining >= s : true) && remaining.substr(0, m) == s ? 1 : 0;
            }
            
            if (memo[pos][tight] != -1) return memo[pos][tight];
            
            int maxDigit = tight ? num[pos] - '0' : limit;
            long long result = 0;
            
            for (int digit = 0; digit <= maxDigit; ++digit) {
                if (digit > limit) break;
                bool newTight = tight && (digit == maxDigit);
                result += dp(pos + 1, newTight);
            }
            
            return memo[pos][tight] = result;
        };
        
        return dp(0, true);
    }
};

class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        def count(x):
            if x < 0:
                return 0
            
            num_str = str(x)
            n = len(num_str)
            m = len(s)
            
            if n < m:
                return 0
            if n == m:
                return 1 if int(s) <= x else 0
            
            # 检查s是否满足limit条件
            if any(int(c) > limit for c in s):
                return 0
            
            memo = {}
            
            def dp(pos, tight):
                if pos == n - m:
                    # 检查剩余部分是否能匹配s
                    remaining = num_str[pos:]
                    if tight:
                        return 1 if remaining >= s else 0
                    else:
                        return 1
                
                if (pos, tight) in memo:
                    return memo[(pos, tight)]
                
                max_digit = int(num_str[pos]) if tight else limit
                result = 0
                
                for digit in range(min(max_digit, limit) + 1):
                    new_tight = tight and (digit == int(num_str[pos]))
                    result += dp(pos + 1, new_tight)
                
                memo[(pos, tight)] = result
                return result
            
            return dp(0, True)
        
        return count(finish) - count(start - 1)

public class Solution {
    public long NumberOfPowerfulInt(long start, long finish, int limit, string s) {
        return Count(finish, limit, s) - Count(start - 1, limit, s);
    }
    
    private long Count(long x, int limit, string s) {
        if (x < 0) return 0;
        
        string numStr = x.ToString();
        int n = numStr.Length;
        int m = s.Length;
        
        if (n < m) return 0;
        if (n == m) return long.Parse(s) <= x ? 1 : 0;
        
        // 检查s是否满足limit条件
        foreach (char c in s) {
            if (c - '0' > limit) return 0;
        }
        
        var memo = new Dictionary<(int, bool), long>();
        
        long Dp(int pos, bool tight) {
            if (pos == n - m) {
                string remaining = numStr.Substring(pos);
                if (tight) {
                    return string.Compare(remaining, s) >= 0 ? 1 : 0;
                } else {
                    return 1;
                }
            }
            
            if (memo.ContainsKey((pos, tight))) {
                return memo[(pos, tight)];
            }
            
            int maxDigit = tight ? numStr[pos] - '0' : limit;
            long result = 0;
            
            for (int digit = 0; digit <= Math.Min(maxDigit, limit); digit++) {
                bool newTight = tight && (digit == numStr[pos] - '0');
                result += Dp(pos + 1, newTight);
            }
            
            memo[(pos, tight)] = result;
            return result;
        }
        
        return Dp(0, true);
    }
}

var numberOfPowerfulInt = function(start, finish, limit, s) {
    function countPowerfulInts(upperBound) {
        const upperStr = upperBound.toString();
        const sLen = s.length;
        const upperLen = upperStr.length;
        
        if (upperLen < sLen) return 0;
        
        // Check if s itself is valid (all digits <= limit)
        for (let digit of s) {
            if (parseInt(digit) > limit) return 0;
        }
        
        const prefixLen = upperLen - sLen;
        let result = 0;
        
        // Count numbers with fewer digits than upperBound
        for (let len = sLen; len < upperLen; len++) {
            const prefixLenForThisLen = len - sLen;
            if (prefixLenForThisLen === 0) {
                result += 1;
            } else {
                result += Math.pow(limit + 1, prefixLenForThisLen);
            }
        }
        
        // Count numbers with same number of digits as upperBound
        if (prefixLen === 0) {
            // s has same length as upperBound
            if (s <= upperStr) result += 1;
        } else {
            // Generate prefix and check if resulting number <= upperBound
            const targetSuffix = s;
            const candidateStr = upperStr.slice(0, prefixLen) + targetSuffix;
            
            if (candidateStr <= upperStr) {
                // Check if prefix digits are valid
                let validPrefix = true;
                for (let i = 0; i < prefixLen; i++) {
                    if (parseInt(upperStr[i]) > limit) {
                        validPrefix = false;
                        break;
                    }
                }
                if (validPrefix) {
                    result += countValidPrefixes(upperStr.slice(0, prefixLen), limit);
                }
            } else {
                // Need to count all valid prefixes of length prefixLen
                result += Math.pow(limit + 1, prefixLen);
            }
        }
        
        return result;
    }
    
    function countValidPrefixes(maxPrefix, limit) {
        let count = 0;
        
        function dfs(pos, current, isLimit) {
            if (pos === maxPrefix.length) {
                return 1;
            }
            
            const maxDigit = isLimit ? parseInt(maxPrefix[pos]) : limit;
            let result = 0;
            
            for (let digit = 0; digit <= Math.min(maxDigit, limit); digit++) {
                result += dfs(pos + 1, current + digit.toString(), isLimit && (digit === parseInt(maxPrefix[pos])));
            }
            
            return result;
        }
        
        return dfs(0, "", true);
    }
    
    return countPowerfulInts(finish) - countPowerfulInts(start - 1);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(log n × limit)	n为finish的位数，每个位置最多有limit+1种选择
空间复杂度	O(log n)	递归深度和记忆化存储空间

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目