题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
long long f[20][10][1024];
int a[15];
int dfs(int pos,int pre,int lead,int limit,int cnt)
{
if(!pos) return !lead;
if(!limit&&!lead&&f[pos][pre][cnt]!=-1) return f[pos][pre][cnt];
int res=0,up=limit?a[pos]:9;
for(int i=0;i<=up;i++)
{
if(cnt&(1<<i)) continue;
int c=cnt;
if(lead&!i)
{
res+=dfs(pos-1,0,lead&&!i,limit&&i==up,cnt);
}
else
{
c|=1<<i;
res+=dfs(pos-1,i,lead&&!i,limit&&i==up,c);
}
}
return limit?res:(lead?res:f[pos][pre][cnt]=res);
}
int cal(int x)
{
memset(f,-1,sizeof(f));
int len=0;
while(x) a[++len]=x%10,x/=10;
unordered_map<int,int> mp;
return dfs(len,0,1,1,0);
}
int countSpecialNumbers(int n)
{
memset(a,0,sizeof(a));
int res=cal(n);
return res;
}
};