题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
long long f[30][3][3];
class Solution {
public:
long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
string a=to_string(finish);
string b=to_string(start-1);
std::function<long long(int,int,int,string)> dfs=
[&](int i,int is_limit,int num,string t)->long long{
if(i==t.size()) return num;
if(f[i][is_limit][num]!=-1) return f[i][is_limit][num];
auto&res=f[i][is_limit][num];
if(t.size()-i<=s.size()){
int x=s.size()-(t.size()-i);
if(is_limit==false) return dfs(i+1,is_limit&&limit==(s[x]-'0'),1,t);
else {
if(t[i]-'0'<s[x]-'0') return 0;
else return dfs(i+1,is_limit&&s[x]-'0'==t[i]-'0',1,t);
}
}
res=0;
if(!num) res=dfs(i+1,0,0,t);
int up,di;
if(is_limit) up=min(t[i]-'0',limit);
else up=limit;
di=0;
if(!num) di=1;
for(int d=di;d<=up;d++){
res+=dfs(i+1,is_limit&&d==t[i]-'0',1,t);
}
return res;
};
long long res=0;
memset(f,-1,sizeof(f));
if(finish>=stoll(s))res+=dfs(0,1,0,a);
memset(f,-1,sizeof(f));
if(start-1>=stoll(s)) res-=dfs(0,1,0,b);
return res;
}
};
py
class Solution:
def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
b=str(start-1)
a=str(finish)
@cache
def dfs(i:int,is_limit:bool,num:bool,t:str)->int:
if i==len(t):return int(num)
if len(t)-i<=len(s):
x=len(s)-(len(t)-i)
if is_limit==False:
return dfs(i+1,is_limit and limit==int(s[x]),True,t)
else:
if int(t[i])<int(s[x]):
return 0
else:
return dfs(i+1,is_limit and int(s[x])==int(t[i]),True,t)
return 0
res=0
if not num:res=dfs(i+1,False,False,t)
if is_limit:
up=min(int(t[i]),limit)
else:up=limit
di=0
if not num:di=1
for d in range(di,up+1):
res+=dfs(i+1, is_limit and d==int(t[i]), True,t)
return res
res=0
if finish>=int(s):
res=dfs(0,True,False,a)
if start-1>=int(s):
res-=dfs(0,True,False,b)
return res
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution:
def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
low=str(start)
high=str(finish)
n=len(high)
low='0'*(n-len(low))+low
@cache
def dfs(i:int,limit_low:bool,limit_high:bool,is_num:bool)->int:
if i==n:return int(is_num)
res=0
if not is_num and low[i]=='0':
#前面没填过数,且目前最低位
res+=dfs(i+1,True,False,False)
lo=int(low[i]) if limit_low else 0
hi=int(high[i]) if limit_high else 9
d0=0 if is_num else 1
if n-i>len(s):
for d in range(max(lo,d0),min(hi,limit)+1):
res+=dfs(i+1,limit_low and d==lo, limit_high and d==hi,True)
else:
x=int(s[len(s)-(n-i)])
if max(lo,d0) <=x <=min(hi,limit):
res=dfs(i+1,limit_low and x==lo,limit_high and x==hi,True)
return res
return dfs(0,True,True,False)