整数中1出现的次数

问题陈述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例：

1
2
输入：n = 12
输出：5

问题解法

将从各位至最高位出现1的次数累加即可得到。

记当前位为cur，cur的左边所有位记为高位high；cur的右边所有位记为低位low；10i10^i记为位因子digit。

某位中出现1的次数计算方法

  1. 当cur=0时，此位1的个数计算公式为：high×digit。

  2. 当cur=1时，此位1的个数计算公式为：high×digit+low+1。

  3. 当cur=2，3，4，5，6，7，8，9时，此位1的个数计算公式为：（high+1）×digit。

变量递推

1
2
3
4
5
while high != 0 or cur != 0   //当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
   low += cur * digit    //将 cur 加入 low ，组成下轮 low
   cur = high % 10      //下轮 cur 是本轮 high 的最低位
   high /= 10          //将本轮 high 最低位删除，得到下轮 high
   digit *= 10        //位因子每轮 × 10

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class CountOne{
    public int countDigitsOne(int[] data){
        //初始化
        int high=data/10,cur=data%10,low=0;
        int res=0,digit=1;
        while(high!=0||cur!=0){
            if(cur==0)    res+=high*digit;  
            else if(cur==1)    res+=high*digit+low+1; 
            else    res+=(high+1)*digit; 
            //变量递推
            low+=cur*digit;
            cur=high%10;
            high/=10;
            digit*=10;
        }
        return res;
    }
}