首页 > 试题广场 >

整数中1出现的次数（从1到n整数中1出现的次数）

[编程题]整数中1出现的次数（从1到n整数中1出现的次数）
  • 热度指数：401015 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数
例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

注意：11 这种情况算两次

数据范围：
进阶：空间复杂度 ，时间复杂度
示例1

输入

13

输出

6
示例2

输入

0

输出

0
算法知识视频讲解
添加回答
推荐
咩咩jiang头像 咩咩jiang
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
    //主要思路：设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），分别对每个数位上有多少包含1的点进行分析
    //根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i
    //当i表示百位，且百位对应的数>=2,如n=31456,i=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a%10+1)*100个点的百位为1
    //当i表示百位，且百位对应的数为1，如n=31156,i=100，则a=311,b=56，此时百位对应的就是1，则共有a%10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a%10*100）+(b+1)，这些点百位对应为1
    //当i表示百位，且百位对应的数为0,如n=31056,i=100，则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0~30）
    //综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%10==1)，需要增加局部点b+1
    //之所以补8，是因为当百位为0，则a/10==(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)
    int count=0;
    long long i=1;
    for(i=1;i<=n;i*=10)
    {
        //i表示当前分析的是哪一个数位
        int a = n/i,b = n%i;
        count=count+(a+8)/10*i+(a%10==1)*(b+1);
    }
    return count;
    }
};
编辑于 2015-08-18 23:21:43 回复(86)
Python
LYC_ley头像 LYC_ley 
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        base = 1
        res = 0
        while (base <=n):
            cur = n/base%10
            a = n/base/10
            b = n%base
            if(cur ==1):
                res = res+(a)*base + b +1
            elif(cur == 0):
                res = res +a*base
            else:
                res = res +(a+1)*base
            base =10*base
        return res
采用了题解方法的python版

发表于 2021-08-21 13:59:17 回复(0)
Python
tantantansq头像 tantantansq 
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        s=str(n)
        count=0
        for i in range(len(s)):
            a=10**i 
            high=int(n/(10*a))
            low=n%a
            cur=int(n/a)%10
            if cur==0:
                count+=high*a 
            elif cur==1:
                count+=high*a+(low+1)
            else:
                count+=(high+1)*a 
        return count
                

发表于 2021-08-08 15:05:25 回复(0)
Python
杨慧清头像 杨慧清 
'''
我是这么想的：把从1到n的数都转化为字符串，在转化成列表，在计算里边的1的个数。
'''
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count=0
        for i in range(n+1):
            res=list(str(i))
            for i in range(len(res)):
                if res[i]=='1':
                    count+=1
        return (count)

发表于 2020-10-15 09:10:54 回复(0)
Python
dwzhu头像 dwzhu
python大法好鸭 
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        total_num = 0 
        for i in range(1, n+1):
            num = str(i).count('1')
            total_num += num
        return total_num
基本思想：对于每一个数字，先把它装换为字符串，然后统计每个字符串中“1”出现的次数，累加起来即可。
编辑于 2021-02-27 21:32:38 回复(0)
Python
温润如玉的少年头像 温润如玉的少年
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        if n == 1:#如果输入n为1，则只出现一次
            count = 1
            return count
        # write code here
        count = 0
        for i in range(1,(n+1)):#当n大于1的时候，每次循环取余得到每个数字，压入空栈中，计#数1出现的次数即可
            i = int(i)
            string = []
            
            while i > 0:
                b = i%10
                string.append(b)
                i = int(i/10)
                
            c = string.count(1)
            count = count + c
        return count
发表于 2020-08-24 20:59:43 回复(0)
Python
听风你的头像 听风你的
python方式，理解为字符串查找元素
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        sum=0
        for i in range(1,n+1):
            if '1' in str(i):
                sum=sum+str(i).count('1')
        return sum
发表于 2020-08-16 16:04:49 回复(0)
Python
牛客702212974号头像 牛客702212974号
# -*- coding:utf-8 -*-
#每次对10取模，然后判断个位数是否为1,然后对当前n地板除10,
#n//10,其值再用于下次对10取模
#两次循环暴力求解，n较大时，效率低
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        for i in range(1, n+1):
            while i:
                a = i % 10
                if a == 1:
                    count = count + 1
                i = i // 10
        return count
发表于 2020-08-07 14:53:45 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        for i in range(1,n+1):
            for j in str(i):
                if j == '1':
                    count +=1
        return count
将待求数转化成从字符串,并遍历1~n
发表于 2020-07-25 17:27:13 回复(0)
Python
牛客770473387号头像 牛客770473387号
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        for a in range(n+1):
            A = str(a)
            for i in A:
                if i == '1':
                    count += 1
        return count
                
                
发表于 2020-06-16 11:50:58 回复(0)
Python
西二旗小王头像 西二旗小王
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        for i in range(n+1):
            while i > 0:
                if i%10 == 1:
                    count += 1
                i //= 10
        return count
发表于 2020-06-14 21:23:06 回复(0)
Python
橘子汽水超人2号头像 橘子汽水超人2号

数字从小到大，把每个数包含的1的个数放到一个字典里去。
每一个大数分解成最高位+余下数，比如2021分解为2和021两部分，分别判断最高位和分出来的那部分相加即可，缺点是比较费空间 
# -*- coding:utf-8 -*-
import collections
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        sum = 0
        numLib = {}
        N = 1
        for num in range(n+1):
            numLib.setdefault(num,0)
            numLib[num]=(numLib[num % N]+int(num//N==1))
            sum+=numLib[num]
            if num==10*N-1:
                N*=10
        return sum
常规解法： 
class Solution:   # 常规解法
    def NumberOf1Between1AndN_Solution(self, n):
        sum = 0
        for i in range(n+1):
            while i//10>0:
                if i%10==1:
                    sum+=1
                i=i//10
            sum+=int(i%10==1)
        return sum





编辑于 2020-06-02 09:37:13 回复(0)
Python
牛客473055830号头像 牛客473055830号
import re
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        l = [str(i) for i in range(1, n + 1)]
        count = 0
        for i in l:
            count += i.count('1')
        return count
发表于 2020-05-28 23:18:15 回复(0)
Python
一直爬的蜗牛头像 一直爬的蜗牛 
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        for i in range(1,n+1):
            str_i = str(i)
            count += str_i.count("1")
        return count

发表于 2020-05-24 00:23:29 回复(0)
Python
牛客124928456号头像 牛客124928456号
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        s=''
        for i in range(1,n+1):
            s=s+'%s'%i
        return(s.count('1'))
发表于 2020-05-20 19:59:25 回复(0)
Python
牛客112761377号头像 牛客112761377号

一位一位的计算

思路来自B站视频。以下是原链接
https://www.bilibili.com/video/BV1uJ411573j?t=1824
假设n = 7543 [x] 29
如果要让百位的x = 1，那么需要考虑以下几种情况：

  1. 百位的x就是1的时，考虑前面4位数小于7543的情况，一共是0000-7542=7543种可能，而后面2位数的取值可以任意，00-99=100种可能
    • 总次数 = 7543 * 100
  2. 考虑前面4位数就取7543，若百位的x > 1，如n = 7543 [6] 29，那么就可以在比n小的数字中取到百位是1的数字，而后2位数还是可以随便取，还是100种可能
    • 总次数 = 1 * 100
  3. 若百位的x = 1，如 n = 7543 [1] 29，此时后两位就不能随便取值(因为要小于n)，那么取值范围就是 00-29=30种可能
    • 总次数 = 1 * 30
  4. 若百位的x = 0，如 n = 7543 [0] 29，那么不可能取到百位是1的情况，因为一定比n大 
    class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # 运行时间：31ms  占用内存：5860k
        m = len(str(n))  # 数字的长度
        count = 0
        for i in range(1, m+1):
            high = n // 10 ** i                       # 找到当前位之前的位数
            mid = n % 10 ** i // 10 ** (i - 1)        # 找当前位
            low = n % 10 ** (i - 1)                   # 找当前位后面的位数
            # 第(1)个情况
            count += high * (10 ** (i - 1))

            if mid > 1:
                # 第(2.1)个情况
                count += 10 ** (i - 1)
            elif mid == 1:
                # 第(2.2)个情况
                count += (low + 1)
        return count

编辑于 2020-04-22 17:58:30 回复(0)
Python
夜深忽梦少年事丶头像 夜深忽梦少年事丶 
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        while n > 0:
            string = str(n)
            for i in string:
                if i == "1":
                    count += 1
            n = int(n) - 1
        return count

发表于 2020-04-09 17:41:37 回复(0)
Python
Julian_Zha头像 Julian_Zha
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        if n < 1:
            return 0

        count = 0
        for x in range(1, n + 1):
            for part in str(x):
                len_part = len(part)
                for i in range(len_part):
                    if str(1) == part[i]:
                        count += 1

        return count
主要思路为将整型数据利用str()很方便地转化为字符串，这样可以很快地将各个位上的数字与1进行比较。
发表于 2020-04-01 19:12:19 回复(0)
Python
谢小橙头像 谢小橙
以n=3459082190为例，分成三段：lowNum（低位），midNum（中位），highNum（高位）
【1】如果midNum为1（highNum=3459082，midNum=1，lowNum=90），可以有两种情况：1的右边取大于90的情况和右边取小于等于90的情况，如果右边取大于90，左边只能取小于highNum的数（0 ~ 3459081）；如果右边取小于等于90，左边可以取等于及小于highNum的数（0 ~ 3459082）。
【2】如果midNum大于1（highNum=34590，midNum=8，lowNum=2190），当该位为1时，左边取0~34590，右边可以取任意四位数，也就是10^4^种取法。
【3】如果midNum小于1（highNum=3459，midNum=0，lowNum=82190），当该位为1时，必须得跟higNum借一位，所以左边取0~3458，右边可以取任意五位数，也就是10^5^种取法。

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        i=0
        sum_num=0
        highNum=1 # 初始化
        while highNum!=0:
            lowNum=n%(10**i)
            midNum=n//(10**i)%10
            highNum=n//(10**(i+1))
            if midNum == 1:
                sum_num+=(highNum+1)*(lowNum+1)+highNum*(10**i-lowNum-1)
            if midNum >1:
                sum_num+=(highNum+1)*(10**i)
            if midNum <1:
                sum_num+=highNum*(10**i)
            i+=1
        return sum_num

编辑于 2020-03-17 12:04:13 回复(0)
Python
但行好事-莫问前程头像 但行好事-莫问前程
暴力求解
  1. 遍历从 1-n 的每个整数，将整数转为str
  2. 统计str中所有1的个数 
    # -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        (852)# write code here
        cnt = 0
        for i in range(1, n+1):
            i = str(i)
            cnt += i.count('1')
        return cnt
        

编辑于 2020-03-04 10:04:59 回复(0)
Python
朝夕_头像 朝夕_ 
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        if n < 1:
            return 0
        else:
            a = 0
            for i in range(1,n+1):
                a += str(i).count("1")
        return a

编辑于 2020-02-24 10:57:47 回复(0)
提交观点

问题信息

基础数学
来自：编程题练习卷
难度：
95条回答 184264浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号