2376. Count Special Integers
We call a positive integer special if all of its digits are distinct.
Given a positive integer n, return the number of special integers that belong to the interval [1, n].
Example 1:
Input: n = 20 Output: 19 Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.
Example 2:
Input: n = 5 Output: 5 Explanation: All the integers from 1 to 5 are special.
Example 3:
Input: n = 135 Output: 110 Explanation: There are 110 integers from 1 to 135 that are special. Some of the integers that are not special are: 22, 114, and 131.
Constraints:
1 <= n <= 2 * 109
class Solution:'''对各个数位逐位进行填充是否已经开始填如果还没开始填，选择不填(相当于会是更少位数),可以从下一位开始如果选择填：1.决定可以填充的范围low: 如果还没开始填，那么只能从1开始填，否则可从0开始up: a.如果前面各位都是上限，那么这位只能取到s[i]b.否则可以取到92.轮询low~up如果之前没有填过的数字就可以用另外记得更新mask和是否上限'''def countSpecialNumbers(self, n: int) -> int:s = str(n)@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）def dfs(i: int, mask: int, is_limit: bool, is_num: bool) -> int:# print(sub, i, bin(mask)[2:], is_limit, is_num)if i == len(s):return 1 if is_num else 0 # is_num 为 True 表示得到了一个合法数字 res = 0# 还没开始填,可以跳过当前数位if not is_num: res = dfs(i + 1, mask, False, False)# low 和 up 决定当前数位的取值范围# 如果前面没有填数字，则必须从 1 开始（因为不能有前导零）low = 0 if is_num else 1'''# 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦），比如：234 当前在3这位，如果之前一位填的是1，那么这一位随便填，如果之前一位填的是2,那么这一位只能填小于3的数字^'''up = int(s[i]) if is_limit else 9for d in range(low, up + 1): # 枚举要填入的数字 dif mask >> d & 1 == 0: # d 不在 mask 中，说明之前没有填过 dres += dfs(i + 1, mask | (1 << d), is_limit and d == up, True)return res# is_limit 初始值为True# is_num 初始值为Falsereturn dfs(0, 0, True, False)