题目：

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:

Given n = 13,

Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

思路：

对这个数字的每一位求存在1的数字的个数。

从个位開始到最高位。

举个样例54215。比方如今求百位上的1，54215的百位上是2。能够看到xx100到xx199的百位上都是1，这里xx从0到54。即100->199, 1100->1199...54100->54199, 这些数的百位都是1，因此百位上的1总数是55*100



假设n是54125,这时因为它的百位是1，先看xx100到xx199。当中xx是0到53，即54*100, 然后看54100到54125，这是26个。所以百位上的1的总数是54*100 + 26.



假设n是54025。那么仅仅须要看xx100到xx199中百位上的1，这里xx从0到53，总数为54*100

求其它位的1的个数的方法是一样的。

代码：

class Solution {

public:

    int countDigitOne(int n)

    {

        int res=0;

        long left, right, base=1;

        if (n <= 0)

            return 0;

        while (n >= base)

        {

            left = n / base;   //left包括当前位

            right = n % base;  //right为当前位的右半边

            if ((left % 10) > 1)

                res+= (left / 10 + 1) * base;

            else if ((left % 10) == 1)

                res+= (left / 10) * base+ (right + 1);

            else

                res+= (left / 10) * base;

            base *= 10;

        }

        return res;

	}

};

能够把上面三个条件合成一步。例如以下：

class Solution {

public:

    int countDigitOne(int n)

    {

        int res=0;

        long left, right, base=1;

        if (n<=0)

            return 0;

        while (n>=base)

        {

            left = n / base;   //left包括当前位

            right = n % base;  //right为当前位的右半边

            res += ((left + 8) / 10 * base) + (left % 10 == 1) * (right + 1);

            base *= 10;

        }

        return res;

	}

};