【LeeCode 中等 数学 python3】剑指 Offer 43. 1～n整数中1出现的次数

想要看更加舒服的排版、更加准时的推送
关注公众号“不太灵光的程序员”
每日八点有干货推送，微信随时解答你的疑问

剑指 Offer 43. 1～n整数中1出现的次数 python3

中等 数学

输入一个整数 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

# 97%
# 执行用时：32 ms
# 内存消耗：13.7 MB
class Solution:
    def countDigitOne(self, n: int) -> int:
        digit, res = 1, 0
        high, cur, low = n // 10, n % 10, 0
        # 当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
        while high != 0 or cur != 0:
            if cur == 0:
                res += high * digit
            elif cur == 1:
                res += high * digit + low + 1
            else:
                res += (high + 1) * digit
            # 将 cur 加入 low ，组成下轮 low
            low += cur * digit
            # 下轮 cur 是本轮 high 的最低位
            cur = high % 10
            # 将本轮 high 最低位删除，得到下轮 high
            high //= 10
            # 位因子每轮 × 10
            digit *= 10
        return res


if __name__ == "__main__":
    s = Solution()
    print(s.countDigitOne(824883294))
    print(s.countDigitOne(312))
    print(s.countDigitOne(3312))