233. 数字 1 的个数
233. 数字 1 的个数
题目
Given an integer n
, count the total number of digit1
appearing in all non-negative integers less than or equal to n
.
Example 1:
Input: n = 13
Output: 6
Example 2:
Input: n = 0
Output: 0
Constraints:
0 <= n <= 10^9
题目大意
给定一个整数 n
,计算所有小于等于 n
的非负整数中数字 1
出现的个数。
示例 1:
输入: n = 13
输出: 6
示例 2:
输入: n = 0
输出: 0
提示:
0 <= n <= 10^9
解题思路
每个位置上 1
的个数可以通过以下几个规律来计算:
分位计算:对于一个数字的每一位(个位、十位、百位等),我们可以把这个数字分为三部分:
- 当前位的数字。
- 当前位左边的所有数字(高位)。
- 当前位右边的所有数字(低位)。
当前位的贡献:
- 如果当前位是
0
,那么1
的个数只来自于高位的部分。 - 如果当前位是
1
,那么除了高位的部分外,还要加上低位的数字 + 1
(因为当前位的1
本身也算)。 - 如果当前位大于
1
,那么可以认为高位的所有组合都会有1
出现在当前位。
- 如果当前位是
高位和低位的影响:
- 高位的组合数量直接影响到当前位的
1
的总数。 - 低位的数字数量决定了当前位为
1
时的具体计数。
- 高位的组合数量直接影响到当前位的
举个例子:考虑数字 2345
的千位、百位、十位和个位上 1
的个数:
- 千位(2):
1
出现的次数是1000
,1000~1999
,共计1000
个数。 - 百位(3):
1
出现的次数是300
,2100~2199
、1100~1199
、100~199
,共计300
个数。 - 十位(4):
1
出现的次数是240
,2x10~2x19(x=0~3)
、1x10~1x19(x=0~9)
、x10~x19(x=1~9)
、10~19
,共计240
个数。 - 个位(5):
1
出现的次数是235
,1
、11
、21
……2341
,共计235
个数。
复杂度分析
- 时间复杂度:
O(log n)
,因为每次循环处理一位数字。 - 空间复杂度:
O(1)
,只使用了常数空间。
代码
/**
* @param {number} n
* @return {number}
*/
var countDigitOne = function (n) {
let res = 0,
factor = 1, // 用于处理每一位
curDigit = 0, // 当前位置的数字
remainder = 0; // 当前位置右边的所有数字
while (n >= factor) {
curDigit = Math.floor((n / factor) % 10);
remainder = n - Math.floor(n / factor) * factor;
// 计算当前位对1的贡献
if (curDigit == 0) {
res += Math.floor(n / (factor * 10)) * factor;
} else if (curDigit == 1) {
res += Math.floor(n / (factor * 10)) * factor + remainder + 1;
} else {
res += (Math.floor(n / (factor * 10)) + 1) * factor;
}
// 处理下一位
factor *= 10;
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
172 | 阶乘后的零 | [✓] | 数学 | |
1067 | 范围内的数字计数 🔒 | 数学 动态规划 |