这个题目其实来自于Leetcode的以下两道题目:
问题的主体就是,给出一个确定的整数n,求取所有不大于n的,且各个位数都不相同的数的个数。
或者相反,求出存在至少有两位数字相同的数字的个数,不过这两个问题是互补的,所以我们只需要考虑上一个问题即可。
这一题的算法思路算是一个相对复杂一点的分类讨论:
具体到实现上,我们摘录某位大佬的代码实现如下:
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