• LeetCode233数字1的个数-容易理解的组合数学方法



    tags: LeetCode DSA

    题目

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

    示例 1:

    输入:n = 13
    输出:6
    示例 2:

    输入:n = 0
    输出:0

    提示:

    0 <= n <= 1e9

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/number-of-digit-one
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解题思路

    这里面的例子有问题, 说是0~10^9, 结果早就超出1e9了…

    首先来看这样一个例子:13, 怎样来计算数字1的个数呢?

    一个比较直观的思路就是先计算1~10中数字1的个数, 然后计算11~13中数字1的个数.

    显然: 1~10中含有的1的个数为2, 但是在11~13中, 应该怎么计算呢? 这里可以进一步分解计算, 先计算个位中含有1的数量, 这里的话就是先计算1~3的1的个数, 即为1, 然后对上一位(即十位1)分类讨论, 如果是1, 那么1的个数就要加上13-10=3, 这样才能计算出总的1的个数,即最终的答案为2+1+3=6.

    有了这个分析, 我们下面只需要找出计算1~10这样类型的数字1个数公式即可, 进一步可以推广为计算:
    f ( x ) : = { 1 ∼ x 中1的个数 } , 其中 x : = A × 1 0 B . f(x):=\{1\sim x\text{中1的个数}\}\text{, 其中}x:=A\times 10^B. f(x):={1x1的个数}其中x:=A×10B.
    怎么找出这个公式呢, 先以100为例进行分析, 对于100, A = 1 , B = 2 A=1,B=2 A=1,B=2, 那么由组合数学的基本计数原理, 对十位和个位中能取到的数进行分类讨论, 对于仅含有1个1的数, 1可以固定在个位或者十位或者百位, 这样的情况有 9 × 2 + 1 9\times2+1 9×2+1个, 这里包含了十位为0的情况, 这样就不用额外讨论10以内的数了, 最后的1是针对百位而言的, 然后是含有两个1的数, 显然这样的数只有一个, 即11, 那么就可以得到:
    f ( 100 ) = 2 × 9 + 1 + 2 × 1 = 21 , f(100)=2\times9+1+2\times1=21, f(100)=2×9+1+2×1=21,
    这里偷个懒, 我找到了一个计算1~1eN1的数目的公式, 调用了一下LeetCode的提交API, 即:
    f ( 1 0 B ) = B ⋅ 1 0 B − 1 + 1 , f(10^B)=B\cdot10^{B-1}+1, f(10B)=B10B1+1,
    证明过程也比较Trival, 就是幂级数的求导整理运算, 首先通过逐位计算1的数量得到下面的式子,
    f ( 1 0 B ) = ( B 1 ) ⋅ 9 B − 1 ⋅ 1 + ( B 2 ) ⋅ 9 B − 2 ⋅ 2 + ( B 3 ) ⋅ 9 B − 3 ⋅ 3 + ⋯ + 1 f(10^B)=\binom B1\cdot9^{B-1}\cdot1+\binom B2\cdot9^{B-2}\cdot2+\binom B3\cdot9^{B-3}\cdot3+\cdots+1 f(10B)=(1B)9B11+(2B)9B22+(3B)9B33++1
    写成求和的形式, 可得到:
    f ( 1 0 B ) = ∑ k = 1 n k ( n k ) 9 n − k = ∑ k = 0 n ( n − k ) ( n k ) 9 k , f(10^B)=\sum_{k=1}^nk\binom nk9^{n-k}=\sum_{k=0}^n(n-k)\binom nk9^k, f(10B)=k=1nk(kn)9nk=k=0n(nk)(kn)9k,

    g ( x ) = ∑ k = 0 n ( n − k ) ( n k ) x k = ( n + 1 ) ∑ k = 0 n ( n k ) x k − ∑ k = 0 n ( n k ) ( k + 1 ) x k , g(x)=\sum_{k=0}^n(n-k)\binom nkx^k=(n+1)\sum_{k=0}^n\binom nkx^k-\sum_{k=0}^n\binom nk(k+1)x^k, g(x)=k=0n(nk)(kn)xk=(n+1)k=0n(kn)xkk=0n(kn)(k+1)xk,
    两边对 x x x积分得到:
    ∫ g ( x ) d x = ( 1 + x ) n + 1 − x ( 1 + x ) n = ( 1 + x ) n \int g(x)\text dx=(1+x)^{n+1}-x(1+x)^n=(1+x)^n g(x)dx=(1+x)n+1x(1+x)n=(1+x)n
    于是得到:
    g ( x ) = n ( 1 + x ) n − 1    ⟺    f ( 1 0 B ) = n ⋅ 1 0 n − 1 + 1. g(x)=n(1+x)^{n-1}\iff f(10^B)=n\cdot10^{n-1}+1. g(x)=n(1+x)n1f(10B)=n10n1+1.

    但是, 只有这一个例子是不行的, 还不能得到 f ( x ) f(x) f(x)的表达式.(因为A需要大等1)

    下面再来看7000这个数, 同100的讨论, 要计算 f ( 7000 ) f(7000) f(7000),需要分别计算仅含有1个1的数, 含有两个1的数, 含有三个1的数以及含有4个1的数, 可以得到:
    f ( 7000 ) = f ( 7 × 1 0 3 ) = [ 9 3 ( 3 0 ) + 6 ⋅ 9 2 ( 3 1 ) ] × 1 (仅含有一个1) + [ 9 2 ( 3 1 ) + 6 ⋅ 9 1 ( 3 2 ) ] × 2 (含有2个1) + [ 9 1 ( 3 2 ) + 6 ⋅ ( 3 3 ) ] × 3 (含有3个1) + 3 + 1 (含有4个1, 只有1111)

    f(7000)=f(7×103)=[93(30)+692(31)]×1(仅含有一个1)+[92(31)+691(32)]×2(含有2个1)+[91(32)+6(33)]×3(含有3个1)+3+1(含有4个1, 只有1111)" role="presentation" style="position: relative;">f(7000)=f(7×103)=[93(30)+692(31)]×1(仅含有一个1)+[92(31)+691(32)]×2(含有2个1)+[91(32)+6(33)]×3(含有3个1)+3+1(含有4个1, 只有1111)
    f(7000)==+++f(7×103)[93(03)+692(13)]×1(仅含有一个1)[92(13)+691(23)]×2(含有21)[91(23)+6(33)]×3(含有31)3+1(含有41, 只有1111)
    这里要注意对首位(本例中为千位)的讨论, 这里的乘以6指的是只能选0,2,3,4,5,6这6个数, 才能保证1的个数确定, 整理一下, 就可以得到最后的结果:
    f ( x ) = f ( A × 1 0 B ) = [ 9 B ( B 0 ) + ( A − 1 ) ⋅ 9 B − 1 ( B 1 ) ] × 1 + [ 9 B − 1 ( B 1 ) + ( A − 1 ) ⋅ 9 B − 2 ( B 2 ) ] × 2 + [ 9 B − 2 ( B 2 ) + ( A − 1 ) ⋅ 9 B − 3 ( B 3 ) ] × 3 + ⋯ + B + 1
    f(x)=f(A×10B)=[9B(B0)+(A1)9B1(B1)]×1+[9B1(B1)+(A1)9B2(B2)]×2+[9B2(B2)+(A1)9B3(B3)]×3++B+1" role="presentation" style="position: relative;">f(x)=f(A×10B)=[9B(B0)+(A1)9B1(B1)]×1+[9B1(B1)+(A1)9B2(B2)]×2+[9B2(B2)+(A1)9B3(B3)]×3++B+1
    f(x)==+++f(A×10B)[9B(0B)+(A1)9B1(1B)]×1[9B1(1B)+(A1)9B2(2B)]×2[9B2(2B)+(A1)9B3(3B)]×3+B+1

    这里在写代码的时候为方便, 直接用Python的组合数API了, 就是from math import comb, 比较方便, 要是自己写的话也不难, 尾递归实现阶乘然后套公式即可.

    代码

    from math import comb
    
    
    class Solution:
        def countDigitOne(self, n: int) -> int:
            if n == 0:
                return 0
    
            def count1(A, B):
                if A == 0:
                    return 0
                elif B == 0:
                    return 1
                elif A == 1:
                    return B * 10**(B - 1) + 1
                else:
                    A -= 1
                    tmp = 9**B + A * 9**(B - 1) * B + B + 1
                for i in range(2, B + 1):
                    tmp += i * (9**(B - i + 1) * comb(B, i - 1)) + \
                        i * (A * 9**(B - i) * comb(B, i))
                return tmp
    
            def digit(n):
                # 计算位数
                arr = []
                while n:
                    arr.append(n % 10)
                    n //= 10
                return arr
            arr = digit(n)
            dgt = len(arr)
            ans = 0
            flag1 = 0
            for i in range(dgt - 1, -1, -1):
                ans += count1(arr[i], i)
                flag1 += 1 if arr[i] == 1 else 0
                if i > 0 and flag1:
                    ans += arr[i - 1] * flag1 * 10**(i - 1)
            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
    • 39
    • 40

    代码部分主要是将数字 n n n每一位的位数存成数组, 然后遍历(注意, 这里是逆序), 通过前面的讨论, 判断1所在的位置, 如果有, flag1++, 然后后面的数字都要乘上flag1, 即arr[i - 1] * flag1 * 10**(i - 1).

    执行结果还是不错的, 算是线性时间了:

    截屏2022-08-13 22.44.20

    小结

    因为是我自己通过特例一步一步推的, 就感觉还是比较好理解, 但是这样还是比较费时间, 仅供一乐了, 真正的好方法还得看官解.

  • 相关阅读:
    jvm调优-cpu飙升及响应慢
    软件定义存储不能打?这家成立刚三年的公司问鼎全球存储性能榜
    Java 时区
    Vivado下PLL实验
    异地远程访问内网BUG管理系统【Cpolar内网穿透】
    热熔胶行业调研:2022年热熔胶市场发展现状与前景分析
    【ArcGIS For JS】前端geojson渲染行政区划图层并加标签
    新鲜出炉的跨域问题:前端设置credential: ‘include‘,后端不能用‘*‘通配符匹配所有源
    TCP 报文首部的 6 个标记位
    PHP代码审计3—系统重装漏洞
  • 原文地址:https://blog.csdn.net/qq_41437512/article/details/126325498