GetOneTimes
计算从1到n的数字中1出现的次数
这道题目一看，估计是找规律，总结一套规则出来。首先暴力方法，遍历1-n，计算每个数所有1的个数，我当时居然写的一个方法更加搓，我都忘了辗转想除法，
以为只能从高位开始，然后先计算unsigned int最多有12位，然后从10^11此方开始，除，取结果，然后减去高位数，这样直到个位。。。
int EnumGetOneNum(int n)
{
if(n<=0) return 0;
int onesum=0;
for(int i=1;i<=n;i++)
{
int maxten=11;//signed int or unsigned int, max 12 digit
while(i>0)
{
int digit=i/pow(10.0,maxten);
if(digit==1)
onesum++;
i-=digit*pow(10.0,maxten);
maxten--;
}
}
return onesum;
}
后来发现自己连基本的辗转相除法都忘了 o(╯□╰)o 可以从各位先取余，再除，可以直接从个位开始逐个获得digit，这个比从高位好，因为你不知道位数是多少，我傻乎乎的从12位开始。。
附上这个代码
int LowToHighDigit_EnumGetOneNum(int n)
{
if(n<=0) return 0;
int onesum=0;
for(int i=1;i<=n;i++)
{
int maxten=11;//signed int or unsigned int, max 12 digit
while(i>0)
{
int digit=i%10;
if(digit==1)
onesum++;
i=i/10;
//int digit=i/pow(10.0,maxten);
//if(digit==1)
// onesum++;
//i-=digit*pow(10.0,maxten);
//maxten--;
}
}
return onesum;
}
接下来才是重头戏，不愧我想了那么久。。
我开始总结，按照位数来统计，先算个位的1，再十位 百位。。。先看10位的，10-19有10次，110-119有10次，感觉就是除掉前10个，后面差为100的等差，然后里面前面连续10个，后面都没有，
大致计算公式是
n-10=100x+y (n>=10)
sum=10x+10(y>=10)
10*x+y+1(y<10)
于是百位也是类似
n-100=1000x+y (n>=100)
sum=100x+100(y>=100)
100*x+y+1(y<100)
一开始还以为个位就是1 ，sum初值为1，然后从十位开始，后来测试的时候是错的，然后个位也是按照上面的，于是就有如下的代码 o(╯□╰)o
int GetOneNum (int n)
{
if(n<=0) return 0;
int sum=0;
int ten=1;//10 base
while(n>=ten)
{
int x=(n-ten)/(10*ten);
int y=(n-ten)%(10*ten);
sum+=x*ten;
if(y>=ten)
sum+=ten;
else
sum+=(y+1);
ten*=10;
}
return sum;
}
剑指Offer上的是一个递归算法，我也没有往这里想，大致是把最高位和其余数字分开来处理，低的n-1位数字递归算，细节没看，大致思路这样。。。
今天看到CJ的微博，才发现这道题目BOP上也有，于是重新想一遍，发现居然最后归纳式子的时候有点问题一直没搞定。。。。有点慌了，解过的题目现在再次解不出了，可能是因为上次灵光一现的因素太多，没有形成general的思维
套路。最主要是自己想发现不知道把余数 分成两种情况考虑，虽然把十位数1的个数和N关系的函数曲线都画出来，却不知道怎么写出函数关系式，其实还是按照之前(n-10)/100式子来，最好写出n-10=100x+y, 那么如果到了20~109其实和19是一样的，
所以把这100个数用单独的常数来处理，对于10~19 则用一个线性函数处理，当 n>=20时，即(n-10)%100=y>=10, sum=10x+10,否则，n<=19, 即(n-10)%100=y<=9, sum=10*x+y+1分成这两种处理。十位的处理好了，其他类推就可以了。