剑指Offer题解 - Day70

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

力扣题目链接[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

分析：

首先考虑暴力法解题。浅显易懂的方式就是遍历1~n的整数，然后分别计算每个数字中1出现的次数。由于n最大可达2^31 指数级，因此直接循环是不可接受的。

此时就需要寻找规律。首先约定俗成以下规则：

• 将当前位的数字记为cur。
• 将低于当前位的数字记为low。
• 将高于当前位的数字记为high。
• 将当前所处的位记为digit，也就是个位，十位，百位等。

搞清楚几个概念后，我们需要处理两件事情。

1. 如何根据当前位的数字来计算此位出现1的可能性；
2. 如何从当前位递推到更高位，从而继续计算当前位出现1的可能性。

先来看第一个问题，根据当前位数字的不同，分为以下三种情况：

1. cur === 0 ：当前位数字为0，此位出现1的情况由高位决定，也就是 high * digit ，因为高位的数字每变动一次，当前位就会产生1。
2. cur === 1 ：当前位数字为1，此位出现1的情况由高位和低位同时决定，也就是high * digit + low + 1 ，高位不必多说，跟情况1是一样的。添加低位是因为低位不同数字的排列组合也是不同的数字，每个数字都会出现1。由于低位没有计入0，00，诸如此类，因此还需要再加1。
3. cur === 2,3,...,9 ：当前位数字为2~9，此位出现1的情况由高位决定，也就是(high + 1) * digit ，为什么要高位加1呢？因为多出来的一次来自于高位是high * digit，当前位是1的情况。

再来看第二个问题，如何从当前位递推到更高位。此时需要以下四个步骤：

1. low += cur * digit：将 cur 加入 low ，组成下轮 low
2. cur = high % 10：下轮 cur 是本轮 high 的最低位
3. high = Math.floor(high / 10) ：将本轮 high 最低位删除，得到下轮 high
4. digit *= 10 ：所在位每轮 × 10
5. 递推终止条件是：当 high 和 cur 同时为 0 时，说明已经越过最高位，此时终止递推。

基于此，可以写出如下的最终代码：

/**
 * @param {number} n
 * @return {number}
 */
var countDigitOne = function(n) {
    let digit = 1;
    let res = 0;
    let high = Math.floor(n / 10);
    let cur = n % 10;
    let low = 0;
    while(high !== 0 || cur !== 0) {
        if (cur === 0) res += high * digit;
        else if (cur === 1) res += high * digit + low + 1;
        else res += (high + 1) * digit;
        low += cur * digit;
        cur = high % 10;
        high = Math.floor(high / 10);
        digit *= 10;
    }
    return res;
};

• 时间复杂度 O(logn)。
• 空间复杂度 O(1)。

总结

本题考查数学规律。难度系数困难。核心难点在于如何基于当前位的数字来推断出现1的情况；以及如何递推到更高位。

复杂度方面，循环次数为数字 n 的位数，因此时间复杂度是O(logn) ；维护额外的常数级别的变量占用O(1)的空间。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/572jxs/