目录
一、题目
1、题目描述
2、接口描述
python3
cpp
C#
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
python3
cpp
C#
一、题目
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、原题链接
2376. Count Special Integers
二、解题报告
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 = nwhile t:d.append(t % 10)t //= 10@cachedef dfs(n: int, pre: int, lim: bool, zero: bool) -> int:if n < 0:return not zerotop = 9 if lim else d[n]res = 0for i in range(top + 1):if (pre >> i) & 1: continuenxt = pre | (1 << i)if i == 0 and zero:nxt &= nxt - 1res += dfs(n - 1, nxt, lim or i < top, zero and i == 0)return resdfs.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;}}