0233. Number of Digit One¶
题目信息¶
- 题号:
0233
- 难度:
Hard
- 主题:
数学、数位统计、十进制
- 原题:
- 重点:
闭区间 0 到 n、统计数字出现次数而非含 1 的整数个数、前导零不计
题目重述¶
给定非负整数 n,统计从 0 到 n 的所有十进制整数表示中,数字字符 1 一共出现了多少次,并返回总次数。统计范围包含两个端点。
n 位于 [0, 10^9]。同一个整数中出现多个 1 时需要分别计数,例如 11 贡献两次;前导零不属于整数的通常十进制表示,不能参与统计。数字 0 自身不包含 1。
自建示例¶
一个数可以贡献多次:
输入:n = 15
输出:8
解释:1、10、12、13、14、15 各贡献一次,11 贡献两次,总计 8 次。
零边界:
输入:n = 0
输出:0
解释:区间中只有整数 0,它的十进制表示不含数字 1。
按十进制位统计¶
固定一个位权 factor``(``1,10,100,...),把 n 拆成:
high = n / (factor * 10)
cur = (n / factor) % 10
low = n % factor
统计 0..n 中该位出现数字 1 的次数。完整的高位循环贡献 high * factor;
当前位分别有三种情况:
cur == 0:当前高位组合还没有完整走过 1,贡献high * factor;cur == 1:完整循环之外还覆盖低位0..low,贡献high * factor + low + 1;cur > 1:当前高位组合已经完整经过一次 1,贡献(high + 1) * factor。
前导零不会被误计入:当某个更高位还没有出现时,high 的完整循环数量自然为 0;
n=0 时所有位权都超过 n,答案为 0。
以 n=15 为例,个位 cur=5 贡献 2(数字 1、11 的个位),十位 cur=1、low=5 贡献 6,
总数为 8。每个位独立统计,再把贡献相加即可。
正确性说明¶
在固定位权上,连续的 factor*10 个整数会完整经历一次该位从 0 到 9 的循环,数字 1 出现恰好
factor 次;high 计数这些完整循环。余下部分由 cur 决定:当前位小于 1 时尚未进入额外一轮,
等于 1 时只覆盖低位到 low,大于 1 时整轮已经完成。三种情况互斥且覆盖 0..n,所以所有位次数字 1
都被计数一次。
C++ 实现¶
class Solution {
public:
int countDigitOne(int n) {
long long answer = 0;
for (long long factor = 1; factor <= n; factor *= 10) {
const long long high = n / (factor * 10);
const long long current = (n / factor) % 10;
const long long low = n % factor;
if (current == 0) {
answer += high * factor;
} else if (current == 1) {
answer += high * factor + low + 1;
} else {
answer += (high + 1) * factor;
}
}
return static_cast<int>(answer);
}
};
代码分析¶
位权每次乘 10,循环次数为十进制位数,时间复杂度为 O(log n),额外空间为 O(1)。
中间计算使用 long long,避免 factor*10 或贡献项在窄整数类型中提前溢出;n=0 时循环自然跳过。