难度: 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 * 109运行时间: 45 ms
内存: 16.0 MB
from math import perm
class Solution:
def countSpecialNumbers(self, num: int) -> int:
num = str(num)
n = len(num)
res = sum(9 * perm(9, i-1) for i in range(1, n))
s = set()
for i, c in enumerate(num):
for j in range(0, int(c)):
if i+j==0 or j in s:
continue
res += perm(10-i-1, n-i-1)
if int(c) in s:
return res
s.add(int(c))
return res+1
题解采用了数位动态规划的思想。首先，计算所有长度小于给定数字的特殊整数个数，然后计算长度等于给定数字的部分特殊整数。具体地，对于长度小于n的数，可以直接计算每个长度的特殊数字数量，例如长度为i的数字，其首位有9种选择(1-9)，其余位从剩下的9个数字中选(i-1)个数字排列。对于长度等于n的情况，从最高位到最低位逐位确定数字，并排除已经使用过的数字，使用排列计算剩余位的可能组合。如果在某一位发现重复使用数字，则剩余部分不再构成特殊整数。
时间复杂度: O(n)
空间复杂度: O(n)
from math import perm
class Solution:
def countSpecialNumbers(self, num: int) -> int:
num = str(num) # 将数字转换为字符串，便于逐位处理
n = len(num) # 计算数字的长度
# 计算所有长度小于n的特殊数的总数
res = sum(9 * perm(9, i-1) for i in range(1, n))
s = set() # 用于记录已经使用过的数字
for i, c in enumerate(num): # 逐位检查数字
for j in range(0, int(c)):
if i+j==0 or j in s:
continue # 跳过已经使用过的数字
res += perm(10-i-1, n-i-1) # 计算剩余位的可能组合
if int(c) in s:
return res # 如果发生重复，返回当前计算结果
s.add(int(c)) # 将当前数字添加到已使用集合中
return res+1 # 包括数字本身在内的总数
在数位动态规划中，计算长度小于n的特殊整数个数涉及到首位和剩余位的选择与排列。对于每个长度i（小于n），首位数字可以从1到9中选择（共9种选择），因为首位不能是0。剩余的(i-1)位可以从0到9中选择，但需要排除首位选择的数字。因此，剩余位有9种选择（除去首位的一个数字）。具体的排列方式是，从剩下的9个数字中选出(i-1)个进行排列，排列数可以用排列公式perm(9, i-1)表示。这样，每个长度i的特殊整数数量就是9乘以perm(9, i-1)。将所有这些长度的结果相加，就得到了所有长度小于n的特殊整数总数。
在处理长度等于n的数字时，逐位检查并排除已使用过的数字是为了确保数字的每位都是唯一的，从而符合特殊整数的定义。开始时，从最高位到最低位逐一确定每一位的数字，并检查这个数字是否已经在之前的位数中使用过。如果已使用，则此路径不再考虑，因为继续计算将会导致重复数字的出现，不符合特殊整数的条件。如果未使用，则将这个数字标记为已使用，并继续考虑下一位。这种方法的正确性通过确保每个被选中的数字在整个数字中只被使用一次来保证，从而满足特殊整数的要求。
题解中提到的处理方式不会遗漏符合条件的特殊整数。当在逐位检查过程中发现重复使用数字时，意味着当前分支下的所有可能整数都将包含重复数字，因此这一路径不能产生任何有效的特殊整数。提前返回当前计算结果是为了避免无效的计算，因为继续处理这个分支将不会产生新的有效整数。这种处理方式有效地减少了计算量，且确保了只有符合特殊整数定义的数字被计算在内。