leetcode 233. 数字 1 的个数

特别鸣谢：来自夸夸群的 醉笑陪公看落花@知乎，王不懂不懂@知乎，QFIUNE@csdn
感谢小伙伴们督促学习，一起进步

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

输入：n = 13
输出：6
示例 2：

输入：n = 0
输出：0

解题思路

以推算 4550 为案例，推算abcd数字的时候公式应该如何变动

• 找到 不同位数区间的规律，发现0~m个9 区间中，有 m*(10^(m-1)) 个1 令 f(m) = m*(10^(m-1))
• 如果m位a大于1，则带来 a*f(m)+10^m 个1
• 如果m位a ==1，则带来 a*f(m) + bcd 个1
• 如果m位a ==0, 则不带来1

代码

class Solution:
    def countDigitOne(self, n: int) -> int:
        ab = n
        m = -1
        ans = 0
        while(ab!=0):
            b = ab%10
            ab //=10
            m+=1
            if b > 1:
                ans += 10 ** m
            if m > 0:
                ans += b * m * (10 ** (m - 1))
        ab = n
        while(ab!=0):
            a = ab//(10**m)
            if a==1:
                ans += ab%(10**m)+1
            ab %=(10**m)
            m-=1
        return ans