数位dp: 时间复杂度为 n位数*10 接近常熟 分成n位数字讨论即可
public:
vector<int> v;
int NumberOf1Between1AndN_Solution(int n) {
while(n){
v.push_back(n%10);
n/=10;
}
reverse(v.begin(),v.end());
int len=v.size();
int ans=0;
for(int i=0;i<len;i++){
if(i==0){
if(v[i]>1) ans+=pow(10,len-1-i);
else ans+=fend(i+1)+1;
// cout<<ans<<endl;
}else{
int qz=fsta(i),hz=fend(i+1);
int p10=pow(10,len-i-1);
if(v[i]==0) ans+=p10*qz;
else if(v[i]>1) ans+=(qz+1)*p10;
else ans+=qz*p10+hz+1;
}
}
return ans;
}
int fsta(int j){
int temp=0;
for(int i=0;i<j;i++){
temp=temp*10+v[i];
}
return temp;
}
int fend(int j){
int temp=0;
for(int i=j;i<v.size();i++){
temp=temp*10+v[i];
}
return temp;
}
};