一个最简单的方法来计算 $f(N)$ ，那就是从 `1` 开始遍历到 `N` ，将 `1` 的个数加起来就是答案了。但是这个算法的效率， $O(N*log2(N))$ 。 那么让我们来分析一下对于一个指定的 `N` ，如何得到一个规律来求得每一位上所有出现 `1` 的可能性，看看能不能总结出什么规律。 先看一位数的情况。 如果 $N=3$ ，那么从 `1` 到 `3` 的所有数字： $1,2,3$ 。只有个位数字上可能出现 `1` ，而且只出现了一次。那么如果 `N` 为个位数，且 $N>=1$ ，那么 $f(N)=1$ 。 再看两位数的情况。 如果 $N=13$ ，那么个位数出现 `1` 的次数有两次： `1` 和 `11` ，十位数出现 `1` 的个数有 `4` 次： $10,11,12,13$ ，所以 $f(N)=2+4=6$ 。 同理可得： * $f(13)$ =个位数上 `1` 的个数+十位数上 `1` 的个数= $2+4=6$ * $f(23)$ =个位数上 `1` 的个数+十位数上 `1` 的个数= $3+10=13$ * $f(33)$ =个位数上 `1` 的个数+十位数上 `1` 的个数= $4+10=14$ * 。。。 * $f(93)$ =个位数上 `1` 的个数+十位数上 `1` 的个数= $10+10=20$ 接着分析三位数。 如果 $N=123$ ： 个位数上出现 `1` 的个数为 `13` 个： $1,11,21，...，91,101,111,121$ 。 十位数上出现 `1` 的个数为 `20` 个： $10~19,110~119$ 。 百位数上出现 `1` 的个数为 `24` 个： $100~123$ 。 则 $f(123)$ =个位数上 `1` 的个数+十位数上 `1` 的个数+百位数上 `1` 的个数= $13+20+24=57$ 。 根据上面的一些尝试，我们可以推断出下面的一般情况： 如果我们要计算百位数上出现 `1` 的个数，它将受到三个因素的影响：百位数上的数字，百位以下的数字，百位以上的数字。 如果百位数上的数字为 `0` ，则可以知道，百位上可能出现 `1` 的次数由更高位位决定，比如 `12013` ，则可以知道百位出现 `1` 的情况可能是 $100~199,1100~1199,2100~2199，...，11100~11199$ ，一共 `1200` 个。也就是更高位数字`(12)`决定，并且等于更高位数字`(12)` *当前位数`(100)` 。 如果百位数上的数字为 `1` ，则可以知道，百位上可能出现 `1` 的次数不仅受更高位影响，还受低位影响。例如 `12113` ，受更高位影响，百位出现 `1` 的情况是 $100~199,1100~1199,2100~2199，...，11100~11199$ ，一共 `1200` 个。但是它还受低位影响，百位出现 `1` 的情况是 `12100~12113` ，一共 `114` 个，等于低位数字 `(123)` + `1` 。 如果百位数上的数字大于 `1` ，则百位上可能出现 `1` 的次数也仅由更高位决定。比如 `12213` ，则百位上出现 `1` 的可能性为 $100~199,1100~1199,2100~2199，...，11100~11199，12100~12199$ ，一共 `1300` 个，并且等于更高位数字+ $1(12+1)$ *当前位数 `(100)` 。 则我们把百位数推广到任何位数上，就可以高效的计算出 $f(N)$ ，时间复杂度只要 $O(ln(N)/ln(10)+1)$ 。