摘要
Title: 2376. 统计特殊整数
Categories: 数位dp

2376. 统计特殊整数

题意

如果一个正整数每一个数位都是互不相同的，我们称它是特殊整数。

给你一个正整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

思路

详见灵神视频
https://leetcode.cn/problems/count-special-integers/solutions/1746956/shu-wei-dp-mo-ban-by-endlesscheng-xtgx/

下面是模板，切范围只是 [1, n]，不包括0，因为我们省去了前导0的情况，其中

i是索引，从数的高位开始dp。这个参数固定
mask，根据题目要求设定参数，这里的是用二进制数表示集合
is_limit。这个参数固定
is_num。这个参数固定

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        # 将整数 n 转换为字符串表示，方便逐位处理。
        s = str(n)

        @lru_cache(None)  # 使用缓存机制来避免重复计算，提高效率。
        def dfs(i, mask, is_limit, is_num):
            """
            使用深度优先搜索（DFS）和动态规划计算特殊数字的数量。

            参数:
                i (int): 当前处理的位数（在字符串 s 中的索引）。
                mask (int): 位掩码，用于表示目前已经使用的数字。每个位代表一个数字，位被设置为1表示该数字已使用。集合和二进制的转换关系
                is_limit (bool): 表示前面填的数字是否都是 n 对应位上的，如果为 true，那么当前位至多为 int(s[i])，否则至多为 9
                is_num (bool): 表示当前是否已经形成了一个有效的数字（避免前导零）。

            返回值:
                int: 从当前状态开始的有效特殊数字的数量。
            """
            # 基础情况：如果已经处理完所有位。
            if i == len(s):
                # 如果已经形成了一个有效的数字（is_num 为 True），返回 1；否则返回 0。
                return int(is_num)
            
            # 初始化当前状态下的结果。
            res = 0
            
            # 如果还没有形成有效数字，可以选择跳过当前位。
            if not is_num:
                # 递归处理下一位，不形成数字。
                res = dfs(i + 1, mask, False, False)

            # 确定当前位的上限。
            # 如果 is_limit 为 True，当前位的数字不能超过 s[i]；
            # 否则，当前位可以是 0 到 9 之间的任意数字。
            up = int(s[i]) if is_limit else 9
            
            # 确定当前位的下限。
            # 如果已经形成了一个数字，当前位可以从 0 开始；
            # 否则，为了避免前导零，当前位只能从 1 开始。
            down = 0 if is_num else 1
            
            # 尝试当前位的所有可能数字。
            for d in range(down, up + 1):
                # 检查当前数字 d 是否已经使用过（即 mask 中相应的位是否已设置）。
                if not 1 << d & mask:
                    # 递归处理下一位，更新位掩码和限制条件。
                    res += dfs(
                        i + 1, 
                        mask | 1 << d,  # 将当前数字 d 加入位掩码。
                        is_limit and d == up,  # 如果 d 达到上限，更新 is_limit。
                        True  # 现在已经形成了一个有效数字。
                    )

            return res

        # 从第一位开始 DFS，位掩码为空，限制条件由 n 决定，尚未形成数字。
        return dfs(0, 0, True, False)

代码

'''
Author: NEFU AB-IN
Date: 2024-08-10 20:54:06
FilePath: \LeetCode\2376\2376.py
LastEditTime: 2024-08-12 23:45:19
'''
import random
# 3.8.19 import
from ast import Pass
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        s = str(n)

        @lru_cache(None)
        def dfs(i, mask, is_limit, is_num):
            if i == len(s):
                return int(is_num)
            res = 0
            if not is_num:
                res = dfs(i + 1, mask, False, False)

            up = int(s[i]) if is_limit else 9
            down = 0 if is_num else 1
            for d in range(down, up + 1):
                if not 1 << d & mask:
                    res += dfs(i + 1, mask | 1 << d, is_limit and d == up, True)

            return res

        return dfs(0, 0, True, False)