LeetCode 解題筆記：3871. Count Commas in Range II

作者：王一哲
日期：2026年9月9日


LeetCode 題目連結：3871. Count Commas in Range II

解題想法

中等難度題，3870. Count Commas in Range 的加強版。題目給一個正整數 $n$ $(1 \leq n \leq 10^{15})$，計算 $1$ 到 $n$ 共有幾個分隔數字的逗號，小於 $1000$ 的數字不需要加逗號，大於等於 $1000$ 的數字，每隔 $3$ 位數加 $1$ 個逗號。由於 $n$ 最大到 $10^{15}$，可以分成 $5$ 組計算答案：

1. $10^3 \leq x < 10^6$，每個數字加 $1$ 個逗號，答案加上範圍內的數字個數。
2. $10^6 \leq x < 10^9$，每個數字加 $2$ 個逗號，答案加上範圍內的數字個數乘以 $2$。
3. $10^9 \leq x < 10^{12}$，每個數字加 $3$ 個逗號，答案加上範圍內的數字個數乘以 $3$。
4. $10^{12} \leq x < 10^{15}$，每個數字加 $4$ 個逗號，答案加上範圍內的數字個數乘以 $4$。
5. 如果 $n = 10^{15}$，答案再加上 $5$ 個逗號。

這題如果用 C++ 解題，在使用 min 取最小值時，手動輸入的常數要在最後面加上 LL，標記為 long long 格式，否則 min 之中兩個整數格式不同，無法比較。如果用 C 語言解題，因為 C 語言沒有內建的 min 能用，要在最前面用 define 自己定義 min。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.31 MB, beats 13.61%.

class Solution:
    def countCommas(self, n: int) -> int:
        ans = 0
        if n >= 10**3:  # 10**3 ~ 10**6 - 1
            ans += min(n - 10**3 + 1, 10**6 - 10**3)
        if n >= 10**6:  # 10**6 ~ 10**9 - 1
            ans += min(n - 10**6 + 1, 10**9 - 10**6) * 2
        if n >= 10**9:  # 10**9 ~ 10**12 - 1
            ans += min(n - 10**9 + 1, 10**12 - 10**9) * 3
        if n >= 10**12:  # 10**12 ~ 10**15 - 1
            ans += min(n - 10**12 + 1, 10**15 - 10**12) * 4
        if n >= 10**15:  # 10**15 ~ 10**18 - 1
            ans += min(n - 10**15 + 1, 10**18 - 10**15) * 5
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.97 MB, beats 84.80%.

class Solution {
public:
    long long countCommas(long long n) {
        long long ans = 0;
        if (n >= 1000LL) {  // 10**3 ~ 10**6 - 1
            ans += min(n - 1000 + 1, 1000000LL - 1000LL);
        }
        if (n >= 1000000LL) {  // 10**6 ~ 10**9 - 1
            ans += min(n - 1000000 + 1, 1000000000LL - 1000000LL) * 2;
        }
        if (n >= 1000000000LL) {  // 10**9 ~ 10**12 - 1
            ans += min(n - 1000000000 + 1, 1000000000000LL - 1000000000LL) * 3;
        }
        if (n >= 1000000000000LL) {  // 10**12 ~ 10**15 - 1
            ans += min(n - 1000000000000LL + 1, 1000000000000000LL - 1000000000000LL) * 4;
        }
        if (n == 1000000000000000LL) {  // 測資最大到 10**15
            ans += 5;
        }
        return ans;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.51 MB, beats 21.05%.

#define min(a, b) ((a) < (b) ? (a) : (b))

long long countCommas(long long n) {
    long long ans = 0;
    if (n >= 1000LL) {  // 10**3 ~ 10**6 - 1
        ans += min(n - 1000 + 1, 1000000LL - 1000LL);
    }
    if (n >= 1000000LL) {  // 10**6 ~ 10**9 - 1
        ans += min(n - 1000000 + 1, 1000000000LL - 1000000LL) * 2;
    }
    if (n >= 1000000000LL) {  // 10**9 ~ 10**12 - 1
        ans += min(n - 1000000000 + 1, 1000000000000LL - 1000000000LL) * 3;
    }
    if (n >= 1000000000000LL) {  // 10**12 ~ 10**15 - 1
        ans += min(n - 1000000000000LL + 1, 1000000000000000LL - 1000000000000LL) * 4;
    }
    if (n == 1000000000000000LL) {  // 測資最大到 10**15
        ans += 5;
    }
    return ans;
}