Description
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1， 2，…，9。给定表示书的总页码的10 进制整数n (1≤n≤10^9) 。计算书的全部页码中分别用到多少次数字0，1，2，…，9。
Input
输入数据只有1 行，给出表示书的总页码的整数n。
Output
输出数据共有10行，在第k行输出页码中用到数字k-1 的次数，k=1，2，…，10。
Sample Input
11
Sample Output
1
4
1
1
1
1
1
1
1
1
import java.util.Scanner;
public class Main {
public static int num[] = new int[10];
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = 0;
n = cin.nextInt();
Count(n); // 统计00..00 - n之间的0-9数字的个数
num[0] -= del_zero(get_length(n)); // 减去比如0001，0066这种多余的0的个数
for (int i = 0; i < 10; i++)
System.out.println(num[i]);
}
// 获取数字的长度
public static int get_length(int num){
return (int)Math.log10(num) + 1;
}
// 获取数字的第一位数
public static int get_head(int num){
return num / (int) Math.pow(10, get_length(num) - 1);
}
// 获取数字的余数
public static int get_remainder(int num){
return num % (int) Math.pow(10, get_length(num) - 1);
}
/* 统计00..00~n之间多余的0
比如000 - 999可以看成
0 00 - 0 99, 100 - 100
0 1 - 0 9, 10 - 99
*/
public static int del_zero(int length){
if (length == 1)
return 1;
return del_zero(length - 1) + (int) Math.pow(10, length - 1);
}
// 统计00..00 - n之间0-9数字的个数
public static void Count(int n){
/* f(n) = n * 10^(n-1),
f(n)是n个0到n个9之间0-9的个数
比如f(2) = 20
表示00 - 99之间0有20个, 1有20个......9有20个
*/
/* 比如34789, 分成3组0000 - 9999
0 0000 - 0 9999
1 0000 - 1 9999
2 0000 - 2 9999
*/
for (int i = 0; i < 10; i++){
num[i] = num[i] + get_head(n) * (get_length(n) - 1) * (int) Math.pow(10, (get_length(n) - 2));
}
/* 比如34789, 首位0, 1, 2分别加上10000个
00000 - 09999
10000 - 19999
20000 - 29999
*/
for (int i = 0; i < get_head(n); i++){
num[i] = num[i] + (int) Math.pow(10, get_length(n) - 1);
}
// 比如34789, 首位3, num[3]加上余数4789和特殊情况30000
num[get_head(n)] += get_remainder(n) + 1;
// 如果余数为0, 比如 40000, num[0] 得加上长度-1,并且余数为0时结束递归
if (get_remainder(n) == 0) {
num[0] += get_length(n) - 1;
return;
}
/* 比如4000589这种情况, 直接余数递归回漏掉中间的0
所以num[0]得加上(7 - 1 - 3) * (589 + 1)
*/
if (get_length(n) - 1 != get_length(get_remainder(n))) {
num[0] += (get_length(n) - 1 - get_length(get_remainder(n))) * (get_remainder(n) + 1);
}
// 用余数接着递归
Count(get_remainder(n));
}
}