页码统计

[编程题]页码统计

热度指数：2906 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛新买了一本算法书，算法书一共有n页，页码从1到n。牛牛于是想了一个算法题目：在这本算法书页码中0~9每个数字分别出现了多少次？

输入描述:

输入包括一个整数n(1 ≤ n ≤ 1,000,000,000)

输出描述:

输出包括一行10个整数，即0~9这些数字在页码中出现的次数，以空格分隔。行末无空格。

示例1

输入

输出

189 300 300 300 300 300 300 300 300 300

算法知识视频讲解

Java

曼达啊

import java.util.*;
public class Main {
	public static void main(String[] ags) {
		Scanner in = new Scanner(System.in);
		long n = in.nextLong();
		in.close();
		
		long[] numbers = new long[11];
		long i =0;
		
		for( i=1; n/i!=0;i=i*10) {			
			for(int j=1; j<10;j++) {
/**
*(n%(i*10))/i 是计算当前位置上的数，看前面同学的算法，分别计算before，current，after似乎更容易
*/
				if(j<((n%(i*10))/i)) {
					numbers[j]=numbers[j]+(n/(i*10) + 1)*i;
				}
				else if(j==((n%(i*10))/i)) {
					numbers[j]=numbers[j]+(n/(i*10))*i+n%i+1;
				}
				else numbers[j]=numbers[j]+(n/(i*10))*i;;

			}
			if(((n%(i*10))/i)==0) {
				numbers[0]=numbers[0]+(n/(i*10)-1)*i+n%i+1;
			}
			else {
				numbers[0]=numbers[0]+(n/(i*10))*i;
			}
				
				
		}
		
		for(int j =0; j<9; j++) {
			System.out.print(numbers[j] + " ");
		}
		System.out.print(numbers[9]);
	
	}

}

就这么个题，从早上写到晚上，脑子里像一团浆糊

发表于 2020-04-05 06:57:05 回复(0)

Java

hello古斯卡

参考博客：统计页码

发表于 2017-10-05 15:09:20 回复(0)

Java

jakiewoo_vp9

不确定有没有bug, 例子上的输出通过。有点儿动态规划的意思，
每遇到一个数字，把每一位提取出来，累加到该数字之前的结果上。 
看了其他人的回答，测试 900000000，输出为
708888897 
820000000 
820000000 
820000000 
820000000 
820000000 
820000000 
820000000 
820000000 
720000001

public static void calculate(int n) { 
    int[] numbers = new int[10];  for (int i = 1; i<=n; i++) { 
        int k = i; do {
            numbers[k % 10]++;  k /= 10; 
             } while (k > 0); 
     } 
for (int number : numbers) {
System.out.println(number + " ");  }
 }

编辑于 2017-09-18 14:45:19 回复(0)

Java

gs54

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    while(sc.hasNextInt()){
        int n=sc.nextInt();
        int arr[]=new int[10];
        for(int i=0;i<10;i++){
            arr[i]=0;
        }
        count(n,arr);
        for(int i=0;i<9;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.print(arr[9]);
    }


}
public static void count(int n,int arr[]){
    int i=1;

    while(n/i!=0){
        int before=n/(i*10);
        int after=n%i;
        int current=(n/i)%10;
        if(current==0){
            arr[0]+=(before-1)*i+after+1;
        }else{
            arr[0]+=before*i;
        }
        for(int index=1;index<10;index++){
            if(index<current){
                arr[index]+=(1+before)*i;
            }else if(index==current){
                arr[index]+=before*i+after+1;
            }else{
                arr[index]+=before*i;
            }
        }
        i=i*10;
    }

}

} //时间复杂度O(log10(N))

发表于 2017-03-16 22:27:59 回复(0)