233. 数字 1 的个数 #

问题描述#

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

示例 1：
输入：n = 13
输出：6
示例 2：
输入：n = 0
输出：0
提示：

0 <= n <= 2 * 10⁹

解题思路#

如果我们知道 \(n\) 的十进制表示某一位为 \(1\) 的不超过 \(n\) 的数字有多少个，那么我们把每一位为 \(1\) 的数字个数加起来，就是所以不超过 \(n\) 的数字中 \(1\) 的个数了。

假设 \(n\) 的十进制表示从高位到低位每一位上的数字为 \(n=a_{n-1}a_{n-2}\cdots a_0\)，

假设现在我们考虑 \(a_i\) 位置为 \(1\) 的可能数字个数。

我们将 \(n\) 分为 \(a,b,c\) 三部分，\(a\) 表示数字 \(a_{n-1}\cdots a_{i+1}\)，\(b\) 表示数字 \(a_i\)，\(c\) 表示数字 \(a_{i-1}\cdots a_0\)。

如果 \(b\gt1\)，此时 \(a_{n-1}\cdots a_{i+1}\) 可以取到 \([0,a]\) 中的每一个数，\(a_{i-1}\cdots a_0\) 的每一位都可以取 \([0,9]\) 每个数字。所以此时的可能数字个数有 \((1+a)\times10^i\) 个。

如果 \(b=1\)，此时 \(a_{n-1}\cdots a_{i+1}\) 可以取到 \([0,a)\) 中的每一个数时，\(a_{i-1}\cdots a_0\) 的每一位都可以取 \([0,9]\) 每个数字；\(a_{n-1}\cdots a_{i+1}\) 取 \(a\) 时，\(a_{i-1}\cdots a_0\) 可以取 \([0,c]\) 的每一个数。所以此时的可能数字个数有 \(a\times10^i+c+1\) 个。

如果 \(b=0\)，此时 \(a_{n-1}\cdots a_{i+1}\) 可以取到 \([0,a)\) 中的每一个数时，\(a_{i-1}\cdots a_0\) 的每一位都可以取 \([0,9]\) 每个数字。所以此时的可能数字个数有 \(a\times10^i\) 个。

Example

假设 \(n=a_4a_3a_2a_1a_0=10312\)，

考虑 \(a_0\) 位为 \(1\) 时，此时 \(a=1031,b=2,c=0\)，因为 \(b=2\gt1\)，所以此时的可能数字个数有 \((1+a)\times10^0=1032\) 个。

考虑 \(a_1\) 位为 \(1\) 时，此时 \(a=103,b=1,c=2\)，因为 \(b=1\)，所以此时的可能数字个数有 \(a\times10^1+c+1=1030+3=1033\) 个。

考虑 \(a_2\) 位为 \(1\) 时，此时 \(a=10,b=3,c=12\)，因为 \(b=3\gt1\)，所以此时的可能数字个数有 \((1+a)\times10^2=1100\) 个。

考虑 \(a_3\) 位为 \(1\) 时，此时 \(a=1,b=0,c=312\)，因为 \(b=0\)，所以此时的可能数字个数有 \(a\times10^3=1000\) 个。

考虑 \(a_4\) 位为 \(1\) 时，此时 \(a=0,b=1,c=312\)，因为 \(b=1\)，所以此时的可能数字个数有 \(a\times10^4+c+1=313\) 个。

所以最终的结果为 \(1032+1033+1100+1000+313=4478\) 个。

Python

class Solution:
    def countDigitOne(self, n: int) -> int:
        ans, k = 0, 1

        while n // k:
            a, b, c = n // (10 * k), (n // k) % 10, n % k

            if b > 1: t = (a + 1) * k
            if b == 1: t = a * k + c + 1
            if b == 0: t = a * k

            ans += t
            k *= 10

        return ans

C++

class Solution {
public:
    int countDigitOne(int n) {
        int ans = 0;

        int a, b, c, t;
        long long k = 1;

        while (n / k) {
            a = n / (10 * k), b = (n / k) % 10, c = n % k;
            if (b > 1) t = (a + 1) * k;
            if (b == 1) t = a * k + c + 1;
            if (b == 0) t = a * k;

            // cout << t << ' ';
            ans += t;
            k *= 10;
        }
        return ans;
    }
};

233. 数字 1 的个数#

问题描述#

解题思路#

233. 数字 1 的个数 #