题目描述
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
额,题目的意思实际上是求出从1到n整数中1出现的次数。
链接:https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6
题目分析
设N = abcde ,其中abcde分别为十进制中各位上的数字。
如果要计算百位上1出现的次数,它要受到3方面的影响:百位上的数字,百位以下(低位)的数字,百位以上(高位)的数字。
① 如果百位上数字为0,百位上可能出现1的次数由更高位决定。比如:12013,则可以知道百位出现1的情况可能是:100~199,1100~1199,2100~2199,,…,11100~11199,一共1200个。可以看出是由更高位数字(12)决定,并且等于更高位数字(12)乘以 当前位数(100)。
② 如果百位上数字为1,百位上可能出现1的次数不仅受更高位影响还受低位影响。比如:12113,则可以知道百位受高位影响出现的情况是:100~199,1100~1199,2100~2199,,….,11100~11199,一共1200个。和上面情况一样,并且等于更高位数字(12)乘以 当前位数(100)。但同时它还受低位影响,百位出现1的情况是:12100~12113,一共114个,等于低位数字(113)+1。
③ 如果百位上数字大于1(2~9),则百位上出现1的情况仅由更高位决定,比如12213,则百位出现1的情况是:100~199,1100~1199,2100~2199,…,11100~11199,12100~12199,一共有1300个,并且等于更高位数字+1(12+1)乘以当前位数(100)。
这题没看题解之前真是一脸懵逼,找规律真是不太容易啊。
至此,就可以写代码了,为了加深理解,我再通过表格的形式叙述一下算法流程。以21345为例,列表如下:
i(当前位) | n/i/10(前面的数) | n/i%10(当前位的值) | n%i(后面的数) | 当前位1的个数 |
---|---|---|---|---|
1(个位) | 2134 | 5 | 0 | (2134+1)x1=2135 |
10(十位) | 213 | 4 | 5 | (213+1)x10=2140 |
100(百位) | 21 | 3 | 45 | (21+1)x100=2200 |
1000 | 2 | 1 | 345 | 2x1000+345+1 = 2346 |
10000 | 0 | 2 | 1345 | (0+1)x10000=10000 |
综合起来最终结果就是18821.
|
|
上面看懂了之后,再来看这个解法,也很容易。
其实思路是一样的,只不过代码更加简洁了。