剑指offer:整数中1出现的次数
题目描述
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。
创新互联建站提供成都做网站、网站建设、外贸营销网站建设、网页设计,品牌网站制作,广告投放等致力于企业网站建设与公司网站制作,10年的网站开发和建站经验,助力企业信息化建设,成功案例突破上千多家,是您实现网站建设的好选择.
# -*- coding: utf-8 -*-
# @Time : 2019-07-09 16:50
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : numberOf1Between1AndN.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class Solution:
"""
要计算从1到n的数字中“1”出现的个数,暴力解题的时间复杂度很高,因此需要先观察规律进行归纳总结。
对于个位数: 0-9有1个,以10为间隔,即10-19有1个,20-29有1个。
对于十位数:10-19有10个,以100为间隔,即110-119有10个
对于百位数:100-199有100个,以1000为间隔,即1100-1199有100个
……
因此观察写出通项公式:
(n // (i * 10)) * i + min(max(n % (i * 10) - i + 1, 0), i)
"""
def NumberOf1Between1AndN_Solution(self, n):
if n < 1:
return 0
count = 0
i = 1
while i <= n:
count += n // (i * 10) * i + min(max(n % (i * 10) - i + 1, 0), i)
i *= 10
return count
分享名称:剑指offer:整数中1出现的次数
本文来源:http://myzitong.com/article/gehseg.html