package class085;

// 范围内的数字计数

// 给定两个正整数a和b，求在[a,b]范围上的所有整数中

// 1 <= a, b

// 某个数码d出现了多少次

// 测试链接 : https://leetcode.cn/problems/digit-count-in-range/

public class Code04_DigitCount1 {

public static int digitsCount(int d, int a, int b) {

return count(b, d) - count(a - 1, d);

}

// 统计1~num范围上所有的数中，数码d出现了多少次

// 注意是1~num范围，不是0~num范围

public static int count(int num, int d) {

int ans = 0;

// left : 当前位左边的情况数

// right : 当前位右边的情况数

// 当前位的数字是cur

for (int right = 1, tmp = num, left, cur; tmp != 0; right *= 10, tmp /= 10) {

// 情况1：

// d != 0

// 1 ~ 30583 , d = 5

// cur < d的情况

// 个位cur=3 : 0000~3057 5

// 个位上没有额外加

//

// cur > d的情况

// 十位cur=8 : 000~304 5 0~9

// 十位上额外加 : 305 5 0~9

//

// cur == d的情况

// 百位cur=5 : 00~29 5 00~99

// 百位上额外加 : 30 5 00~83

// ...

// 情况2：

// d == 0

// 1 ~ 30583 d = 0

// cur > d的情况

// 个位cur=3 : 0001~3057 0

// 个位上额外加 : 3058 0

//

// cur > d的情况

// 十位cur=8 : 001~304 0 0~9

// 十位上额外加 : 305 0 0~9

//

// cur > d的情况

// 百位cur=5 : 01~29 0 00~99

// 百位上额外加 : 30 0 00~99

//

// cur == d的情况

// 千位cur=0 : 1~2 0 000~099

// 千位上额外加 : 3 0 000~583

left = tmp / 10;

cur = tmp % 10;

if (d == 0) {

left--;

}

ans += left * right;

if (cur > d) {

ans += right;

} else if (cur == d) {

ans += num % right + 1;

}

}

return ans;

}

}