题目描述（困难难度）

给一个数，输出 0 ~ n 中的数字中 1 出现的个数。

解法一暴力

直接想到的当然就是暴力的方法，一个数一个数的判断，一位一位的判断。

但这个解法会超时。

自己也没想到别的方法，讲一下这里的思路。

总体思想就是分类，先求所有数中个位是 1 的个数，再求十位是 1 的个数，再求百位是 1 的个数…

假设 n = xyzdabc，此时我们求千位是 1 的个数，也就是 d 所在的位置。

那么此时有三种情况，

为什么呢？

对于 xyz 的话，可以取 0,1,2...(xyz-1)，也就是 xyz 种可能。

当 xyz 固定为上边其中的一个数的时候，abc 可以取 0,1,2...999，也就是 1000 种可能。

这样的话，总共就是 xyz*1000 种可能。

注意到，我们前三位只取到了 xyz-1，那么如果取 xyz 呢？

此时就出现了上边的三种情况，取决于 d 的值。

d == 1 的时候，千位刚好是 1，此时 abc 可以取的值就是 0 到 abc ，所以多加了 abc + 1。

d > 1 的时候，d 如果取，那么 abc 就可以取 0 到 999，此时就多加了 1000。

再看一个具体的例子。

代码的话就很好写了。

然后代码的话，可以再简化一下，注意到 d > 1 的时候，我们多加了一个 k。

我们可以通过计算 long xyz = xyzd / 10; 的时候，给 xyzd 多加 8，从而使得当 d > 1 的时候，此时求出来的 xyz 会比之前大 1，这样计算 xyz * k 的时候就相当于多加了一个 k。

此外，上边 k 溢出的问题，我们可以通过 long 类型解决。

而这个代码，其实和 Solution -C%2B%2BJavaPython) 中的解法是一样的，只不过省去了 xyz 和 d 这两个变量。

这道题的话，就是数学的分类、找规律的题目了，和找阶乘中 0 的个数一样，没有一些通用的算法，完全靠分析能力，如果面试碰到很容易卡主。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击这里查看详情