LeetCode 233 - 数字 1 的个数

AlightYoung 8/13/2021 LeetCode

困难

原题链接：https://leetcode-cn.com/problems/number-of-digit-one/ (opens new window)

# 题目描述

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1

输入：n = 13
输出：6

示例 2

输入：n = 0
输出：0

提示

0 <= n <= 2 * 10^9

# Python题解

之前尝试了个暴力解，但是测试数据较大，基本不存在暴力解，但还是贴个代码

class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        for i in range(n + 1):
            numlist = list(str(i))
            for j in range(len(numlist)):
                if numlist[j] == '1':
                    count += 1
        return count

1
2
3
4
5
6
7
8
9
10
11
12
13

# 社区题解

暴力解之后，尝试了另一个思路，但是没推出公式，然后就在官解的评论区看到了这个同思路解，就抄了下来。

贴一下大佬的评论地址：逆模因 - 数字 1 的个数 (opens new window)

"""
从低往高位，计算每一位的数量：
第1位上的1有：1 + (n - 1) / 10
第2位上的1有：(1 + (n / 10 - 1) / 10) * 10
第3位上的1有：(1 + (n / 100 - 1) / 10) * 100
...
第k + 1位上的1有：(1 + (n / (10 ^ k) - 1) / 10) * (10 ^ k)
如果n的第k + 1位上是1，则说明可能没有填满该位，计算第k + 1位的数量时还要 - 10 ^ k + 1 + n % (10 ^ k)，相当于独立计算
"""
class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        m, ans = 1, 0
        while n >= m:
            ans += (1 + (n // m - 1) // 10) * m
            if n // m % 10 == 1:
                ans = ans - m + 1 + n % m
            m *= 10
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 官方题解

def countDigitOne(n: int) -> int:
    """
    分别统计各位可能出现的的1
    -----------------------个位---------------------------
    比如1234，个位上会出现1的情况， 01，11 21 ... 1231
    loop = 1234 // 10 = 123，即会出现123次这样的循环区间 [1,10 ]，[11, 20]...[1220, 1230]
    每个loop[0, 10]仅有1位个位1，所以所有循环的个位1总数位 123 * 1
    接下来只要取得剩余部分可能出现1的情况
    rest = 1234 % 10 = 4 这个余数需要分为两种情况
    >= 1时，会出现一次个位1
    < 1时，不会出现个位1
    sum += 123 * 1 + min(max(rest - 10^0 + 1, 0), 1)
    -----------------------十位---------------------------
    同理可得 十位的 1 的情况
    loop = 1234 // 10 ^ 2 = 12 出现12次循环区间 总循环区间范围[0, 1200]
    每个loop[0, 100]有10个十位1，所以所有循环的个位1总数位 12 * 10
    剩余部分 rest = 1234 % 100 = 34，分为三种情况
    < 10 不会出现十位1
    >= 10 < 20 会出现 rest - 10 + 1次十位1
    >= 20 出现全部（10次）十位1的情况
    sum += 34 * 10 + min(max((rest - 10^1 + 1), 0), 10)
    -----------------------百位---------------------------
    loop = 1234 / 10 ^ 3 = 1 总区间 [0, 1000]
    每个区间一共有100个百位1，1 * 100
    rest = 1234 % 1000 = 234，同样为三种情况
    < 100 不会出现百位1
    >=100 < 200 出现 rest - 100 + 1
    >= 200 出现全部100个
    sum += 1 * 100 + min(max(rest - 10^3 + 1, 0), 100)
    -----------------------n位---------------------------
    以此类推到所有位...
    """
    # mulk为10^k
    mulk, ans = 1, 0
    while n >= mulk:
        ans += (n // (mulk * 10) * mulk) + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)
        mulk *= 10
    return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 总结

暴力解不可取！最后好奇一下时间的差距，发现大佬的算法算2*10^9000次方花了4s，而如果是暴力解计算2*10^7这个用例都得14s...

珍爱生命，远离暴力。

看了几天看懂了官解，有用的知识增加了

数位dp的方法还没懂 😦

A·Y

Choose mode