面试题43. 1～n整数中1出现的次数

题目

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

限制：

1 <= n < 2^31
注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/

解法

问题的本质是统计每个位置上出现1的次数，会出现什么情况可以罗列出来，找到规律就好了。

https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/wo-de-jian-dan-jie-fa-by-ai-bian-cheng-de-zhou-n-2/
从leetcode中找到的例子解释：

image.png
代码部分大家大同小异。

class Solution():
    def countDigitOne(self, n):
        res = 0
        i = 1  # 个位开始
        while n // i != 0:
            high = n//(i*10) # 高位数
            current = (n//i) % 10  # 第i位数
            low = n - (n//i) * i  # 低位数
            if current == 0:    # 全部高位决定，等于0低位
                res += high * i
            elif current == 1:
                res += high * i + low + 1  # 加一是100到100+low闭区间
            else:
                res += (high+1) * i
            i *= 10
        return res

总结

分三种情况讨论。