题目

输入一个整数n，求1_{n这n个整数的十进制表示中1出现的次数。例如，输入12,1}12这些整数中包含1的数字有1、10、11和12,1一共出现5次。

解题思路

从数字规律着手考虑问题

分析数字21345。
先看1236 ~ 21345中1出现的次数。1的出现我们从每一个不同的位考虑，比如千位上1出现多少次，百位上1出现多少次......
分析1出现在最高位(万位)的情况。因为万位为2>1，所以1出现在10000 ~ 19999这10000个数字的万位中，一共出现10000次。
扩展: 若万位数为1呢，比如:12345，此时1出现在万位的次数是不是会改变呢?
分析:1出现在10000 ~ 12345的万位上，即1出现的次数是10000 ~ 12345，是2346次(eg:10000、100001.....12345)共有2345+1次，也就是去掉最高位之后剩下的数字再加上1。
扩展: 若万位数为0呢，比如:02345，此时1出现在万位的次数是不是会改变呢? 那此时万位为1的次数为0
-------------------------再分析一下百位数-----------------------------

分析数字21345，将数据分为两段a = 213,b = 45

分析1出现在百位的次数，该数字百位数为3>1，则百位数出现的次数是(00100~ 00199)---->(11100~ 11199)---->(21100~21199)共(21+1)*100次，规律: 21=a/10
若百位数为1时，即a=211，则百位数出现的次数是(00100~ 00199)---->(11100~ 11199)---->(20100~20199) .(21100~20145) 共(20+1)*100+45+1次。规律: (a/10)*100+(b+1)次
若百位数为0时，即a=210，则百位数出现的次数是(00100~ 00199)---->(11100~ 11199)---->(20100~20199)共(a/10)*100次。

代码

int NumberOf1Between1AndN_2( unsigned int n)
{
    int ones = 0;
    for(int i = 1;i<=n;i*=10)
    {
        int a= n/i;
        int b  = n%i;
        //cout << "a: " << a << endl;
        //cout << "b: "  << b  << endl;
        if(a %10 == 0)
        {
            ones += (a / 10) *i;
        }
        else if(a % 10 == 1)
        {
            ones += (a /10) * i + (b + 1);
        }
        else
        {
            ones += ((a /10) +1) *i;
        }
        cout << "ones:" << ones <<endl;
    }
    return ones;
}

普通常规方法

int NumberOf1_1(unsigned int num)
{
    int sum_num = 0;
    while(num%10 == 1)
    {
        sum_num++;
        num = num/10;
    }
    return sum_num;
}

int NumberOf1Between1AndN_1(unsigned int n)
{
    int number = 0;
    for(unsigned int i = 1;i<=n;++i)
    {
        number+=NumberOf1_1(i);
    }
    return number;
}

完整代码见GitHub