美文网首页
面试题32:从1到n整数中1出现的次数

面试题32:从1到n整数中1出现的次数

作者: liuqinh2s | 来源:发表于2019-03-19 17:18 被阅读0次

面试题32:从1到n整数中1出现的次数

题目

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

暴力算法

遍历从1到n的数,对每一个数进行解析,每个数的解析时间是\log_{10} n

算法时间复杂度是n\log(n)

public int NumberOf1Between1AndN_Solution(int n) {
    int sum = 0;
    for(int i=1;i<=n;i++){
        sum+=countOne(i);
    }
    return sum;
}

private int countOne(int n){
    int count = 0;
    while(n!=0){
        int a = n%10;
        if(a==1){
            count++;
        }
        n/=10;
    }
    return count;
}

剑指offer上的解法

n=21345为例,如果我们能把问题分解为:分别求出1~13451346~21345的解,然后实际只去求1346~21345,而对于求1~1345使用递归,那么问题就解决了。

如何求1346~21345的解呢?

我们将分类讨论,最高位1出现多少次?其余位1出现多少次?

最高位1出现在10000~19999中,总共10000个,但这不是一般情况,如果是10000~11345呢?(如果n=11345),所以这里要分类讨论一下,如果最高位小于2,那么总共出现1的数应该就是后面所有的数再加1,也就是1345+1(加1是因为从0算起)。剩余4位中比如千位是1,然后其它3位随便是什么,这样就有1\times10^3个,4位就是:4\times10^3,然后最高位还可以分别是1和2,所以总共是:2\times4\times10^3个。抽象成一般原理:最高位的值\times剩余位数\times10^{剩余位数-1}

因为只跟n的位数有关,所以算法时间复杂度是:\log n

public int NumberOf1Between1AndN_Solution(int n) {
    String s = Integer.toString(n);
    char[] c = s.toCharArray();
    return recurse(c, 0);
}

private int power10(int n){
    int result = 1;
    for(int i=0;i<n;i++){
        result*=10;
    }
    return result;
}

private int recurse(char[] c, int i){
    if(i==c.length-1){
        return 1;
    }
    int sum = 0;
    // 最高位1的个数
    if(c[i]>'1'){
        sum += power10(c.length-1-i);
    }else{
        sum += charToInt(c, i+1)+1;
    }
    // 其余位1的个数
    sum += (c[i]-'0')*(c.length-1-i)*power10(c.length-2-i);
    return sum+recurse(c, i+1);
}

private int charToInt(char[] c, int index){
    int temp = 0;
    for(int j=index;j<c.length;j++){
        temp *= 10;
        temp += (c[j]-'0');
    }
    return temp;
}

编程之美上的解法

如果我们发现了一个规律:

1到10,个位数是1的个数是:1

1到100,十位数是1的个数是:10

1到1000,百位数是1的个数是:100

\vdots

以此类推

依旧以21345为例。

先统计其中个位商上现1的个数:21340是10的2134倍,也就意味着以10为周期1会不断的在个位上出现2134次,再加上21341到21345中出现的21341这个也是个位出现1,所以总共是2135个个位1。

然后统计十位上出现1的个数:21300是100的213倍,以100为周期,十位每次出现10个1,也就是213*10,再加上从21301到21345,中2131x,这些10个数,总共是213*10+10

其实规律这就已经出来了,写成代码如下:

public int NumberOf1Between1AndN_Solution(int n) {
    int sum = 0;
    int count = 10;
    while(n*10/count!=0){
        int a = n/count;
        int b = n%count;
        if(b>(2*count/10)){
            b = (count/10);
        }else if(b>=(count/10)){
            b = n%(count/10)+1;
        }else{
            b = 0;
        }
        sum += a*count/10+b;
        count*=10;
    }
    return sum;
}

算法复杂度也很容易得到:\log n

相关文章

  • 面试题32:从1到n整数中1出现的次数

    面试题32:从1到n整数中1出现的次数 题目 输入一个正整数n,求从1到n这n个整数的十进制表示中1出现的次数。例...

  • 手撕数组

    【面试题51:数组中重复的数字】 【面试题32:求从1到n的整数中1出现的次数】 【面试题33:把数组排成最小的数...

  • 智力题(1的次数,金子分块)

    1出现的次数 输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包...

  • 《剑指offer》— JavaScript(31)整数中1出现的

    整数中1出现的次数(从1到n整数中1出现的次数) 题目描述 求出113的整数中1出现的次数,并算出1001300的...

  • 剑指Offer--1出现的个数

    整数中1出现的次数(从1到n整数中1出现的次数) 题目描述 求出113的整数中1出现的次数,并算出1001300的...

  • 剑指offer刷题记录(C++版本)(之四)

    31.整数中1出现的次数(从1到n整数中1出现的次数) 题目:求出113的整数中1出现的次数,并算出1001300...

  • JZ-031-从 1 到 n 整数中 1 出现的次数

    从 1 到 n 整数中 1 出现的次数 题目描述 求出1-13的整数中1出现的次数,并算出100-1300的整数中...

  • 剑指offer.C++.code31-35

    31. 整数中1出现的次数(从1到n整数中1出现的次数) 求出1-13的整数中1出现的次数,并算出100~1300...

  • Java日记2018-05-14

    第一题 从 1 到 n 整数中 1 出现的次数最直观的想法,求1到n中每个整数中1出现的次数,然后相加即可。而求每...

  • 4.8 垃圾题(2)。。。

    方法 暂无 注意点 暂无 目录 整数中1出现的次数(从1到n整数中1出现的次数) 数值的整数次方 整数中1出现的次...

网友评论

      本文标题:面试题32:从1到n整数中1出现的次数

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