2376.统计特殊整数

链接：2376.统计特殊整数
难度：Hard
标签：数学、动态规划
简介：如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

题解 1 - python

• 编辑时间：2024-09-20
• 执行用时：349ms
• 内存消耗：35.45MB
• 编程语言：python
• 解法介绍：数位DP

class Solution:
    @cache
    def countSpecialNumbers(self, n: int, used: int = 0, first = True) -> int:
        if n < 10:
            res = 0
            # 如果是首位，不考虑0
            start = 1 if first else 0
            for v in range(start, n + 1):
                if not (used & (1 << v)):
                    res += 1
            return res
        arr = list(str(n))
        max_num = int(arr[0]) * 10 ** (len(arr) - 1)
        res = 0
        for v in range(int(arr[0])):
            if v == 0 and first: # 首位且0的话一定要
                res += self.countSpecialNumbers(10 ** (len(arr) - 1) - 1, used, first)
            elif not (used & (1 << v)): # 这个数字没遍历过时才要
                res += self.countSpecialNumbers(10 ** (len(arr) - 1) - 1, used | (1 << v), False)
        # 如果首位没有遍历过 且 不能存在两个0
        if not (used & (1 << int(arr[0]))) and len(str(n)) - len(str(n - max_num)) <= 2:
            next_used = used | (1 << int(arr[0]))
            # 如果中间存在一个0，就把0放进used
            if len(str(n - max_num)) != len(str(n)) - 1: next_used |= 1
            res += self.countSpecialNumbers(n - max_num, next_used, False)
        return res