剑指offer：整数中1出现的次数-创新互联

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

创新互联专注为客户提供全方位的互联网综合服务，包含不限于成都做网站、网站建设、外贸营销网站建设、泉港网络推广、微信小程序定制开发、泉港网络营销、泉港企业策划、泉港品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们大的嘉奖；创新互联为所有大学生创业者提供泉港建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

# -*- 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

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

本文名称：剑指offer：整数中1出现的次数-创新互联
本文链接：http://cdiso.cn/article/degede.html