数位dp，LeetCode 2376 统计特殊整数
目录
一、题目
1、题目描述
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数
n，请你返回区间[1, n]之间特殊整数的数目。
2、接口描述
python3
class Solution:
def countSpecialNumbers(self, n: int) -> int:cpp
class Solution {
public:
int countSpecialNumbers(int n) {
}
};C#
public class Solution {
public int CountSpecialNumbers(int n) {
}
}3、原题链接
二、解题报告
1、思路分析
关于数位dp：数位dp详解，记忆化搜索，递推，OJ精讲_数位dp记忆化搜索-CSDN博客
数位dp很多时候都是板子题，只需修改记忆化搜索的参数和状态获取
这里如果使用记忆化的做法我们需要：
前面填过的数的集合pre（二进制表示集合），前缀是否小于n的前缀lim，是否前导零 zero
然后下面就是板子做法了
这里额外提一下递推做法：
记忆化的做法实际上是在走搜索树，最右侧的一条路径 lim 始终为false，其本质是等于n的情况，对于其它路径其实可以组合数学求解
对于位数小于n的数，不妨设位数为i，那么方案数为 9 * fac(9) / fac(10 - i)
对于位数等于n的数，我们从高位试填（走搜索树上最右侧路径），用 vis 数组记录用过的数字
对于第 i 位，假如有 cnt 个数字未使用
试着填 第 i 位填 小于 d[i] 的情况，方案为 cnt * fac(9 - i, m - i - 1)
然后判断 该位能否填 d[i]，即 vis[d[i]] 是否出现？
出现的话，break
否则，vis[d[i]] = true
对于最右侧路径对应n只会有1的贡献，我们只需在结束的时候判断是否走完了路径来使得答案+1即可
2、复杂度
时间复杂度： O(log^2 n)空间复杂度：O(log(n))
python3 记忆化 时间复杂度：O(mU2^U), U = 10
3、代码详解
python3
class Solution:
def countSpecialNumbers(self, n: int) -> int:
d = []
t = n
while t:
d.append(t % 10)
t //= 10
@cache
def dfs(n: int, pre: int, lim: bool, zero: bool) -> int:
if n < 0:
return not zero
top = 9 if lim else d[n]
res = 0
for i in range(top + 1):
if (pre >> i) & 1: continue
nxt = pre | (1 << i)
if i == 0 and zero:
nxt &= nxt - 1
res += dfs(n - 1, nxt, lim or i < top, zero and i == 0)
return res
dfs.cache_clear()
return dfs(len(d) - 1, 0, False, True)cpp
int fac[10];
auto init = []{
fac[0] = 1;
for (int i = 1; i < 10; ++ i)
fac[i] = fac[i - 1] * i;
return 0;
}();
int getPer(int n, int m) {
return fac[n] / fac[n - m];
}
class Solution {
public:
int countSpecialNumbers(int n) {
std::string s = std::to_string(n);
int m = s.size();
int res = 0;
for (int i = 0; i + 1 < m; ++ i) res += 9 * getPer(9, i);
std::vector<bool> vis(10);
int i = 0;
for (; i < m; ++ i) {
int v = s[i] ^ 48;
int cnt = 0;
for (int j = i ? 0 : 1; j < v; ++ j)
if (!vis[j])
++ cnt;
res += cnt * getPer(9 - i, m - i - 1);
if (vis[v]) break;
else vis[v] = true;
}
if (i == m) ++ res;
return res;
}
};C#
public class Solution
{
static int[] fac;
static Solution()
{
fac = new int[10];
fac[0] = 1;
for (int i = 1; i < 10; ++ i) fac[i] = i * fac[i - 1];
}
static int getPer(int n, int k)
{
return fac[n] / fac[n - k];
}
public int CountSpecialNumbers(int n)
{
string s = n.ToString();
int m = s.Length, res = 0;
bool[] vis = new bool[10];
int i = 0;
for (i = 0; i + 1 < m; ++i) res += 9 * getPer(9, i);
for (i = 0; i < m; ++ i)
{
int v = s[i] ^ 48;
int cnt = 0;
for (int j = i > 0 ? 0 : 1; j < v; ++j) {
if (!vis[j])
++cnt;
}
res += cnt * getPer(9 - i, m - i - 1);
if (vis[v]) break;
else vis[v] = true;
}
if (i == m) ++res;
return res;
}
}原文地址：https://blog.csdn.net/EQUINOX1/article/details/142377236
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！