数字 1 的个数

Submission

运行时间: 28 ms

内存: 14.8 MB

class Solution:
    def countDigitOne(self, n: int) -> int:
        res = 0
        digit = 1
        high, cur, low = n // 10, n % 10, 0
        while high != 0 or cur != 0:
            if cur == 0:
                res += high * digit
            elif cur == 1:
                res += high * digit + low + 1
            else:
                res += high * digit + digit
            low += cur * digit
            cur = high % 10
            high //= 10
            digit *= 10
        return res

Explain

该题解使用了数位分析的方法来解决问题。算法通过逐个分析数字n的每一位来计算1的出现次数。首先，将整数n分解为三个部分：高位（high），当前位（cur），和低位（low）。'digit'代表当前分析位的数位值（1, 10, 100, ...）。算法从个位开始，逐步向高位移动，每次迭代更新三个部分的值：1. 如果当前位是0，则1的出现次数由更高位决定。2. 如果当前位是1，则1的出现次数由更高位和更低位共同决定。3. 如果当前位大于1，则1的出现次数也由更高位决定，但要加上当前数位值。这种逐位分析的方法避免了直接计数的大量重复操作，提高了效率。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def countDigitOne(self, n: int) -> int:
        res = 0  # 初始化结果为0
        digit = 1  # 当前分析的数位（1, 10, 100, ...）
        high, cur, low = n // 10, n % 10, 0  # 初始化高位，当前位和低位
        while high != 0 or cur != 0:  # 当还有高位或当前位时继续循环
            if cur == 0:
                res += high * digit  # 当前位是0，计算高位贡献
            elif cur == 1:
                res += high * digit + low + 1  # 当前位是1，计算高位和低位的贡献
            else:
                res += high * digit + digit  # 当前位大于1，计算高位贡献并加上当前数位值
            low += cur * digit  # 更新低位
            cur = high % 10  # 更新当前位
            high //= 10  # 更新高位
            digit *= 10  # 更新数位值
        return res  # 返回结果

Explore

整数n的分解为高位（high），当前位（cur），和低位（low）是基于数位的分析来逐位计算1的出现次数的需要。'high'是当前位左边的所有数字，代表了当前分析位以上的数位；'cur'是正在分析的那一位数字；'low'是当前位右边的所有数字，代表了当前分析位以下的数位。这种分解让我们能够考虑到每一位数字变化时1出现的次数是如何受到其它位数的影响的。例如，当我们分析某一特定位时，这位数字左边的数字（高位）决定了这位可以取的可能的最大次数，而右边的数字（低位）提供了额外的计数，尤其是当中间的数位为1时。

当当前位cur大于1时，表示在当前的数位上，数字1会出现在从0到9的所有可能值中，并且每种情况都会重复一整个digit周期（例如在十位上，从10到19, 110到119等）。因此，除了高位决定的次数外（即高位数字乘以当前数位值），我们还必须加上整个当前数位的范围（即digit），这代表从1到当前数位值的最大值范围内，1将额外出现。这个加法操作是因为在当前位的数字大于1的情况下，1在当前数位上会从0循环到9再重复，从而确保每个完整的数位周期内都有一个额外的1出现。

在算法中更新低位low的表达式`low += cur * digit`是用来累积当前位之前所有低位上的数字，形成一个完整的低位值。这样做的目的是当我们移动到更高的位时，可以保留已经分析过的低位数字，因为这些数字会影响到更高位上1的出现次数的计算。例如，当从个位向十位移动时，原来的个位数字（现在的cur）乘以其数位值（digit表示当前数位的十进制值）会被加到low中，以便在计算更高位时可以使用完整的低位信息。这是一个关键的步骤，因为它保证了在分析每一位时都能够准确地利用之前位的具体数值信息。