LintCode 3867 · 范围内的数字计数

问题分析

计算在区间 [low, high] 中，数字 d 出现的次数。

核心思想：使用数位DP或前缀和思想
• count(low, high) = count(0, high) - count(0, low-1)

方法一：逐位统计法（推荐）AC

public class Solution {
/**
* @param d: a digit
* @param low: the lower bound
* @param high: the upper bound
* @return: the number of d in the range from low to high
*/
public int digitsCount(int d, int low, int high) {
return count(high, d) - count(low - 1, d);
}

// 计算 [0, n] 中数字 d 出现的次数
private int count(int n, int d) {
    if (n < 0) return 0;
    
    long result = 0;
    long base = 1;  // 当前位的权重：1, 10, 100, ...
    
    while (base <= n) {
        // 将数字分为三部分：高位、当前位、低位
        long high = n / (base * 10);  // 高位
        long cur = (n / base) % 10;   // 当前位
        long low = n % base;          // 低位
        
        if (d == 0) {
            // 处理 d=0 的特殊情况（不能把前导零算进去）
            if (high > 0) {
                if (cur > d) {
                    result += high * base;
                } else if (cur == d) {
                    result += (high - 1) * base + low + 1;
                } else {
                    result += (high - 1) * base;
                }
            }
        } else {
            // d != 0 的情况
            if (cur > d) {
                result += (high + 1) * base;
            } else if (cur == d) {
                result += high * base + low + 1;
            } else {
                result += high * base;
            }
        }
        
        base *= 10;
    }
    
    return (int) result;
}

}

方法二：数位DP（递归写法）超时

public class Solution {
public int digitsCount(int d, int low, int high) {
return dfs(high, d, true, false) - dfs(low - 1, d, true, false);
}

// limit: 是否受到上界限制
// lead: 是否有前导零
private int dfs(int n, int d, boolean limit, boolean lead) {
    if (n < 0) return 0;
    String s = String.valueOf(n);
    int len = s.length();
    int[][] memo = new int[len][2];
    for (int[] row : memo) Arrays.fill(row, -1);
    return dp(s, 0, d, limit, lead, memo);
}

private int dp(String s, int pos, int d, boolean limit, boolean lead, int[][] memo) {
    if (pos == s.length()) {
        return lead ? 0 : 0;  // 返回已统计的结果
    }
    
    if (!limit && !lead && memo[pos][lead ? 1 : 0] != -1) {
        return memo[pos][lead ? 1 : 0];
    }
    
    int up = limit ? s.charAt(pos) - '0' : 9;
    int res = 0;
    
    for (int i = 0; i <= up; i++) {
        if (i == d) {
            if (lead && i == 0) {
                // 前导零不计入
                res += dp(s, pos + 1, d, limit && i == up, true, memo);
            } else {
                res += dp(s, pos + 1, d, limit && i == up, false, memo);
            }
        } else {
            res += dp(s, pos + 1, d, limit && i == up, lead && i == 0, memo);
        }
    }
    
    if (!limit && !lead) {
        memo[pos][lead ? 1 : 0] = res;
    }
    
    return res;
}

}

算法解释

逐位统计原理

以 n = 2593, d = 5 为例，统计十位为5的次数：

位置 高位 当前位 低位 贡献

个位 259 3 0 26×1=26 (0-25的十位)

十位 25 9 3 26×10=260 (0-25的十位)

百位 2 5 93 2×100+94=294 (0-199 + 200-259)
复杂度分析
方法 时间复杂度 空间复杂度

逐位统计 O(log n) O(1)

数位DP O(log n × 状态数) O(log n)

推荐使用逐位统计法，代码简洁高效！