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

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