Medium

题目描述

给你一个正整数 n。

对于从 1 到 n 的每个整数 x，我们写下通过移除 x 的十进制表示中所有零得到的整数。

返回一个整数，表示写下的不同整数的数量。

示例 1：

输入：n = 10

输出：9

解释：

我们写下的整数是 1, 2, 3, 4, 5, 6, 7, 8, 9, 1。有 9 个不同的整数（1, 2, 3, 4, 5, 6, 7, 8, 9）。

示例 2：

输入：n = 3

输出：3

解释：

我们写下的整数是 1, 2, 3。有 3 个不同的整数（1, 2, 3）。

约束条件：

  • 1 <= n <= 10^15

提示：

  • 构建小于等于 n 且仅使用数字 1 到 9 的整数
  • 使用数学方法或数位 DP 来统计这样的整数

解题思路

这道题的关键洞察是：移除零后的结果实际上就是只包含数字1-9的数。

我们需要统计有多少个由数字1-9组成的正整数，且这些整数小于等于移除n中所有零后的结果。

解题思路：

  1. 数位DP方法：我们可以使用数位动态规划来解决这个问题。状态定义为当前位置、是否受到上界限制、是否已经开始填数字。

  2. 直接计算方法：

    • 首先将n转换为字符串，移除所有零得到目标数字
    • 对于长度为k的数字，我们可以直接计算有多少个由1-9组成的k位数
    • 长度小于k的数字：1位数有9个(1-9)，2位数有9×9=81个，以此类推
    • 长度等于k的数字：需要按位比较，确保不超过目标数字

  3. 优化思路：考虑到约束条件中n可能很大(10^15)，我们需要高效的计算方法。

最优解法是使用数位DP，因为它能够准确处理边界情况并且时间复杂度合理。

代码实现

class Solution {
public:
    long long countDistinct(long long n) {
        string s = to_string(n);
        string filtered = "";
        for (char c : s) {
            if (c != '0') filtered += c;
        }
        
        int len = filtered.length();
        vector<vector<long long>> dp(len + 1, vector<long long>(2, 0));
        
        function<long long(int, bool, bool)> dfs = [&](int pos, bool tight, bool started) -> long long {
            if (pos == len) return started ? 1 : 0;
            
            if (!tight && started && dp[pos][0] != 0) return dp[pos][0];
            if (!tight && !started && dp[pos][1] != 0) return dp[pos][1];
            
            long long result = 0;
            int limit = tight ? (filtered[pos] - '0') : 9;
            
            if (!started) {
                result += dfs(pos + 1, false, false); // 不填数字
            }
            
            for (int digit = 1; digit <= limit; digit++) {
                bool newTight = tight && (digit == limit);
                result += dfs(pos + 1, newTight, true);
            }
            
            if (!tight) {
                dp[pos][started ? 0 : 1] = result;
            }
            
            return result;
        };
        
        return dfs(0, true, false);
    }
};

class Solution:
    def countDistinct(self, n: int) -> int:
        s = str(n)
        filtered = ''.join(c for c in s if c != '0')
        
        if not filtered:
            return 0
        
        length = len(filtered)
        memo = {}
        
        def dfs(pos, tight, started):
            if pos == length:
                return 1 if started else 0
            
            if (pos, tight, started) in memo:
                return memo[(pos, tight, started)]
            
            result = 0
            limit = int(filtered[pos]) if tight else 9
            
            if not started:
                result += dfs(pos + 1, False, False)
            
            for digit in range(1, limit + 1):
                new_tight = tight and (digit == limit)
                result += dfs(pos + 1, new_tight, True)
            
            memo[(pos, tight, started)] = result
            return result
        
        return dfs(0, True, False)

public class Solution {
    public long CountDistinct(long n) {
        string s = n.ToString();
        string filtered = "";
        foreach (char c in s) {
            if (c != '0') filtered += c;
        }
        
        if (string.IsNullOrEmpty(filtered)) return 0;
        
        int length = filtered.Length;
        Dictionary<(int, bool, bool), long> memo = new Dictionary<(int, bool, bool), long>();
        
        long Dfs(int pos, bool tight, bool started) {
            if (pos == length) return started ? 1 : 0;
            
            var key = (pos, tight, started);
            if (memo.ContainsKey(key)) return memo[key];
            
            long result = 0;
            int limit = tight ? (filtered[pos] - '0') : 9;
            
            if (!started) {
                result += Dfs(pos + 1, false, false);
            }
            
            for (int digit = 1; digit <= limit; digit++) {
                bool newTight = tight && (digit == limit);
                result += Dfs(pos + 1, newTight, true);
            }
            
            memo[key] = result;
            return result;
        }
        
        return Dfs(0, true, false);
    }
}

var countDistinct = function(n) {
    const seen = new Set();
    
    function removeZeros(num) {
        return parseInt(num.toString().replace(/0/g, ''));
    }
    
    for (let i = 1; i <= n; i++) {
        seen.add(removeZeros(i));
    }
    
    return seen.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(d × 2 × 2 × 9) = O(d)，其中 d 是移除零后数字的位数
空间复杂度O(d) 用于记忆化存储和递归栈空间