Hard

题目描述

如果一个正整数的所有数位都不相同，我们称它为特殊整数。

给定一个正整数 n，返回区间 [1, n] 内特殊整数的数目。

示例 1：

输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。因此，特殊整数有 19 个。

示例 2：

输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。

示例 3：

输入：n = 135
输出：110
解释：从 1 到 135 共有 110 个特殊整数。
一些不是特殊整数的例子：22、114 和 131。

提示：

  • 1 <= n <= 2 * 10^9

提示：

  • 尝试考虑动态规划。
  • 使用数位动态规划的思想来构建数字，另外使用位掩码来记录你在构建数字时已经使用了哪些数位。

解题思路

这是一道典型的数位动态规划问题。我们需要统计从1到n中所有数位不重复的数字个数。

核心思路：

  1. 数位DP：逐位构建数字，使用状态记录已使用的数位
  2. 状态设计：dp[pos][mask][is_limit][is_num]
    • pos：当前处理的位置
    • mask：位掩码，记录已使用的数位（0-9）
    • is_limit：是否受到上界限制
    • is_num：是否已经开始填数字（处理前导零）

具体实现：

  • 当is_num=false时，可以选择跳过当前位（前导零）或开始填数字
  • 当is_num=true时，必须填入数字，且不能与之前使用的数位重复
  • 使用记忆化搜索优化重复子问题

时间复杂度分析：

  • 状态数：位数 × 2^10 × 2 × 2 = O(log n × 1024)
  • 总复杂度：O(log n × 2^10)

这种解法能够高效处理大数范围的数位DP问题，是此类题目的标准解法。

代码实现

class Solution {
public:
    int countSpecialNumbers(int n) {
        string s = to_string(n);
        int m = s.length();
        vector<vector<vector<vector<int>>>> memo(m, vector<vector<vector<int>>>(1024, vector<vector<int>>(2, vector<int>(2, -1))));
        
        function<int(int, int, bool, bool)> dfs = [&](int pos, int mask, bool is_limit, bool is_num) -> int {
            if (pos == m) {
                return is_num;
            }
            
            if (memo[pos][mask][is_limit][is_num] != -1) {
                return memo[pos][mask][is_limit][is_num];
            }
            
            int res = 0;
            if (!is_num) {
                res = dfs(pos + 1, mask, false, false);
            }
            
            int up = is_limit ? s[pos] - '0' : 9;
            int low = is_num ? 0 : 1;
            
            for (int d = low; d <= up; d++) {
                if ((mask >> d) & 1) continue;
                res += dfs(pos + 1, mask | (1 << d), is_limit && d == up, true);
            }
            
            return memo[pos][mask][is_limit][is_num] = res;
        };
        
        return dfs(0, 0, true, false);
    }
};

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        s = str(n)
        m = len(s)
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dfs(pos, mask, is_limit, is_num):
            if pos == m:
                return int(is_num)
            
            res = 0
            if not is_num:
                res = dfs(pos + 1, mask, False, False)
            
            up = int(s[pos]) if is_limit else 9
            low = 0 if is_num else 1
            
            for d in range(low, up + 1):
                if (mask >> d) & 1:
                    continue
                res += dfs(pos + 1, mask | (1 << d), is_limit and d == up, True)
            
            return res
        
        return dfs(0, 0, True, False)

public class Solution {
    private int[,,,] memo;
    private string s;
    private int m;
    
    public int CountSpecialNumbers(int n) {
        s = n.ToString();
        m = s.Length;
        memo = new int[m, 1024, 2, 2];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 1024; j++) {
                for (int k = 0; k < 2; k++) {
                    for (int l = 0; l < 2; l++) {
                        memo[i, j, k, l] = -1;
                    }
                }
            }
        }
        
        return Dfs(0, 0, 1, 0);
    }
    
    private int Dfs(int pos, int mask, int isLimit, int isNum) {
        if (pos == m) {
            return isNum;
        }
        
        if (memo[pos, mask, isLimit, isNum] != -1) {
            return memo[pos, mask, isLimit, isNum];
        }
        
        int res = 0;
        if (isNum == 0) {
            res = Dfs(pos + 1, mask, 0, 0);
        }
        
        int up = isLimit == 1 ? s[pos] - '0' : 9;
        int low = isNum == 1 ? 0 : 1;
        
        for (int d = low; d <= up; d++) {
            if ((mask >> d & 1) == 1) continue;
            res += Dfs(pos + 1, mask | (1 << d), isLimit == 1 && d == up ? 1 : 0, 1);
        }
        
        return memo[pos, mask, isLimit, isNum] = res;
    }
}

var countSpecialNumbers = function(n) {
    const s = n.toString();
    const len = s.length;
    const memo = new Map();
    
    function dp(pos, mask, isLimit, hasStarted) {
        if (pos === len) {
            return hasStarted ? 1 : 0;
        }
        
        const key = `${pos}-${mask}-${isLimit}-${hasStarted}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        let res = 0;
        const limit = isLimit ? parseInt(s[pos]) : 9;
        
        for (let digit = 0; digit <= limit; digit++) {
            if (hasStarted && (mask & (1 << digit))) {
                continue;
            }
            
            const newMask = hasStarted || digit > 0 ? mask | (1 << digit) : mask;
            const newIsLimit = isLimit && digit === limit;
            const newHasStarted = hasStarted || digit > 0;
            
            res += dp(pos + 1, newMask, newIsLimit, newHasStarted);
        }
        
        memo.set(key, res);
        return res;
    }
    
    return dp(0, 0, true, false);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(log n × 2^10)
空间复杂度O(log n × 2^10)

说明：

  • 时间复杂度：位数为 log n，状态掩码有 2^10 种可能，加上其他状态维度，总体为 O(log n × 2^10)
  • 空间复杂度：记忆化存储的状态空间大小，同时间复杂度

相关题目