Hard

题目描述

给定一个整数 n，计算所有小于或等于 n 的非负整数中数字 1 出现的个数。

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

约束条件：

  • 0 <= n <= 10^9

提示：

  • 注意溢出问题。

解题思路

这道题要求计算从 0 到 n 中所有数字中 1 出现的总次数。主要有三种解法：

方法一：暴力枚举 遍历每个数字，统计其中 1 的个数。时间复杂度 O(n log n)，对于大数据会超时。

方法二：数学规律法（推荐） 观察数字 1 在各个位置上出现的规律。对于第 i 位（从右往左，从 0 开始），分析当前位、高位、低位的影响：

  • 当前位为 0：该位上 1 的个数 = higher × 10^i
  • 当前位为 1：该位上 1 的个数 = higher × 10^i + lower + 1
  • 当前位 > 1：该位上 1 的个数 = (higher + 1) × 10^i

方法三：动态规划 + 数位DP 使用记忆化搜索，按位构造数字，统计包含 1 的情况数。适合处理复杂的数位问题。

数学规律法最优，时间复杂度 O(log n)，空间复杂度 O(1)，思路清晰且效率高。

代码实现

class Solution {
public:
    int countDigitOne(int n) {
        long long count = 0;
        long long factor = 1;
        
        while (factor <= n) {
            long long higher = n / (factor * 10);
            long long cur = (n / factor) % 10;
            long long lower = n % factor;
            
            if (cur == 0) {
                count += higher * factor;
            } else if (cur == 1) {
                count += higher * factor + lower + 1;
            } else {
                count += (higher + 1) * factor;
            }
            
            factor *= 10;
        }
        
        return count;
    }
};

class Solution:
    def countDigitOne(self, n: int) -> int:
        count = 0
        factor = 1
        
        while factor <= n:
            higher = n // (factor * 10)
            cur = (n // factor) % 10
            lower = n % factor
            
            if cur == 0:
                count += higher * factor
            elif cur == 1:
                count += higher * factor + lower + 1
            else:
                count += (higher + 1) * factor
            
            factor *= 10
        
        return count

public class Solution {
    public int CountDigitOne(int n) {
        long count = 0;
        long factor = 1;
        
        while (factor <= n) {
            long higher = n / (factor * 10);
            long cur = (n / factor) % 10;
            long lower = n % factor;
            
            if (cur == 0) {
                count += higher * factor;
            } else if (cur == 1) {
                count += higher * factor + lower + 1;
            } else {
                count += (higher + 1) * factor;
            }
            
            factor *= 10;
        }
        
        return (int)count;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var countDigitOne = function(n) {
    let count = 0;
    let digit = 1;
    
    while (digit <= n) {
        let higher = Math.floor(n / (digit * 10));
        let cur = Math.floor(n / digit) % 10;
        let lower = n % digit;
        
        if (cur === 0) {
            count += higher * digit;
        } else if (cur === 1) {
            count += higher * digit + lower + 1;
        } else {
            count += (higher + 1) * digit;
        }
        
        digit *= 10;
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数学规律法暴力枚举法数位DP
时间复杂度O(log n)O(n log n)O(log² n)
空间复杂度O(1)O(1)O(log n)

相关题目