[Leetcode 1067] Digit Count in Range

原题说明

Given an integer d between 0 and 9, and two positive integers low and high as lower and upper bounds, respectively. Return the number of times that d occurs as a digit in all integers between low and high, including the bounds low and high.

Example 1:

Input: d = 1, low = 1, high = 13
Output: 6
Explanation: 
The digit d=1 occurs 6 times in 1,10,11,12,13. Note that the digit d=1 occurs twice in the number 11.

Example 2:

Input: d = 3, low = 100, high = 250
Output: 35
Explanation: 
The digit d=3 occurs 35 times in 103,113,123,130,131,…,238,239,243.

Note:

0 <= d <= 9
1 <= low <= high <= 2×10^8

解题思路

这道题我们用递归的方式，递归函数为recursiveCount(N, d), 将N当中出现d的次数分为个位数中出现的次数，加上非个位数出现的次数。
个位数出现的次数为N/10, 非个位数中出现的次数为recursiveCount(N / 10, d) * 10, 可以理解为N / 10中每一个数都可以加后缀0 - 9成为N中的一个数字。
当然还要考虑最后一位的大小，从而加减一个偏差，详见代码注释。

示例代码 (cpp)

class Solution {
    int recursiveCount(int N, int d) {
        // 退出条件
        if (N <= 9) {
            return d == 0 ? 0 : (d <= N);
        }
        int ret = 0;
        // 个位数字d出现的次数，不包含最后一次，e.g. N=797，这里只计算1 - 789之间个位数字出现d的次数
        ret += (d == 0 ? (N / 10 - 1) : N / 10);
        // 判断最后一次个位数字是否包含d，e.g. N=797，判断790-797之间个位数字是否出现d
        if (N % 10 >= d) {
            ++ret;
        }
        // 除了个位数字以外其他位数d出现的个数, e.g. N=797，我们计算了1 - 799之间非个位数字出现d的次数
        ret += recursiveCount(N / 10, d) * 10;
        // 前面默认最后一位到9，因此我们要减去最后一位不到9的情况，e.g. N=797, 我们计算798 - 799两数非个位数字出现d的次数
        string nstr = to_string(N / 10);
        ret -= std::count(nstr.begin(), nstr.end(), d + '0') * (9 - N % 10);
        return ret;
    }
public:
    int digitsCount(int d, int low, int high) {
        return recursiveCount(high, d) - recursiveCount(low - 1, d);
    }
};

示例代码 (java)

class Solution {
    public int digitsCount(int d, int low, int high) {
        return countDigit(high, d) - countDigit(low-1, d);
    }
    
    int countDigit(int n, int d) {
        if(n < 0 || n < d) {
            return 0;
        }
        
        int count = 0;
        for(long i = 1; i <= n; i*= 10) {
            long divider = i * 10;
            count += (n / divider) * i;
            
            if (d > 0) {
                count += Math.min(Math.max(n % divider - d * i + 1, 0), i); // comment1: tailing number need to be large than d *  i to qualify.
            } else {
                if(n / divider > 0) {
                    if(i > 1) {  // comment2: when d == 0, we need avoid to take numbers like 0xxxx into account.
                        count -= i;
                        count += Math.min(n % divider + 1, i);  
                    }
                }
            }
        }
        
        return count;
    }
}

示例代码 (python)

class Solution:
    def digitsCount(self, d: int, low: int, high: int) -> int:
        def helper(n, k):
            pivot, res = 1, 0
            while n >= pivot:
                res += (n // (10 * pivot)) * pivot + min(pivot, max(n % (10 * pivot) - k * pivot + 1, 0))
                res -= pivot if k == 0 else 0 # no leading zero
                pivot *= 10
            return res + 1 # last-digit can be zero
        return helper(high, d) - helper(low-1, d)

复杂度分析

时间复杂度: O(log(N))
空间复杂度: O(1)

视频讲解

我们在Youtube上更新了视频讲解，欢迎关注！