剑指 Offer 43. 1～n 整数中 1 出现的次数 #

问题描述#

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：
输入：n = 12
输出：5
示例 2：
输入：n = 13
输出：6
限制：

1 <= n < 2^31

注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/

解题思路#

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

如果我们知道 \(a_i=1\) （即十进制表示的第 \(i\) 位）的数字（不超过 \(n\)）有多少个 \(C(a_i=1)\)，那么我们把每一位为 \(1\) 的数字个数加起来 \(\sum_{i=0}^{n-1}C(a_i=1)\)，就是所有不超过 \(n\) 的数字中 \(1\) 的个数了。

假设现在我们考虑 \(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;
    }
};

剑指 Offer 43. 1～n 整数中 1 出现的次数#

问题描述#

解题思路#

剑指 Offer 43. 1～n 整数中 1 出现的次数 #