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