剑指offer31-整数中1出现的次数

题目描述

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

知识点回顾

查找、数学

参考：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/

根据当前位 curcur 值的不同，分为以下三种情况：

变量递推公式：
设计按照 “个位、十位、...” 的顺序计算，则 high / cur / low / digithigh/cur/low/digit 应初始化为：
high = n // 10
cur = n % 10
low = 0
digit = 1 # 个位
因此，从个位到最高位的变量递推公式为：
while high != 0 or cur != 0: # 当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
   low += cur * digit # 将 cur 加入 low ，组成下轮 low
   cur = high % 10 # 下轮 cur 是本轮 high 的最低位
   high //= 10 # 将本轮 high 最低位删除，得到下轮 high
   digit *= 10 # 位因子每轮 × 10

代码

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        digit=1
        cur=n%10
        low=0
        high=n//10
        sum=0
        while (cur or high):
            if cur==0:
                sum+=high*digit
            elif cur ==1:
                sum+=(high*digit+low+1)
            else:
                sum+=(high+1)*digit
            digit*=10
            cur=high%10
            low=n%digit
            high=high//10
        return sum