[LeetCode解题报告] 2376. 统计特殊整数

一、 题目

1. 题目描述

2. 原题链接

链接: 2376. 统计特殊整数

二、 解题报告

1. 思路分析

 这题是306周赛T4，我抄了力扣上其他题的题解。
 赛后学习了灵神的记忆化搜索模板，记录一下。
1
2

• 记录一下灵神的数位dp通用模板。
• 先把数字x转化成字符串s。
• 定义一个记忆化函数@cache def f(i,mask,is_limit,is_num):
• 函数返回：在前边用了mask的集合后，约束从左开始第i位后边的数字能构造出的数目。
• 其中i代表现在运算到第几位。
• mask代表用了哪些数字，有的题目用不到，或者是其他约束。
• is_limit代表当前位是否受到了对应s串上对应位数字的约束，比如针对’123’这个串，当前两位填了’12’,那么第3位只能填0123.
  • 也就是说，当is_limit==True，则当前位最多填int(s[i]；否则能填到9
• is_num，也叫is_not_lead,代表当前位的前一位是否填了数字，本题如果没填数字，即本位是开头，那么等于本位也可以跳过，相当于多一种情况。

2. 复杂度分析

设转化后的字符串长度是n≈10
复杂度O(10102410)，状态数(10*1024)*转移数(10)。

3. 代码实现

数位DP记忆化搜索模板。

class Solution:
    def countSpecialNumbers(self, x: int) -> int:
        s = str(x)
        n = len(s)
        @cache
        def f(i,mask,is_limit,is_num):
            if i == n:
                return int(is_num)
            ans = 0
            if not is_num:
                ans += f(i+1,mask,False,False)
            r = int(s[i]) if is_limit else 9
            l = 0 if is_num else 1
            for j in range(l,r+1):
                if not mask>>j&1:
                    ans += f(i+1,mask|(1<<j),is_limit and j == r,True)
            return ans 
        return f(0,0,True,False)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三、 本题小结

1. 有时间把灵神的数位DP题单过一遍，写个模板出来。

四、 参考链接

• 链接: [LeetCode周赛复盘] 第 306 场周赛20220814