Medium

题目描述

给定一个整数 n。

返回在标准数字格式下，写出从 [1, n]（包含）范围内所有整数时使用的逗号总数。

在标准格式中：

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

示例 1：

输入：n = 1002
输出：3
解释：数字 "1,000"、"1,001" 和 "1,002" 每个都包含一个逗号，总共 3 个。

示例 2：

输入：n = 998
输出：0
解释：从 1 到 998 的所有数字都少于四位数，因此不使用逗号。

约束条件：

  • 1 <= n <= 10^15

解题思路

这道题需要计算从 1 到 n 的所有数字在标准格式下使用的逗号总数。

核心思路：

我们可以按照数字的位数进行分组：

  • 1-3 位数：0 个逗号
  • 4-6 位数：1 个逗号
  • 7-9 位数：2 个逗号
  • 10-12 位数：3 个逗号
  • …

对于 k 位数的数字，逗号数量为 (k-1) // 3。

算法步骤：

  1. 确定 n 的位数，从而知道需要处理哪些位数组
  2. 对于每个完整的位数组（如 4-6 位），计算该组内所有数字的逗号总数
  3. 对于包含 n 的最后一个位数组，只计算到 n 为止的数字

具体实现：

  • 对于 d 位数（d >= 4），该位数的数字范围是 [10^(d-1), 10^d - 1]
  • 每个 d 位数包含 (d-1) // 3 个逗号
  • 如果 n 在这个范围内，则只计算到 n 的部分

时间复杂度为 O(log n)，因为只需要处理 n 的位数个组别。

代码实现

class Solution {
public:
    long long countCommas(long long n) {
        long long result = 0;
        long long power = 1000; // 10^3, 第一个需要逗号的数字组
        
        while (power <= n) {
            // 计算当前位数组的逗号数量
            long long commas = (to_string(power).length() - 1) / 3;
            
            // 当前组的最大值
            long long nextPower = power * 1000;
            long long maxInGroup = min(n, nextPower - 1);
            
            // 当前组中数字的数量
            long long count = maxInGroup - power + 1;
            
            result += count * commas;
            power = nextPower;
        }
        
        return result;
    }
};

class Solution:
    def countCommas(self, n: int) -> int:
        result = 0
        power = 1000  # 10^3, 第一个需要逗号的数字组
        
        while power <= n:
            # 计算当前位数组的逗号数量
            commas = (len(str(power)) - 1) // 3
            
            # 当前组的最大值
            next_power = power * 1000
            max_in_group = min(n, next_power - 1)
            
            # 当前组中数字的数量
            count = max_in_group - power + 1
            
            result += count * commas
            power = next_power
        
        return result

public class Solution {
    public long CountCommas(long n) {
        long result = 0;
        long power = 1000; // 10^3, 第一个需要逗号的数字组
        
        while (power <= n) {
            // 计算当前位数组的逗号数量
            long commas = (power.ToString().Length - 1) / 3;
            
            // 当前组的最大值
            long nextPower = power * 1000;
            long maxInGroup = Math.Min(n, nextPower - 1);
            
            // 当前组中数字的数量
            long count = maxInGroup - power + 1;
            
            result += count * commas;
            power = nextPower;
        }
        
        return result;
    }
}

var countCommas = function(n) {
    let result = 0;
    let power = 1000; // 10^3, 第一个需要逗号的数字组
    
    while (power <= n) {
        // 计算当前位数组的逗号数量
        let commas = Math.floor((power.toString().length - 1) / 3);
        
        // 当前组的最大值
        let nextPower = power * 1000;
        let maxInGroup = Math.min(n, nextPower - 1);
        
        // 当前组中数字的数量
        let count = maxInGroup - power + 1;
        
        result += count * commas;
        power = nextPower;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(log n)
空间复杂度O(1)

时间复杂度：需要处理的位数组数量与 n 的位数成正比，即 O(log n) 空间复杂度：只使用常数级别的额外空间