0000 - Number of digit one

Other

June 11, 2023

题干

破题

这道题的难度是 Hard ，但是题干明明看起来又非常简单，这实在让人倒吸一口凉气，这可能会有多种情况地、很复杂地展开。

但是，但是，不要慌，先看一下数据规模，数据规模本身足以揭露答案。发现是 $10^9$ ，这意味着线性的、一遍扫描的办法是不通的，需要一个比如对数级的亚线性的算法。这对于一个数字来说，第一时间可以想到的就是按照10进制的位来分解问题。

比如说，给定的数字 $\texttt{N}$ 被分解为 $\texttt{N}=\displaystyle{\sum_{i=0}^{n} a_i\cdot 10^i}$ ，对于前 $i+1$ 位的数字，显然一部分的 $1$ 可以由 $a_i \cdot f(10^i)$ 计算出，这是指前 $i$ 位上的 $1$ ，但还有一部分的 $1$ 是在第 $i+1$ 位上的，它们的计算是根据 $a_i$ 的大小，显然如果 $a_i \gt 1$ ，那么会有 $10^i$ 个 $1$，而如果 $a_i=1$ ，那么会有 $(\sum_{k=1}^{\displaystyle{\sum_{j=0}^{i} a_j\cdot 10^j}}k) +1$ 个 $1$ 。这样我们逐位计算就可以在对数级的时间复杂度下算出结果。

解①：

根据上面我们的想法，整理出如下代码：

from functools import cache

def solve(n: int) -> int:
    @cache
    def f(i: int) -> int:
        if i == 0:
            return 1
        else:
            return 10 * f(i - 1) + 10**i

    acc = n
    bits = [acc % 10]
    acc //= 10

    while acc > 0:
        bits.append(acc % 10)
        acc //= 10

    ans = int(bool(bits[0]))

    for j in range(1, len(bits)):
        if bits[j]:
            ans += bits[j] * f(j - 1) + (
                (10**j) if bits[j] > 1 else (n % 10**j + 1)
            )

    return ans

代码可以整合到一个循环里：

这里使用 base 作为控制逐位循环的变量的想法是从其他代码里参考而来，觉得非常好就使用了。

def solve(n: int) -> int:
    base = 10
    pack = 1
    div = n

    ans = int(bool(div % 10))

    while base < n: # a*pack + head/b
        a = div % 100 // 10

        if a:
            if a > 1:
                head = base
            else:
                head = n % base + 1

            ans += a*pack + head

        pack = 10 * pack + base
        div //= 10
        base *= 10

    return ans

0000 - Number of digit one

题干

破题

解①：

注解