Leetcode-233-Number of Digit One

数数字的题目说难也难，说简单也简单，难就难在不重不漏，简单就简单在方法找对了，就是一个公式的事儿。

这道题的思路其实不难找，我们考虑一下什么时候会出现数字1：

1、11、21、……、91
10、11、12、……、19
100、101、……、199

我们看到，统计1在各个数位上出现的次数比较简单，不会重复也不易遗漏。我们看到11在这里出现了两次，按照数位计算的话就是十位计算一次个位计算一次，并不会产生重复。

现在的问题就是，如何计算各个数位上1的个数。

比如我们看数字，个位上有多少个呢？把分成和两部分，可以看到，前一部分可以取，后一部分可以取，于是个位上的个数就是。

下面我们看十位，同样的思路，我们把分成和两部分，前一部分可以取，后一部分可以取于是十位上是的个数为。

依次进行下去并将结果相加即为最终结果。

需要注意的特殊情况是某一位上的数字为和的情况，比如，我们在考查十位上数字的个数的时候应该取(而非)，因为。

当数字为，十位上数字的个数为。

从而我们可以由以上规律得到一个统一的计算公式，代码如下：

class Solution {
public:
    int countDigitOne(int n) 
    {
        int res = 0;
        for (long i=1;i<=n;i*=10) 
            res+=(n/i+8)/10*i+(n/i%10==1)*(n%i+1);
        return res;
    }
};