题目
给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例:
1 | 输入: 13 |
思路
看到这道题的第一反应是用一种类似于筛法的方式,比如数字3虽然没有包含1,可以在数字3左右添加1构造出 31和13,似乎可以使用这种方式由一位数开始用递归将所有包含1的数字都构造出来.但是发现并不能很好解决数字重复的问题 以及包含1的数字的构造不是很好实现.于是作罢.
进一步挖掘问题,一个数字每位数之间相互独立互不影响,我们可以先统计范围内个位数是1的数字有多少个.然后以此类推,其中又分为三种情况 数字n中该为数 为0 为 1 或者大于1.
- n = 233333333 left = 2333333 right = 33, 百位数上总数应为233334 *100
- n = 233333033,left = 2333330,right = 33 ,因为在百位数为1时,左右数字组合可能大于233333033,比如233333100, 所以百位数上1的总数为233333*100
- n = 233333133,left = 2333331,right = 33,左方数字为2333331时,结果可能大于n,比如233333134,所以百位数上1的总数为233333*100+33+1
1 | long countDigitOne(long n) { |
其中result += (left+8)/10*index;
个人认为是一种很技巧性的方法将数字与处理结果对于,省去了多个if判断.