题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

输入

13

输出

6

这道题如果使用暴力破解,肯定是会超时的,所以我们需要看看这里面有没有啥规律。(这规律并非我自己发现的,从别人的答案中得知,直呼牛逼)

假设现在有一个是为num,num是位数一共为x,n~1~ 个位,n~2~ 表示十位,n~x~ 表示最高位,那么num就可以表示为:n~x~n~x-1~n~x-2~...n~3~n~2~n~1~。
比如3504,最高位是3,百位是5,十位是0,个位是4,拿十位来说,比十位更高的位上的数是3,5,比十位更低的位数上的数是4。

当前位是0

假设当前位上的数是0,譬如3504,那么35是高位,4是低位,当前位是十位,也就是10,1出现的可能性是哪些呢?

从001X到341X
猜想一下,前面的千位和百位的组合是不是可以从00到34,有人说为什么不到35,351X明显超出范围了!!!
那后面的X是不是可以随意的0到9呢?那肯定是啊,所以前面00到34一共35个数,0到9一共10个数,这个10也就是因为当前的1在十位上。
所以当前位是0的时候,该位出现1的数字个数是:
$$
高位*当前位数 = 35 *10 =350
$$

当前位是1

假设我们现在计算的是3514,当前位是1,高位是35,低位是4。除了前面说的高位从00到34,低位可以从0到9,之外。仔细观察!!!

351X
如果高位是35的时候,低位是不是可以从0-4,一共五个数。最大的数是3514,所以当前位是1的时候,当前位数出现1的个数是:
$$
高位当前位数+低位+1 = 3510+4+1 = 355
$$

当前位>1

假设我们现在计算的是3524,当前位是2,高位是35,低位是4。我们发现,当当前位是1的时候,高位可以从0到35,而低位是可以从0到9,最小是0010,最大是3519。
因此当前位大于2的时候,所有数字中出现1的个数是:
$$
(高位+1)*当前位数 = (1+35)*10 = 360
$$

每一位上出现1的次数都依照上面的算法,就可以得出出现1的所有次数。代码如下:

    public static int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        int level = 1;
        int high = n / 10;
        int low = 0;
        int cur = n % 10;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                sum = sum + high * level;
            } else if (cur == 1) {
                sum = sum + high * level + low + 1;
            } else {
                sum = sum + (high + 1) * level;
            }
            low = cur * level + low;
            level = level * 10;
            cur = high % 10;
            high = high / 10;
        }
        return sum;
    }

不得不说,找到这个规律的人真的超级牛逼!!!

【作者简介】
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。这个世界希望一切都很快,更快,但是我希望自己能走好每一步,写好每一篇文章,期待和你们一起交流。

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者核实删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

纵然缓慢,驰而不息。