2801. 统计范围内的步进数字

Hard

题目描述

给你两个以字符串形式表示的正整数 low 和 high，找出在闭区间 [low, high] 范围内步进数字的数量。

步进数字是一个整数，其中所有相邻数字的绝对差值恰好为 1。

返回在闭区间 [low, high] 范围内步进数字的数量。由于答案可能很大，请返回答案对 10^9 + 7 取模的结果。

注意：步进数字不能有前导零。

示例 1：

输入：low = "1", high = "11"
输出：10
解释：范围 [1,11] 内的步进数字有 1, 2, 3, 4, 5, 6, 7, 8, 9 和 10。范围内总共有 10 个步进数字。因此，输出为 10。

示例 2：

输入：low = "90", high = "101"
输出：2
解释：范围 [90,101] 内的步进数字有 98 和 101。范围内总共有 2 个步进数字。因此，输出为 2。

提示：

1 <= int(low) <= int(high) < 10^100
1 <= low.length, high.length <= 100
low 和 high 只含数字
low 和 high 都没有前导零

解题思路

这道题需要统计指定范围内的步进数字个数。步进数字的特点是相邻位数字的绝对差值恰好为1。

核心思路： 使用经典的数位DP（数字动态规划）来解决。由于要求范围 [low, high] 内的个数，我们可以计算 countSteppingNumbers(high) - countSteppingNumbers(low-1)。

数位DP状态定义：

pos: 当前处理到的位置
last: 上一位的数字
isLimit: 当前是否受到上界限制
isStart: 是否还在前导零状态

转移过程：

如果还在前导零状态，可以继续放0（保持前导零状态）或放1-9开始构造数字
如果已经开始构造数字，下一位只能放 last±1 且在 [0,9] 范围内的数字
需要特别处理边界情况和模运算

优化细节：

使用记忆化避免重复计算
对于减1操作，需要特别处理字符串形式的大整数减法
合理处理边界条件，如 low=“0” 的情况

这个解法的时间复杂度主要取决于数字的位数和状态数量，对于长度为n的数字，复杂度约为 O(n × 10 × 2 × 2)。

代码实现

class Solution {
private:
    static const int MOD = 1000000007;
    string num;
    vector<vector<vector<vector<int>>>> memo;
    
    int dfs(int pos, int last, bool isLimit, bool isStart) {
        if (pos == num.size()) {
            return isStart ? 0 : 1;
        }
        
        if (!isLimit && !isStart && memo[pos][last][0][0] != -1) {
            return memo[pos][last][0][0];
        }
        
        int limit = isLimit ? (num[pos] - '0') : 9;
        long long result = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            bool newIsStart = isStart && (digit == 0);
            bool newIsLimit = isLimit && (digit == limit);
            
            if (isStart) {
                if (digit == 0) {
                    result = (result + dfs(pos + 1, 0, newIsLimit, true)) % MOD;
                } else {
                    result = (result + dfs(pos + 1, digit, newIsLimit, false)) % MOD;
                }
            } else {
                if (abs(digit - last) == 1) {
                    result = (result + dfs(pos + 1, digit, newIsLimit, false)) % MOD;
                }
            }
        }
        
        if (!isLimit && !isStart) {
            memo[pos][last][0][0] = result;
        }
        
        return result;
    }
    
    int countHelper(const string& s) {
        if (s == "0") return 0;
        
        num = s;
        memo.assign(s.size(), vector<vector<vector<int>>>(10, vector<vector<int>>(2, vector<int>(2, -1))));
        return dfs(0, 0, true, true);
    }
    
    string subtract1(const string& s) {
        if (s == "0") return "-1";
        
        string result = s;
        int i = result.size() - 1;
        
        while (i >= 0 && result[i] == '0') {
            result[i] = '9';
            i--;
        }
        
        if (i >= 0) {
            result[i]--;
        }
        
        // Remove leading zeros
        int start = 0;
        while (start < result.size() && result[start] == '0') {
            start++;
        }
        
        if (start == result.size()) return "0";
        return result.substr(start);
    }
    
public:
    int countSteppingNumbers(string low, string high) {
        int highCount = countHelper(high);
        string lowMinus1 = subtract1(low);
        int lowCount = (lowMinus1 == "-1") ? 0 : countHelper(lowMinus1);
        
        return (highCount - lowCount + MOD) % MOD;
    }
};

class Solution:
    def countSteppingNumbers(self, low: str, high: str) -> int:
        MOD = 10**9 + 7
        
        def count_helper(s):
            if s == "0":
                return 0
            
            n = len(s)
            memo = {}
            
            def dfs(pos, last, is_limit, is_start):
                if pos == n:
                    return 0 if is_start else 1
                
                state = (pos, last, is_limit, is_start)
                if state in memo:
                    return memo[state]
                
                limit = int(s[pos]) if is_limit else 9
                result = 0
                
                for digit in range(limit + 1):
                    new_is_start = is_start and digit == 0
                    new_is_limit = is_limit and digit == limit
                    
                    if is_start:
                        if digit == 0:
                            result = (result + dfs(pos + 1, 0, new_is_limit, True)) % MOD
                        else:
                            result = (result + dfs(pos + 1, digit, new_is_limit, False)) % MOD
                    else:
                        if abs(digit - last) == 1:
                            result = (result + dfs(pos + 1, digit, new_is_limit, False)) % MOD
                
                memo[state] = result
                return result
            
            return dfs(0, 0, True, True)
        
        def subtract_1(s):
            if s == "0":
                return "-1"
            
            result = list(s)
            i = len(result) - 1
            
            while i >= 0 and result[i] == '0':
                result[i] = '9'
                i -= 1
            
            if i >= 0:
                result[i] = str(int(result[i]) - 1)
            
            # Remove leading zeros
            result_str = ''.join(result).lstrip('0')
            return result_str if result_str else "0"
        
        high_count = count_helper(high)
        low_minus_1 = subtract_1(low)
        low_count = 0 if low_minus_1 == "-1" else count_helper(low_minus_1)
        
        return (high_count - low_count) % MOD

public class Solution {
    private const int MOD = 1000000007;
    private string num;
    private Dictionary<(int, int, bool, bool), int> memo;
    
    private int Dfs(int pos, int last, bool isLimit, bool isStart) {
        if (pos == num.Length) {
            return isStart ? 0 : 1;
        }
        
        var state = (pos, last, isLimit, isStart);
        if (memo.ContainsKey(state)) {
            return memo[state];
        }
        
        int limit = isLimit ? (num[pos] - '0') : 9;
        long result = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            bool newIsStart = isStart && (digit == 0);
            bool newIsLimit = isLimit && (digit == limit);
            
            if (isStart) {
                if (digit == 0) {
                    result = (result + Dfs(pos + 1, 0, newIsLimit, true)) % MOD;
                } else {
                    result = (result + Dfs(pos + 1, digit, newIsLimit, false)) % MOD;
                }
            } else {
                if (Math.Abs(digit - last) == 1) {
                    result = (result + Dfs(pos + 1, digit, newIsLimit, false)) % MOD;
                }
            }
        }
        
        memo[state] = (int)result;
        return (int)result;
    }
    
    private int CountHelper(string s) {
        if (s == "0") return 0;
        
        num = s;
        memo = new Dictionary<(int, int, bool, bool), int>();
        return Dfs(0, 0, true, true);
    }
    
    private string Subtract1(string s) {
        if (s == "0") return "-1";
        
        char[] result = s.ToCharArray();
        int i = result.Length - 1;
        
        while (i >= 0 && result[i] == '0') {
            result[i] = '9';
            i--;
        }
        
        if (i >= 0) {
            result[i] = (char)(result[i] - 1);
        }
        
        string resultStr = new string(result).TrimStart('0');
        return string.IsNullOrEmpty(resultStr) ? "0" : resultStr;
    }
    
    public int CountSteppingNumbers(string low, string high) {
        int highCount = CountHelper(high);
        string lowMinus1 = Subtract1(low);
        int lowCount = lowMinus1 == "-1" ? 0 : CountHelper(lowMinus1);
        
        return (highCount - lowCount + MOD) % MOD;
    }
}

var countSteppingNumbers = function(low, high) {
    const MOD = 1000000007;
    
    function countSteppingNumbersUpTo(num) {
        const n = num.length;
        const memo = {};
        
        function dp(pos, lastDigit, tight, started) {
            if (pos === n) {
                return started ? 1 : 0;
            }
            
            const key = `${pos}-${lastDigit}-${tight}-${started}`;
            if (key in memo) return memo[key];
            
            const limit = tight ? parseInt(num[pos]) : 9;
            let result = 0;
            
            for (let digit = 0; digit <= limit; digit++) {
                const newTight = tight && (digit === limit);
                const newStarted = started || (digit > 0);
                
                if (!started && digit === 0) {
                    result = (result + dp(pos + 1, -1, newTight, newStarted)) % MOD;
                } else if (!started || Math.abs(digit - lastDigit) === 1) {
                    result = (result + dp(pos + 1, digit, newTight, newStarted)) % MOD;
                }
            }
            
            return memo[key] = result;
        }
        
        return dp(0, -1, true, false);
    }
    
    function isSteppingNumber(s) {
        for (let i = 1; i < s.length; i++) {
            if (Math.abs(parseInt(s[i]) - parseInt(s[i-1])) !== 1) {
                return false;
            }
        }
        return true;
    }
    
    function subtract(a, b) {
        let result = "";
        let borrow = 0;
        let i = a.length - 1;
        let j = b.length - 1;
        
        while (i >= 0 || j >= 0) {
            let digitA = i >= 0 ? parseInt(a[i]) : 0;
            let digitB = j >= 0 ? parseInt(b[j]) : 0;
            
            digitA -= borrow;
            if (digitA < digitB) {
                digitA += 10;
                borrow = 1;
            } else {
                borrow = 0;
            }
            
            result = (digitA - digitB) + result;
            i--;
            j--;
        }
        
        result = result.replace(/^0+/, "");
        return result === "" ? "0" : result;
    }
    
    const countHigh = countSteppingNumbersUpTo(high);
    const lowMinus1 = subtract(low, "1");
    const countLow = lowMinus1 === "0" || lowMinus1 === "" ? 0 : countSteppingNumbersUpTo(lowMinus1);
    
    return (countHigh - countLow + MOD) % MOD;
};

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

复杂度分析

复杂度类型	大小
时间复杂度	O(n × 10 × 2 × 2) = O(n)
空间复杂度	O(n × 10 × 2 × 2) = O(n)

其中 n 是输入字符串的长度。数位DP的状态数量为位置数×数字种类×边界状态×前导零状态，通过记忆化避免重复计算，时间复杂度线性于字符串长度。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目