LeetCode 233. 数字 1 的个数
题目分析
给定整数 n，计算所有小于等于 n 的非负整数中，数字 1 出现的总次数。
示例：
输入: n = 13
输出: 6
解释: 1, 10, 11, 12, 13 中包含 1，共出现 6 次
1(1个) + 10(1个) + 11(2个) + 12(1个) + 13(1个) = 6
输入: n = 20
输出: 12
解释: 1, 10-19 中包含 1，共 12 次
解决方案
方法一：数位统计（数学方法，推荐）⭐
核心思想： 按位统计，计算每一位上 1 出现的次数，然后累加。
class Solution {
public int countDigitOne(int n) {
if (n 1，所以十位上 1 出现的次数 = (high + 1) * digit = (21 + 1) * 10 = 220
解释：
0010-0019, 0110-0119, 0210-0219, …, 2010-2019, 2110-2119
共 22 组，每组 10 个，共 220 次
三种情况详解
当前位 cur 公式 示例 (n=2134)
cur = 0 high * digit 统计百位：21×100 = 2100次
cur = 1 high * digit + low + 1 统计千位：0×1000 + 134 + 1 = 135次
cur > 1 (high + 1) * digit 统计十位：(21+1)×10 = 220次
完整测试代码
public class Test {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.countDigitOne(0)); // 0
System.out.println(solution.countDigitOne(1)); // 1
System.out.println(solution.countDigitOne(10)); // 2
System.out.println(solution.countDigitOne(13)); // 6
System.out.println(solution.countDigitOne(20)); // 12
System.out.println(solution.countDigitOne(99)); // 20
System.out.println(solution.countDigitOne(100)); // 21
System.out.println(solution.countDigitOne(110)); // 32
System.out.println(solution.countDigitOne(2134)); // 1665
System.out.println(solution.countDigitOne(10000)); // 4001
System.out.println(solution.countDigitOne(2147483647)); // 2977074380
}
}
执行流程示例
以 n = 13 为例：
digit = 1 (个位):
high = 13 / 10 = 1
cur = (13 / 1) % 10 = 3
low = 13 % 1 = 0
cur > 1 → count += (1 + 1) * 1 = 2
(个位上1出现：1, 11 共2次)
digit = 10 (十位):
high = 13 / 100 = 0
cur = (13 / 10) % 10 = 1
low = 13 % 10 = 3
cur == 1 → count += 0 * 10 + 3 + 1 = 4
(十位上1出现：10, 11, 12, 13 共4次)
digit = 100 > 13，结束
总计数 = 2 + 4 = 6 ✓
复杂度分析
方法 时间复杂度 空间复杂度
方法一（数位统计） O(log n) O(1)
方法二（递归） O(log n) O(log n)
方法三（优化公式） O(log n) O(1)
暴力枚举 O(n × log n) O(1)
log n = 数字的位数（最多 10 位 for int）
关键点说明
为什么用 long 类型？
long digit = 1; // 避免 digit * 10 溢出
当 n 接近 Integer.MAX_VALUE 时，digit 可能溢出。
公式推导
对于第 i 位（权重为 digit）：
完整周期数 = high
每个周期中 1 出现 digit 次
不完整周期根据 cur 决定
边界情况
if (n 0) {
if (num % 10 == 1) count++;
num /= 10;
}
}
return count;
}
}
常见错误
错误 原因 修复
整数溢出 digit 超过 int 范围 使用 long digit
cur=1 时公式错误 忘记加 low+1 high * digit + low + 1
边界处理 n=0 时返回错误 添加 if (n <= 0) return 0
循环条件 digit 溢出导致死循环 digit <= n 且用 long
推荐
使用方法一（数位统计），代码清晰，效率高，容易理解和面试讲解。
扩展思考
如果要统计其他数字（2-9）出现的次数，只需修改判断条件：
// 统计数字 k (1-9) 出现的次数
public int countDigitK(int n, int k) {
int count = 0;
long digit = 1;
while (digit <= n) {
long high = n / (digit * 10);
long cur = (n / digit) % 10;
long low = n % digit;
if (cur < k) {
count += high * digit;
} else if (cur == k) {
count += high * digit + low + 1;
} else {
count += (high + 1) * digit;
}
digit *= 10;
}
return count;
}
