查找规律:
只有一位的数字n,只有1个数字包含1,就是1,设a[1]=1;
两位数字的话,有10 11 12...19 21 31 41 ...91 ,那么a[2]=a[1]9+10^(2-1)
同理a[i]=a[i-1]9+10^(i -1)
举例,比如113
113 首先我们把小于3位的所有数字中的1的个数加起来,就是a[1]+a[2]
其次我们再去找100到113有多少个1,这其中包括两部分:一个是首位的1,有14个,还有就是13里面有多少个1,这时就可以递归查找13有多少个1。13有6个1,所以100-113 有20个1
如果213 ,那么100到213 有多少个1呢?这里100-199中包括的1,我们是可以算出来的,等于100+a[2],然后我们再找13里有多少个1
如果313,100-299是可以算出来的,等于100+a[2]+a[2],然后再找13里有多少个1
这道题目有个坑点,就是n可能会小于0
typedef long long int _int;
class Solution {
public:
_int a[11];
int countDigitOne(int n) {
if(n<0)
return 0;
a[1]=1;
for(int i=2;i<=10;i++)
{
a[i]=a[i-1]*9+(int)pow(10,i-1)+a[i-1];
}
int h = getNum(n);
return fun(n,h);
}
int getNum(int x)
{
int h=0;
while(x)
{
x/=10;
h++;
}
return h;
}
_int fun(int n,int i)
{
if(i==0||n==0)
return 0;
if(i==1&&n>=1)
return a[i];
_int res = 0;
int x=n/(int)pow(10,i-1);
res+= a[i-1];
res+= x==1?0:(int)pow(10,i-1)+a[i-1]*(x-1);
_int n2 = n%((int)pow(10,i-1));
_int y = fun(n2,getNum(n2));
if(x==1)
{
res+=n%((int)pow(10,i-1))+1;
res+=y;
}
else
res+=y;
return res;
}
};
LeetCode 233. Number of Digit One
原文:https://www.cnblogs.com/dacc123/p/12361603.html