3870.统计范围内的逗号：模拟 或 一步计算

【LetMeFly】3870.统计范围内的逗号：模拟 或 一步计算

力扣题目链接：https://leetcode.cn/problems/count-commas-in-range/

给你一个整数 n。

返回将所有从 [1, n]（包含两端）范围内的整数以 标准 数字格式书写时所用到的 逗号总数。

在 标准 格式中：

• 从右边开始，每 三位 数字后插入一个逗号。
• 位数 少于四位 的数字不包含逗号。

 

示例 1：

输入： n = 1002

输出： 3

解释：

数字 "1,000"、"1,001" 和 "1,002" 每个都包含一个逗号，总计 3 个逗号。

示例 2：

输入： n = 998

输出： 0

解释：

从 1 到 998 的所有数字位数都少于四位，因此没有使用逗号。

 

提示：

• 1 <= n <= 105

解题方法一：模拟

从$1000$到$n$模拟，计算每个数字十进制下的位数（当数字非零时候不断除以$10$并向下取整），则逗号数量为$\frac{位数-1}{3}$。

• 时间复杂度$O(n\log n)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-09-08 12:36:37
 */
class Solution {
private:
    int cal(int n) {
        int len = 0;
        while (n) {
            len++;
            n /= 10;
        }
        return (len - 1) / 3;
    }
public:
    int countCommas(int n) {
        int ans = 0;
        for (int i = 1000; i <= n; i++) {
            ans += cal(i);
        }
        return ans;
    }
};

解题方法二：一步计算

不难发现题目的数据范围是$1\leq n\leq 10^5$，而$1\leq n\leq 999$的数字没有逗号，$1000\leq n\leq 10^5$的数字每个数字有一个逗号，所以直接返回$999$到$n$的数字个数即可。

• 时间复杂度$O(1)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-09-08 12:38:43
 */
class Solution {
public:
    int countCommas(int n) {
        return max(0, n - 999);
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源