欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-10 13:59:17
想要看更加舒服的排版、更加准时的推送关注公众号“不太灵光的程序员”每日八点有干货推送,微信随时解答你的疑问剑指 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%# 执行用时....

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

剑指 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))

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

本文地址:https://blog.csdn.net/qq_23934063/article/details/107525047