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;
}
};