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