经典算法：不大于N的特殊数字

• 经典算法：不大于N的特殊数字
  • 1. 题目描述
  • 2. 算法思路
  • 3. 代码实现

1. 题目描述

这个题目其实来自于Leetcode的以下两道题目：

1. 1012. Numbers With Repeated Digits
2. 2376. Count Special Integers

问题的主体就是，给出一个确定的整数$n$，求取所有不大于$n$的，且各个位数都不相同的数的个数。

或者相反，求出存在至少有两位数字相同的数字的个数，不过这两个问题是互补的，所以我们只需要考虑上一个问题即可。

2. 算法思路

这一题的算法思路算是一个相对复杂一点的分类讨论：

1. 首先，如果生成的数字位数小于$n$，那事实上就是一个简单的排列组合问题，除了首数字不能为$0$之外，就没有什么特殊情况了；
2. 然后要考虑一下位数相同的情况，此时又需要分两类进行考察
   1. 首先是第一位比目标数小的情况，此时后面就是一个完全的排列问题，还是比较好处理的；
   2. 然后就是临界情况，即第一位与目标值相同的情况，此时我们就需要考察第二位的情况，然后此时就又一次回到了这一段开头的情况。
3. 另外还有一个比较特殊的情况就是如果这个数存在两个位数是相同的情况下，此时跳出循环即可。

3. 代码实现

具体到实现上，我们摘录某位大佬的代码实现如下：

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        nums = [int(i) for i in str(n+1)] 
        d = len(nums) 
        res = 0 
        
       
        for i in range(1,d):
            res += 9 * math.perm(9,i-1)
        
		
        for i, x in enumerate(nums):
            if i == 0:
                digit_range = range(1,x) 
            else:
                digit_range = range(x)
                
            for y in digit_range:
                if y not in nums[:i]:
                    res += math.perm(9-i,d-1-i)
            if x in nums[:i]: break
                
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23