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

Categories:

题目描述
思路分析
1. 解法一：按位统计（推荐）
相似题目

题目描述

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

思路分析

解法一：按位统计（推荐）

核心思路：

逐位统计每一位上数字 1 出现的次数。

对于当前位 factor，设 high = n / (factor * 10)，cur = (n / factor) % 10，low = n % factor。

分三种情况累加：cur == 0、cur == 1、cur >= 2。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示给定数字。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int countDigitOne(int n) {
        long factor = 1;
        long res = 0;

        while (n / factor != 0) {
            long high = n / (factor * 10);
            long cur = (n / factor) % 10;
            long low = n % factor;

            // 按当前位数值分类统计
            if (cur == 0) {
                res += high * factor;
            } else if (cur == 1) {
                res += high * factor + low + 1;
            } else {
                res += (high + 1) * factor;
            }

            factor *= 10;
        }

        return (int) res;
    }
}

func countDigitOne(n int) int {
	factor := int64(1)
	res := int64(0)

	for n/int(factor) != 0 {
		high := int64(n) / (factor * 10)
		cur := (int64(n) / factor) % 10
		low := int64(n) % factor

		// 按当前位数值分类统计
		if cur == 0 {
			res += high * factor
		} else if cur == 1 {
			res += high*factor + low + 1
		} else {
			res += (high + 1) * factor
		}

		factor *= 10
	}

	return int(res)
}

相似题目

题目	难度	考察点
233. 数字 1 的个数	困难	按位统计
400. 第 N 位数字	中等	数位分析
1012. 至少有 1 位重复的数字	困难	数位 DP
357. 统计各位数字都不同的数字个数	中等	数位 DP
1291. 顺次数	中等	枚举

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/57384677