Hard

题目描述

给你正整数 low、high 和 k。

如果一个数满足以下两个条件，那么它是美丽的：

  • 偶数位的数目等于奇数位的数目。
  • 这个数可以被 k 整除。

返回范围 [low, high] 中美丽整数的数目。

示例 1：

输入：low = 10, high = 20, k = 3
输出：2
解释：给定范围中有 2 个美丽整数：[12,18]。
- 12 是美丽的，因为它包含 1 个奇数位和 1 个偶数位，且可以被 k = 3 整除。
- 18 是美丽的，因为它包含 1 个奇数位和 1 个偶数位，且可以被 k = 3 整除。
另外我们可以看到：
- 16 不美丽，因为它不能被 k = 3 整除。
- 15 不美丽，因为它的偶数位和奇数位数目不相等。
可以证明给定范围中只有 2 个美丽整数。

示例 2：

输入：low = 1, high = 10, k = 1
输出：1
解释：给定范围中有 1 个美丽整数：[10]。
- 10 是美丽的，因为它包含 1 个奇数位和 1 个偶数位，且可以被 k = 1 整除。
可以证明给定范围中只有 1 个美丽整数。

示例 3：

输入：low = 5, high = 5, k = 2
输出：0
解释：给定范围中有 0 个美丽整数。
- 5 不美丽，因为它不能被 k = 2 整除，且偶数位和奇数位数目不相等。

约束条件：

  • 0 < low <= high <= 10^9
  • 0 < k <= 20

解题思路

这是一个典型的数位动态规划问题。我们需要统计在给定范围内同时满足两个条件的数字：奇偶数位个数相等且能被k整除。

核心思路： 使用数位DP求解区间问题，设计状态来记录当前构造数字的状态。我们定义 f(n) 表示从1到n中美丽整数的个数，答案为 f(high) - f(low-1)。

状态设计：

  • pos：当前填写到第几位
  • tight：是否贴着上界
  • started：是否开始填写非零数字
  • diff：奇数位个数减去偶数位个数的差值
  • mod：当前数字模k的余数

状态转移： 对于每一位，我们尝试填入0-9的数字，更新相应状态。奇数位增加diff，偶数位减少diff。最终检查diff是否为0且mod是否为0。

边界条件：

  • 当遍历完所有位时，检查diff是否为0（奇偶位个数相等）且mod是否为0（能被k整除）
  • 需要特别处理前导零的情况

这种方法的时间复杂度为O(log(high) × 2 × 2 × 20 × k)，可以有效处理给定的约束条件。

代码实现

class Solution {
public:
    int numberOfBeautifulIntegers(int low, int high, int k) {
        return count(high, k) - count(low - 1, k);
    }
    
private:
    string num;
    int K;
    int memo[11][2][2][21][21];
    
    int count(int x, int k) {
        if (x <= 0) return 0;
        num = to_string(x);
        K = k;
        memset(memo, -1, sizeof(memo));
        return dp(0, 1, 0, 10, 0);
    }
    
    int dp(int pos, int tight, int started, int diff, int mod) {
        if (pos == num.size()) {
            return started && diff == 10 && mod == 0;
        }
        
        if (memo[pos][tight][started][diff][mod] != -1) {
            return memo[pos][tight][started][diff][mod];
        }
        
        int limit = tight ? num[pos] - '0' : 9;
        int result = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            int newTight = tight && (digit == limit);
            int newStarted = started || (digit > 0);
            int newDiff = diff;
            int newMod = mod;
            
            if (newStarted) {
                if (digit % 2 == 0) {
                    newDiff--;
                } else {
                    newDiff++;
                }
                newMod = (mod * 10 + digit) % K;
            }
            
            result += dp(pos + 1, newTight, newStarted, newDiff, newMod);
        }
        
        return memo[pos][tight][started][diff][mod] = result;
    }
};

class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
        def count(x):
            if x <= 0:
                return 0
            
            s = str(x)
            n = len(s)
            memo = {}
            
            def dp(pos, tight, started, diff, mod):
                if pos == n:
                    return 1 if started and diff == 0 and mod == 0 else 0
                
                if (pos, tight, started, diff, mod) in memo:
                    return memo[(pos, tight, started, diff, mod)]
                
                limit = int(s[pos]) if tight else 9
                result = 0
                
                for digit in range(limit + 1):
                    new_tight = tight and digit == limit
                    new_started = started or digit > 0
                    new_diff = diff
                    new_mod = mod
                    
                    if new_started:
                        if digit % 2 == 0:
                            new_diff -= 1
                        else:
                            new_diff += 1
                        new_mod = (mod * 10 + digit) % k
                    
                    result += dp(pos + 1, new_tight, new_started, new_diff, new_mod)
                
                memo[(pos, tight, started, diff, mod)] = result
                return result
            
            return dp(0, True, False, 0, 0)
        
        return count(high) - count(low - 1)

public class Solution {
    private string num;
    private int k;
    private Dictionary<string, int> memo;
    
    public int NumberOfBeautifulIntegers(int low, int high, int k) {
        return Count(high, k) - Count(low - 1, k);
    }
    
    private int Count(int x, int k) {
        if (x <= 0) return 0;
        
        this.num = x.ToString();
        this.k = k;
        this.memo = new Dictionary<string, int>();
        
        return Dp(0, true, false, 0, 0);
    }
    
    private int Dp(int pos, bool tight, bool started, int diff, int mod) {
        if (pos == num.Length) {
            return (started && diff == 0 && mod == 0) ? 1 : 0;
        }
        
        string key = $"{pos},{tight},{started},{diff},{mod}";
        if (memo.ContainsKey(key)) {
            return memo[key];
        }
        
        int limit = tight ? num[pos] - '0' : 9;
        int result = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            bool newTight = tight && digit == limit;
            bool newStarted = started || digit > 0;
            int newDiff = diff;
            int newMod = mod;
            
            if (newStarted) {
                if (digit % 2 == 0) {
                    newDiff--;
                } else {
                    newDiff++;
                }
                newMod = (mod * 10 + digit) % k;
            }
            
            result += Dp(pos + 1, newTight, newStarted, newDiff, newMod);
        }
        
        memo[key] = result;
        return result;
    }
}

var numberOfBeautifulIntegers = function(low, high, k) {
    function digitDP(num) {
        const s = num.toString();
        const n = s.length;
        const memo = new Map();
        
        function dp(pos, isLimit, isNum, evenCount, oddCount, remainder) {
            if (pos === n) {
                return isNum && evenCount === oddCount && remainder === 0 ? 1 : 0;
            }
            
            const key = `${pos}-${isLimit}-${isNum}-${evenCount}-${oddCount}-${remainder}`;
            if (memo.has(key)) {
                return memo.get(key);
            }
            
            let result = 0;
            
            if (!isNum) {
                result += dp(pos + 1, false, false, evenCount, oddCount, remainder);
            }
            
            const start = isNum ? 0 : 1;
            const end = isLimit ? parseInt(s[pos]) : 9;
            
            for (let digit = start; digit <= end; digit++) {
                const newEvenCount = evenCount + (digit % 2 === 0 ? 1 : 0);
                const newOddCount = oddCount + (digit % 2 === 1 ? 1 : 0);
                const newRemainder = (remainder * 10 + digit) % k;
                const newIsLimit = isLimit && digit === parseInt(s[pos]);
                
                result += dp(pos + 1, newIsLimit, true, newEvenCount, newOddCount, newRemainder);
            }
            
            memo.set(key, result);
            return result;
        }
        
        return dp(0, true, false, 0, 0, 0);
    }
    
    return digitDP(high) - digitDP(low - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型C++PythonC#JavaScript
时间复杂度O(log(high) × k)O(log(high) × k)O(log(high) × k)O(log(high) × k)
空间复杂度O(log(high) × k)O(log(high) × k)O(log(high) × k)O(log(high) × k)

相关题目