美文网首页
面试题43:1~n整数中1出现的次数

面试题43:1~n整数中1出现的次数

作者: 潘雪雯 | 来源:发表于2020-05-05 23:15 被阅读0次

题目

输入一个整数n,求1n这n个整数的十进制表示中1出现的次数。例如,输入12,112这些整数中包含1的数字有1、10、11和12,1一共出现5次。

解题思路

  • 从数字规律着手考虑问题
  1. 分析数字21345
  2. 先看1236 ~ 21345中1出现的次数。1的出现我们从每一个不同的位考虑,比如千位上1出现多少次,百位上1出现多少次......
  3. 分析1出现在最高位(万位)的情况。因为万位为2>1,所以1出现在10000 ~ 19999这10000个数字的万位中,一共出现10000次。
  4. 扩展: 若万位数为1呢,比如:12345,此时1出现在万位的次数是不是会改变呢?
    分析:1出现在10000 ~ 12345的万位上,即1出现的次数是10000 ~ 12345,是2346次(eg:10000、100001.....12345)共有2345+1次,也就是去掉最高位之后剩下的数字再加上1。
  5. 扩展: 若万位数为0呢,比如:02345,此时1出现在万位的次数是不是会改变呢? 那此时万位为1的次数为0
    -------------------------再分析一下百位数-----------------------------
  • 分析数字21345,将数据分为两段a = 213,b = 45
  1. 分析1出现在百位的次数,该数字百位数为3>1,则百位数出现的次数是(00100~ 00199)---->(11100~ 11199)---->(21100~21199)共(21+1)*100次,规律: 21=a/10
  2. 若百位数为1时,即a=211,则百位数出现的次数是(00100~ 00199)---->(11100~ 11199)---->(20100~20199) .(21100~20145) 共(20+1)*100+45+1次。规律: (a/10)*100+(b+1)
  3. 若百位数为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;
}

完整代码见GitHub

相关文章

网友评论

      本文标题:面试题43:1~n整数中1出现的次数

      本文链接:https://www.haomeiwen.com/subject/ynkbghtx.html