【刷算法】整数中1出现的次数（从1到n整数中1出现的次数）

Shisui 发布于2019-08-23 10:29 / 2231人阅读

摘要：题目描述求出的整数中出现的次数并算出的整数中出现的次数为此他特别数了一下中包含的数字有因此共出现次但是对于后面问题他就没辙了。希望你们帮帮他并把问题更加普遍化可以很快的求出任意非负整数区间中出现的次数从到中出现的次数。

题目描述

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

分析 解法1

从1到n依次遍历，对于每一个数字都检查一遍它有几个1，然后累加即可，时间复杂度是O(N*logN)

解法2

例如103这样的数字：

个位数是1的有001，011，021，031，041，051，061，071，081，091，101，共11个

十位数是1的有010，011，012，013，014，015，016，017，018，019，共10个

百位数是1的有100，101，102，103

所以对于每一位来说，这一位数字是1的情况是由这一位本身、这一位的所有高位、这一位的所有低位，共同决定的，总结一下，对于abXcd来说：

X=0时，如果ab=01，那么就有00100~00199这100个数字都是X位是1的数字

X=1时，如果ab=01，那么就有00100~00199这100个数字 + ab100~ab1cd这个cd个数字

X>=2时，如果ab=01，那么就有00100~00199这100个数字 + 01100~01199这100个数字

其实这道问题在《编程之美》第134页有详解，看不懂可以看看书。

代码实现

// 解法1
function NumberOf1Between1AndN_Solution(n)
{
    var count = 0;
    for(var i = 1;i <= n;i++){
        var cur = i;
        while(cur !== 0) {
            if(cur % 10 === 1)
                count++;
            cur  = Math.floor(cur/10);
        }
    }

    return count;
}
// 解法2
function NumberOf1Between1AndN_Solution(n)
{
    var count = 0;
    var factor = 1;
    var cur = 0;
    var high = 0;
    var low = 0;
    
    while(divide(n, factor) !== 0){
        low = n - (divide(n, factor))*factor;
        cur = (divide(n, factor))%10;
        high = divide(n, factor*10);
        
        if(cur === 0)
            count += high*factor;
        else if(cur === 1)
            count += (high*factor + low + 1);
        else 
            count += (high+1)*factor;
        
        factor *= 10;
    }
    return count;
}
          
function divide(a, b){
    return Math.floor(a/b);        
}

GPU云服务器云服务器数据出现次数统计 php统计出现次数 js正则出现次数 js统计字母出现次数

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96389.html

由三道 LeetCode 题目简单了解一下位运算

摘要：使用位运算数组只出现一次数字的数组得到最低的有效位，即两个数不同的那一位看完上面的解法，我脑海中只有问号的存在，啥意思啊下面就让我们简单了解一下位运算并解析一下这三道题目。另，负数按补码形式参加按位与运算。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只出现一次以外...

daydream 2019-05-21 11:41 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：简单介绍一下位运算异或运算异或逻辑的关系是当不同时，输出当相同时，输出。另，负数按补码形式参加按位与运算。使一个数的最低位为零，可以表示为。，截止到这儿，三道题目中使用的位运算介绍完毕，那么这里我们插入一下的详细题解。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只...

刘明 2019-05-22 14:21 评论0 收藏0
剑指offer: 整数中1出现的次数（从1到n整数中1出现的次数）

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

forsigner 2019-08-16 18:23 评论0 收藏0
剑指offer中的算法题(PHP版)

摘要：二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。解法有两种，一种是递归法，一种是迭代法但是递归法计算的时间复杂度是以的指数的方式递增的，如果面试中千万不要用递归法，一定要用迭代法。二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和...

big_cat 2019-06-27 15:43 评论0 收藏0
C语言——一维数组算法问题

摘要：算法描述向数组中输入元素定义一个新数组将数组中的元素倒序存放将数组正序输出，注意结尾无空格的格式问题。最后打印出来数组中的元素，也就是非共有值，此处注意格式问题。问题1：将数组中的数逆序存放本题要求编写程序，将给定的n个整数存入数组中，将数组中的这n个数逆序存放，再按顺序输出数组中的元...

lifesimple 2021-11-15 11:38 评论0 收藏0