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

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

来自牛客 剑指offer

题目描述

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

来自 Python-Offer,解释见博客

``` python 2 class Solution: def get_1_digits(self, n): if n <= 0: return 0 if n == 1: return 1 current = 9 * self.get_1_digits(n-1) + 10 ** (n-1) return self.get_1_digits(n-1) + current

def NumberOf1Between1AndN_Solution(self, n):
    if n < 10:
        return 1 if n >= 1 else 0
    digit = len(str(n))  # 位数
    low_nums = self.get_1_digits(digit - 1)  # 最高位之前的1的个数
    high = int(str(n)[0])  # 最高位
    low = n - high * 10 ** (digit-1)  # 低位

    if high == 1:
        high_nums = low + 1  # 最高位上1的个数
        all_nums = high_nums
    else:
        high_nums = 10 ** (digit - 1)
        all_nums = high_nums + low_nums * (high - 1)  # 最高位大于1的话，统计每个多位数后面包含的1
    return low_nums + all_nums + self.NumberOf1Between1AndN_Solution(low) ```