题目
输入一个整数n,求1n这n个整数的十进制表示中1出现的次数。例如,输入12,112这些整数中包含1的数字有1、10、11和12,1一共出现5次。
解题思路
- 从数字规律着手考虑问题
- 分析数字21345。
- 先看1236 ~ 21345中1出现的次数。1的出现我们从每一个不同的位考虑,比如千位上1出现多少次,百位上1出现多少次......
- 分析1出现在最高位(万位)的情况。因为万位为2>1,所以1出现在10000 ~ 19999这10000个数字的万位中,一共出现10000次。
-
扩展: 若万位数为1呢,比如:12345,此时1出现在万位的次数是不是会改变呢?
分析:1出现在10000 ~ 12345的万位上,即1出现的次数是10000 ~ 12345,是2346次(eg:10000、100001.....12345)共有2345+1次,也就是去掉最高位之后剩下的数字再加上1。 -
扩展: 若万位数为0呢,比如:02345,此时1出现在万位的次数是不是会改变呢? 那此时万位为1的次数为0
-------------------------再分析一下百位数-----------------------------
- 分析数字21345,将数据分为两段a = 213,b = 45
- 分析1出现在百位的次数,该数字百位数为3>1,则百位数出现的次数是(00100~ 00199)---->(11100~ 11199)---->(21100~21199)共(21+1)*100次,规律: 21=a/10
- 若百位数为1时,即a=211,则百位数出现的次数是(00100~ 00199)---->(11100~ 11199)---->(20100~20199) .(21100~20145) 共(20+1)*100+45+1次。规律: (a/10)*100+(b+1)次
- 若百位数为0时,即a=210,则百位数出现的次数是(00100~ 00199)---->(11100~ 11199)---->(20100~20199)共(a/10)*100次。
代码
int NumberOf1Between1AndN_2( unsigned int n)
{
int ones = 0;
for(int i = 1;i<=n;i*=10)
{
int a= n/i;
int b = n%i;
//cout << "a: " << a << endl;
//cout << "b: " << b << endl;
if(a %10 == 0)
{
ones += (a / 10) *i;
}
else if(a % 10 == 1)
{
ones += (a /10) * i + (b + 1);
}
else
{
ones += ((a /10) +1) *i;
}
cout << "ones:" << ones <<endl;
}
return ones;
}
- 普通常规方法
int NumberOf1_1(unsigned int num)
{
int sum_num = 0;
while(num%10 == 1)
{
sum_num++;
num = num/10;
}
return sum_num;
}
int NumberOf1Between1AndN_1(unsigned int n)
{
int number = 0;
for(unsigned int i = 1;i<=n;++i)
{
number+=NumberOf1_1(i);
}
return number;
}
网友评论