政子的博客

技术|学习|随笔

CodingInterview-整数中1出现的次数

这道题没归纳出来，参考了网友的思路。不得不说，他的思路比书里的要清晰简单很多。

其实想明白了的话思路是很简单的。首先，先说几个 case。

首先求个位中的 1 的数量。可以观察到个位中的 1 是每 10 个数轮回一次，每次是 1 个 1(0-9)，所以用 n/10 即可计算出。但是还有特殊情况，就是如果 n 的个位是大于 1 的话，个位上 1 的个数会比刚刚计算的多一个，所以应该归纳为 n/10+(n%10>=1?1:0)。

接着，去求十位中 1 的数量。可以观察到十位中的 1 是每 100 个数字轮回一次，每次是 10 个 1(0-99），所以用 n/100*10 即可算出。但也有特殊情况，就是如果 n 的十位大于 1 的话，十位上 1 的个数会多很多，具体分为三种情况：我们定 l=n%100，那么如果 l>=20，则 1 会多出 10 个，如果 10<=l<20，则 1 会多出 l-10+1个，如果 l<10，则 1 没有多。

其余的数位类似。所以可以得到一个通用的公式：设当前的位数上的基数为 i，则当前位数上 1 出现的次数为：n/(i*10)*i+(if(n%(i*10)>=2*i) i else if(n%(i\*10)<i) 0 else n%(i*10)-i+1)。

具体的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        if(n<=0) return 0;
        int count=0;
        for(int i=1;i<=n;i*=10){
            int factor=i*10;
            count+=(n/factor)*i;
            int left=n%factor;
            if(left>=2*i) count+=i;
            else if(left<i) ;
            else count+=left-i+1;
        }
        return count;
    }
};