剑指Offer:整数中1出现的次数
题目
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。
思路 + 代码
暴力穷举会超出时间,这道题的关键是找规律。
一个数字,分解为十位、百位、千位…上来看。
因为数字由1~n组成,既有十位、百位、千位等组成。
首先,每十个数,个位数字出现一次。每百位数,个位数字出现十次…
n/(i*10)*i, i=1, 10, 100, ...
其次,对于后面的数,例如1611,从百位数来看,前面的数字 1611/100*10=160, 后面数字为11,因此后面的个位数为 1+1=2, 而1620和1650后面的个位数字都是10个,因此后面个位数字:
max(min(n%(i*10)-i+1,0),i)
1 | import java.lang.Math; |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 孙云增的博客!
评论