跳转至

LeetCode: 233. 数字 1 的个数

1、题目描述

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

示例:

输入: 13
输出: 6 
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

2、解题思路

  • 按照位进行统计,找到每个位对最终结果的增益
例如:2314

对于千位,在千位可能出现的是1000~1999,yigong 一共是1000个,也就是10^3,增益为1000

对于百位,如果百位为1,那么就是100~199,一共会出现100次,也是是10^2,但是,需要注意的就是,百位由于千位的影响,循环了多少次呢?2次,最后由于超出了2000,并且314已经超过了第三次循环,因此增益为300

对于十位,同样的,循环了23次,循环增益为23*10 = 230,并且我们发现14已经进入了下一个循环,但是只有5个,也就是10,11,12,13,14,因此十位总增益为235

对于个位数,单次循环增益为1,循环了231次,并且进入下次循环,增加1,一共是232

总的增益值 = 1000 + 300 + 235 + 232 = 1767

实例代码:

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n <= 0:
            return 0

        ans = 0
        base = 1
        num = n
        while num:
            remainder = num % 10
            ans += (num // 10) * base
            if remainder == 1:
                ans += n % base + 1
            elif remainder > 1:
                ans += base
            num //= 10
            base *= 10
        return ans