欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)

程序员文章站 2022-06-20 18:32:39
1 题目描述 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 ......

1 题目描述

  求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。acmer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

2 思路和方法

  统计整数n中的每个十进制位中1出现的次数,再累加起来。 对于每一位来说可以把一个数拆分为 前面( begin)+中间( middle)+后面(end )。 1234的百位 = 1+2+34 

  (编程之美)找数字规律,五行代码:
  首先要知道以下规律:

  从 1 至 10,在它们的个位数中,1出现了 1 次;
  从 1 至 100,在它们的十位数中,1出现了 10 次;
  从1至1000,在它们的百位数中,1出现了100次;

  依次类推,从 1 至 10 i,在它们的左数第二位(右数第 i 位),1出现了 (10 i-1)次。这个规律很容易验证。

  我们以n=21345为例来使用这个规律。首先分析个位1出现了几次。从1~21340数字1总共出现了2134*1次,最后剩下21341、21342、21343、21344、21345,所有还出现1次数字1。所以个位共出现1的次数为2135次。

  接下来分析十位中1出现了几次。从1~21300数字1总共出现了213*10次,剩下的数字从 21301至 21345,它们最大的十位数是 4 > 1,所以还有10次。所以十位共出现2140次。

  接下来分析百位中1出现了几次。从1至21000数字1共出现了21*100次。剩下的数字是21001~21345,最大的百位数是3,大于1,所以还有100次。所以百位中1共出现了2200次。

  接下来分析千位中1出现了几次。从120000数字1共出现了2*1000次。剩下的数字是2000121345,最大的千位数是1,等于1,这种情况稍微比较复杂,因为它并不包括所有千位为1的数字,即1000个,这种情况取决于低位上的数字,为345+1=346次。最后总计2346次。

  接下来分析万位中1出现了几次。因为它是最高位了因此直接看最高位的数字,即2,2>1。很显然10000~19999中1在万位共出现了10000次。如果最高位等于1那就和上一步的思想一样。

通过以上几步的分析我们可以得出结果:1~21345中1共出现了18821次。

3 c++核心代码

简洁版:https://blog.csdn.net/typantk/article/details/88386888(讲解的太好了)

 1 class solution {
 2 public:
 3     int numberof1between1andn_solution(int n)
 4     {
 5         int ones = 0;
 6         for (long m = 1; m <= n; m *= 10)
 7             ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
 8         return ones;
 9     }
10 };

代码较多

 1 class solution {
 2 public:
 3     int numberof1between1andn_solution(int n)
 4     {
 5         int temp = n;
 6         int last;
 7         int result = 0;
 8         int base = 1;
 9         while(temp){
10             last = temp%10;     //个位数是否为1
11             temp = temp/10;    //去掉个位数
12             result += temp*base;
13             if (last==1){
14                 result += n%base + 1;
15             }
16             else if(last>1){
17                 result += base;
18             }
19             base *= 10;
20         }
21         return result;
22     }
23 };

4. c++完整代码

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 long long fun(long long n)
 6 {
 7     if (n < 1)
 8         return 0;
 9     long long count = 10, num = 0, begin, middle, end, m;
10     begin = n;
11     middle = 0;
12     end = 0;
13     while (begin)
14     {
15         begin = n / count;
16         m = n%count;
17         middle = m / (count / 10);
18         end = m % (count / 10);
19         if (middle > 1)
20             num = num + (count / 10) * (begin + 1);
21         else if (middle == 1)
22             num = num + (count / 10) * begin + (end + 1);
23         else
24             num = num + (count / 10) * begin;
25         count = count * 10;
26     }
27     return num;
28 }
29 
30 int main()
31 {
32     long long n, m;
33     while (scanf("%lld %lld", &n, &m) != eof)
34     {
35         if (n>m)
36             printf("%lld\n", fun(n) - fun(m - 1));
37         else
38             printf("%lld\n", fun(m) - fun(n - 1));
39     }
40     printf("%\n");
41 
42     system("pause");
43     return 0;
44 }

https://blog.csdn.net/zhoubin1992/article/details/47361969

参考资料

https://blog.csdn.net/typantk/article/details/88386888(讲解的太好了)

https://blog.csdn.net/qq_25343557/article/details/79330274(讲解的太好了)