3519. 计算非递减数字的数量

Hard

题目描述

给你两个用字符串表示的整数 l 和 r，以及一个整数 b。返回在闭区间 [l, r] 内，当以 b 进制表示时数字非递减的整数的数量。

如果一个整数从左到右读取时（从最高有效位到最低有效位），每一位都大于或等于前一位，则认为该整数的数字是非递减的。

由于答案可能很大，请返回结果对 10^9 + 7 取模后的值。

示例 1：

输入：l = "23", r = "28", b = 8
输出：3
解释：
从 23 到 28 在 8 进制下的数字是：27, 30, 31, 32, 33, 和 34。
其中，27, 33, 和 34 具有非递减数字。因此，输出是 3。

示例 2：

输入：l = "2", r = "7", b = 2
输出：2
解释：
从 2 到 7 在 2 进制下的数字是：10, 11, 100, 101, 110, 和 111。
其中，11 和 111 具有非递减数字。因此，输出是 2。

约束条件：

1 <= l.length <= r.length <= 100
2 <= b <= 10
l 和 r 只包含数字
l 表示的值小于或等于 r 表示的值
l 和 r 不包含前导零

提示：

使用数位动态规划。

解题思路

这是一道典型的数位动态规划问题。我们需要统计在给定范围内，以 b 进制表示时数字非递减的数的个数。

核心思路：

数位 DP 框架：使用数位 DP 来处理区间 [l, r] 的计数问题，通过 count(r) - count(l-1) 来获得答案。
状态设计：
- pos：当前处理到第几位
- lastDigit：前一位的数字（确保非递减）
- tight：是否受到上界限制
- started：是否已经开始填充非零数字
转移过程：
- 对于每一位，我们可以选择从 lastDigit 到 b-1 的任意数字（保证非递减）
- 如果当前位受到 tight 限制，则最大只能选择到原数字的对应位
- 特别处理前导零的情况
进制转换：需要将输入的十进制字符串转换为 b 进制表示，然后进行 DP 计算。

算法步骤：

实现字符串减一操作（用于计算 l-1）
将十进制字符串转换为 b 进制数组
使用记忆化数位 DP 计算满足条件的数的个数
返回 count(r) - count(l-1)

时间复杂度主要取决于数字的位数和进制，由于有记忆化，每个状态只计算一次。

代码实现

class Solution {
    int MOD = 1e9 + 7;
    vector<vector<vector<vector<int>>>> memo;
    vector<int> digits;
    int base;
    
public:
    int countNumbers(string l, string r, int b) {
        base = b;
        
        // 计算 count(r) - count(l-1)
        int countR = solve(r, b);
        string l_minus_1 = subtractOne(l);
        int countL = l_minus_1.empty() ? 0 : solve(l_minus_1, b);
        
        return (countR - countL + MOD) % MOD;
    }
    
private:
    int solve(string num, int b) {
        // 转换为 b 进制
        digits = convertToBase(num, b);
        int n = digits.size();
        
        // 重置记忆化数组
        memo.assign(n, vector<vector<vector<int>>>(b, vector<vector<int>>(2, vector<int>(2, -1))));
        
        return dp(0, 0, 1, 0);
    }
    
    int dp(int pos, int lastDigit, int tight, int started) {
        if (pos == digits.size()) {
            return started;
        }
        
        if (memo[pos][lastDigit][tight][started] != -1) {
            return memo[pos][lastDigit][tight][started];
        }
        
        int limit = tight ? digits[pos] : base - 1;
        int result = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            int newTight = tight && (digit == limit);
            int newStarted = started || (digit > 0);
            int newLastDigit = newStarted ? digit : 0;
            
            // 如果已经开始且当前数字小于上一个数字，跳过
            if (newStarted && digit < lastDigit) {
                continue;
            }
            
            result = (result + dp(pos + 1, newLastDigit, newTight, newStarted)) % MOD;
        }
        
        return memo[pos][lastDigit][tight][started] = result;
    }
    
    vector<int> convertToBase(string num, int b) {
        vector<int> result;
        while (!num.empty() && num != "0") {
            int remainder = 0;
            string newNum = "";
            
            for (char c : num) {
                int current = remainder * 10 + (c - '0');
                if (!newNum.empty() || current / b > 0) {
                    newNum += to_string(current / b);
                }
                remainder = current % b;
            }
            
            result.push_back(remainder);
            num = newNum.empty() ? "0" : newNum;
        }
        
        reverse(result.begin(), result.end());
        return result.empty() ? vector<int>{0} : result;
    }
    
    string subtractOne(string num) {
        int i = num.length() - 1;
        while (i >= 0 && num[i] == '0') {
            num[i] = '9';
            i--;
        }
        
        if (i >= 0) {
            num[i]--;
            if (num[0] == '0' && num.length() > 1) {
                return num.substr(1);
            }
        } else {
            return "";
        }
        
        return num;
    }
};

class Solution:
    def countNumbers(self, l: str, r: str, b: int) -> int:
        MOD = 10**9 + 7
        
        def subtract_one(num_str):
            num = list(num_str)
            i = len(num) - 1
            while i >= 0 and num[i] == '0':
                num[i] = '9'
                i -= 1
            
            if i >= 0:
                num[i] = str(int(num[i]) - 1)
                result = ''.join(num).lstrip('0')
                return result if result else ""
            return ""
        
        def convert_to_base(num_str, base):
            if num_str == "0":
                return [0]
            
            result = []
            num = num_str
            
            while num and num != "0":
                remainder = 0
                new_num = ""
                
                for c in num:
                    current = remainder * 10 + int(c)
                    if new_num or current // base > 0:
                        new_num += str(current // base)
                    remainder = current % base
                
                result.append(remainder)
                num = new_num if new_num else "0"
            
            return result[::-1]
        
        def solve(num_str, base):
            digits = convert_to_base(num_str, base)
            n = len(digits)
            
            from functools import lru_cache
            
            @lru_cache(None)
            def dp(pos, last_digit, tight, started):
                if pos == n:
                    return int(started)
                
                limit = digits[pos] if tight else base - 1
                result = 0
                
                for digit in range(limit + 1):
                    new_tight = tight and (digit == limit)
                    new_started = started or (digit > 0)
                    new_last_digit = digit if new_started else 0
                    
                    if new_started and digit < last_digit:
                        continue
                    
                    result = (result + dp(pos + 1, new_last_digit, new_tight, new_started)) % MOD
                
                return result
            
            return dp(0, 0, True, False)
        
        count_r = solve(r, b)
        l_minus_1 = subtract_one(l)
        count_l = 0 if not l_minus_1 else solve(l_minus_1, b)
        
        return (count_r - count_l + MOD) % MOD

public class Solution {
    private const int MOD = 1000000007;
    private int[,,,] memo;
    private int[] digits;
    private int baseNum;
    
    public int CountNumbers(string l, string r, int b) {
        int countR = Solve(r, b);
        string lMinus1 = SubtractOne(l);
        int countL = string.IsNullOrEmpty(lMinus1) ? 0 : Solve(lMinus1, b);
        
        return (countR - countL + MOD) % MOD;
    }
    
    private int Solve(string num, int b) {
        baseNum = b;
        digits = ConvertToBase(num, b);
        int n = digits.Length;
        
        memo = new int[n, b, 2, 2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < b; j++) {
                for (int k = 0; k < 2; k++) {
                    for (int l = 0; l < 2; l++) {
                        memo[i, j, k, l] = -1;
                    }
                }
            }
        }
        
        return Dp(0, 0, 1, 0);
    }
    
    private int Dp(int pos, int lastDigit, int tight, int started) {
        if (pos == digits.Length) {
            return started;
        }
        
        if (memo[pos, lastDigit, tight, started] != -1) {
            return memo[pos, lastDigit, tight, started];
        }
        
        int limit = tight == 1 ? digits[pos] : baseNum - 1;
        int result = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            int newTight = (tight == 1 && digit == limit) ? 1 : 0;
            int newStarted = (started == 1 || digit > 0) ? 1 : 0;
            int newLastDigit = newStarted == 1 ? digit : 0;
            
            if (newStarted == 1 && digit < lastDigit) {
                continue;
            }
            
            result = (result + Dp(pos + 1, newLastDigit, newTight, newStarted)) % MOD;
        }
        
        return memo[pos, lastDigit, tight, started] = result;
    }
    
    private int[] ConvertToBase(string num, int b) {
        if (num == "0") return new int[] { 0 };
        
        var result = new List<int>();
        
        while (!string.IsNullOrEmpty(num) && num != "0") {
            int remainder = 0;
            string newNum = "";
            
            foreach (char c in num) {
                int current = remainder * 10 + (c - '0');
                if (!string.IsNullOrEmpty(newNum) || current / b > 0) {
                    newNum += (current / b).ToString();
                }
                remainder = current % b;
            }
            
            result.Add(remainder);
            num = string.IsNullOrEmpty(newNum) ? "0" : newNum;
        }
        
        result.Reverse();
        return result.Count == 0 ? new int[] { 0 } : result.ToArray();
    }
    
    private string SubtractOne(string num) {
        char[] chars = num.ToCharArray();
        int i = chars.Length - 1;
        
        while (i >= 0 && chars[i] == '0') {
            chars[i] = '9';
            i--;
        }
        
        if (i >= 0) {
            chars[i]--;
            string result = new string(chars).TrimStart('0');
            return string.IsNullOrEmpty(result) ? "" : result;
        }
        
        return "";
    }
}

/**
 * @param {string} l
 * @param {string} r
 * @param {number} b
 * @return {number}
 */
var countNumbers = function(l, r, b) {
    const MOD = 1e9 + 7;
    
    function subtractOne(numStr) {
        const num = numStr.split('');
        let i = num.length - 1;
        
        while (i >= 0 && num[i]

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

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目