剑指offer-面试题32.从1到n整数中1出现的次数

74 阅读 0 评论 49 点赞

我是靠谱客的博主幽默鸡，最近开发中收集的这篇文章主要介绍剑指offer-面试题32.从1到n整数中1出现的次数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目:输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字中1，10，11和12,1一共出现了5次

本题可以直接变量1到n的n个数然后分别计算每个数中1的个数，然而这种方法是效率很低下的书上给出了一共方法，去找数n各个位置上出现1的规律，在这里我就不再描述具体的规律推倒过程，只是给出这样一个普遍性的规律。

1.对每一位上面的数字，当该数字等于零时，该位上1的个数等于高位*该位的位数

2.对每一位上面的数字，当该数字等于1时，该位上1的个数等于高位*该位的位数+低位数加1

3.对每一位上面的数字，当该数字等于非0非1时，该位上1的个数等于（高位+1）*该位的位数

例如52014

该数字十位数为1，那么十位上1的个数=（520）*10+（4+1）=5205

该数字百位数为0，那么百位上1的个数=(52)*100=5200

该数字千位数为2，那么千位上1的个数=（5+1）*1000=6000

该数字个位数为4，那么个位上1的个数=(5201+1)*1=5202

该数字万位上为5，那么万位上1的个数=(0+1)*10000=10000

那么1-52014中所有1的个数为:5205+5200+6000+5202+10000=31607

实现代码如下:

 1 #include <iostream>
 2 using namespace std;
 3
 4 int CountOneSum(int Number)
 5 {
 6
int HighPos=0;
 7
int LowPos=0;
 8
int count=0;
 9
int CurrPos=0;
10
11
int k=1;
12
13
while(Number/k!=0)
14 
{
15
LowPos=Number-(Number/k)*k;
16
CurrPos=(Number/k)%10;
17
HighPos=Number/(k*10);
18
19
switch(CurrPos)
20 
{
21
case 0:
22
count+=(HighPos*k);
23
break;
24
case 1:
25
count+=(HighPos*k+LowPos+1);
26
break;
27
default:
28
count+=((HighPos+1)*k);
29 
}
30
31
k=k*10;
32 
}
33
return count;
34 }
35
36 int main (int argc, char* argv[])
37 {
38
int num;
39
cout<<"Please input the number you want to count '1': ";
40
cin>>num;
41
int OneCount=0;
42
OneCount=CountOneSum(num);
43
cout<<"The Count of '1' is: "<<OneCount<<endl;
44
system("pause");
45
return 0;
46 }