剑指 Offer 43. 1～n 整数中 1 出现的次数
力扣题目链接[1]
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
「示例 1：」
代码语言：javascript复制输入：n = 12
输出：5
「示例 2：」
代码语言：javascript复制输入：n = 13
输出：6
「限制：」
1 <= n < 2^31
分析：
首先考虑暴力法解题。浅显易懂的方式就是遍历1~n的整数，然后分别计算每个数字中1出现的次数。由于n最大可达2^31 指数级，因此直接循环是不可接受的。
此时就需要寻找规律。首先约定俗成以下规则：
- 将当前位的数字记为
cur。 - 将低于当前位的数字记为
low。 - 将高于当前位的数字记为
high。 - 将当前所处的位记为
digit，也就是个位，十位，百位等。
搞清楚几个概念后，我们需要处理两件事情。
- 如何根据当前位的数字来计算此位出现1的可能性；
- 如何从当前位递推到更高位，从而继续计算当前位出现1的可能性。
先来看第一个问题，根据当前位数字的不同，分为以下三种情况：
cur === 0：当前位数字为0，此位出现1的情况由高位决定，也就是high * digit，因为高位的数字每变动一次，当前位就会产生1。cur === 1：当前位数字为1，此位出现1的情况由高位和低位同时决定，也就是high * digit low 1，高位不必多说，跟情况1是一样的。添加低位是因为低位不同数字的排列组合也是不同的数字，每个数字都会出现1。由于低位没有计入0，00，诸如此类，因此还需要再加1。cur === 2,3,...,9：当前位数字为2~9，此位出现1的情况由高位决定，也就是(high 1) * digit，为什么要高位加1呢？因为多出来的一次来自于高位是high * digit，当前位是1的情况。
再来看第二个问题，如何从当前位递推到更高位。此时需要以下四个步骤：
low = cur * digit：将 cur 加入 low ，组成下轮 lowcur = high % 10：下轮 cur 是本轮 high 的最低位high = Math.floor(high / 10)：将本轮 high 最低位删除，得到下轮 highdigit *= 10：所在位每轮 × 10- 递推终止条件是：当 high 和 cur 同时为 0 时，说明已经越过最高位，此时终止递推。
基于此，可以写出如下的最终代码：
代码语言：javascript复制/**
* @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/
