首页 > 试题广场 >

页码统计

[编程题]页码统计
  • 热度指数：2882 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
牛牛新买了一本算法书，算法书一共有n页，页码从1到n。牛牛于是想了一个算法题目：在这本算法书页码中0~9每个数字分别出现了多少次？

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


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

输入

999

输出

189 300 300 300 300 300 300 300 300 300
算法知识视频讲解
添加回答
C/C++
┌；崛起`灬。°😊 头像 ┌；崛起`灬。°😊 
#include <stdio.h>
int main()
{
    int i,n,j,temp = 0,a = 1,b = 10;
    int count[10] = {0}; 
    scanf("%d",&n);
    while(n >= a)
    {
        for(j = 0;j < 10;j++)
        {
            temp = temp + n/b;    
            if(j < n%b/a)
            temp = temp + 1;
            count[j] = count[j] + temp * a;
            temp = 0;
        }
        for(i = 0;i <= n%b/a;i++)
        {
            if(i == n%b/a)
            count[i] = count[i] + n % a + 1;
        }
        count[0] = count[0] - a;
        a = a * 10;
        b = b * 10;
            
    }
    for(i = 0;i < 10;i++)
    {
        printf("%d",count[i]);
        if(9-i)
        printf(" ");    
    }
    return 0;
}

发表于 2017-09-26 17:41:06 回复(0)
nicklhk头像 nicklhk 
//从各位开始对n的每一位进行判断
#include <iostream>
#include <vector>
using namespace std;
int getCount(int n, int t)
{
	if (n < 1 || t < 0)
		return -1;
	int cnt = 0,len=0;
	int k = 1;
	int j = n;
	while (j)
	{
		j = j / 10;
		++len;
	}
	for (int i = 0; i < len; ++i)
	{
		if (t>0)
		{
			if ((n / k) % 10 < t)
				cnt += (n / (k*10))*k;
			else if ((n / k) % 10 == t)
				cnt += (n / (k * 10))*k + n%k + 1;
			else
				cnt += (n / (k * 10) + 1)*k;
		}
		else
		{
			if ((n / k) % 10 == t)
				cnt += (n / (k * 10) - 1)*k + n % k + 1;
			else
				cnt += (n / (k * 10))*k;
		}
		k = k * 10;
	}
	return cnt;
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < 10; ++i)
	{
		if (i == 0)
			cout << getCount(n, i);
		else
			cout << " " << getCount(n, i);
	}
	cout << endl;
	return 0;
}

发表于 2017-07-27 18:59:48 回复(0)
老车夫头像 老车夫 
逐位求解每个数字该位上出现的次数，累加到数组中。
#include
using namespace std;
int main(){
    int n,i,j;
    cin>>n;
    int tmp[10]={0};
    for(i=1;j=n/i;i*=10){
        int high=j/10;
        int res=j%10;
        for(int k=0;k<10;k++)
              tmp[k]+=i*high;
        for(int k=0;k<res;k++)
              tmp[k]+=i;
        tmp[res]+=n%i+1;
        tmp[0]=tmp[0]-i/10;//0的特殊处理
    }
    tmp[0]=tmp[0]-i/10;
    for(int i=0;i<9;i++)
        cout<<tmp[i]<<" ";
    cout<<tmp[9];
    return 0;
}

发表于 2017-04-19 14:35:43 回复(0)
zero_python头像 zero_python 
def find(num):
    # 计算每个数字, 在每一位上出现的次数.
    res = [0] * 10  # 结果
    digit = 1  # 个位
    while True:
        low = num % digit
        cur = (num % (10 * digit)) / digit
        high = num / (10 * digit)  # 将数字分割, 例如 digit为100时, 表示百位. 12345 将有 high = 12, cur = 3, low = 45
        
        if cur == 0 and high == 0:
            break
        
        for i in range(10):  # 从0到9, 计算i在digit位出现的次数.
            if i < cur:
                if i == 0:  # 这里主要是因为 0 不能作为数字的开头.
                    res[i] += high * digit
                else:
                    res[i] += (high+1) * digit
            elif i == cur:
                if i==0:
                    res[i] += (high-1) * digit + low + 1
                else:
                    res[i] += high * digit + low + 1
            else:
                if i == 0:
                    res[i] += (high-1) * digit 
                else:
                    res[i] += high * digit
        digit *= 10  # 下一位
    return res

num = int(raw_input())
res = find(num)
print ' '.join(map(str, res))

发表于 2017-04-01 00:44:05 回复(0)
MightOwt头像 MightOwt 
//提供一种简单的思路
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String str = "0123456789";
		while(scanner.hasNext()){
			int n = scanner.nextInt();
			int[] nums = new int[10];
			for(int i=1;i<=n;i++){
				char[] c = new String(i+"").toCharArray();
				for(int j=0;j<c.length;j++){
					nums[str.indexOf(c[j])] +=1;
				}
			}
			for(int i=0;i<nums.length-1;i++){
				System.out.print(nums[i]+" ");
			}
			System.out.println(nums[9]);
		}
	}	
}

编辑于 2017-03-09 15:12:04 回复(4)
路过的熊头像 路过的熊 
#include<iostream>
using namespace std;

int count(int n, int x) {
	int res = 0, j;
	for (int i = 1; j = n / i; i *= 10) {
		int high = j / 10;
		if (x == 0) {
			if (high)
				high--;
			else
				break;
		}
		res += high * i;
		int tem = j % 10;
		if (tem > x)
			res += i;
		else if (tem == x)
			res += n - j * i + 1;
	}
	return res;
}

int main(){
	int n;
	while (cin >> n){
		cout << count(n, 0);
		for (int i = 1; i <= 9; i++)
			cout << " " << count(n, i);
	}
	return 0;
}
//最优的解法了，时间复杂度O(log10(N))，以10为底N的对数，也就是N的位数

编辑于 2017-03-09 18:33:39 回复(7)
天祺头像 天祺 
   2位数的情况：

   N=13,个位数出现的1的次数为2，分别为1和11，十位数出现1的次数为4，分别为10,11,12,13，所以f(N) = 2+4。

   N=23,个位数出现的1的次数为3，分别为1，11，21，十位数出现1的次数为10，分别为10~19，f(N)=3+10。

   由此我们发现，个位数出现1的次数不仅和个位数有关，和十位数也有关，如果个位数大于等于1，则个位数出现1的次数为十位数的数字加1；如果个位数为0，个位数出现1的次数等于十位数数字。而十位数上出现1的次数也不仅和十位数相关，也和个位数相关：如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1，假如十位数大于1，则十位数上出现1的次数为10。

   3位数的情况:

   N=123

   个位出现1的个数为13:1,11,21，…，91,101,111,121

   十位出现1的个数为20:10~19,110~119

   百位出现1的个数为24:100~123

   我们可以继续分析4位数，5位数，推导出下面一般情况： 

   假设N，我们要计算百位上出现1的次数，将由三部分决定：百位上的数字，百位以上的数字，百位一下的数字。

   如果百位上的数字为0，则百位上出现1的次数仅由更高位决定，比如12013，百位出现1的情况为100~199,1100~1199,2100~2199，…，11100~11199，共1200个。等于更高位数字乘以当前位数，即12 * 100。

   如果百位上的数字大于1，则百位上出现1的次数仅由更高位决定，比如12213，百位出现1的情况为100~199,1100~1199,2100~2199，…，11100~11199，12100~12199共1300个。等于更高位数字加1乘以当前位数，即（12 + 1）*100。

如果百位上的数字为1，则百位上出现1的次数不仅受更高位影响，还受低位影响。例如12113，受高位影响出现1的情况：100~199,1100~1199,2100~2199，…，11100~11199，共1200个，但它还受低位影响，出现1的情况是12100~12113，共14个，等于低位数字13+1。 

public static long getFactorCount(long num,byte factor){
		long count=0;
		long current=0,next=0,before=0;
		long i=1;
		
		while((num/i)!=0){
			current=(num/i)%10;
			next=num/(i*10);
			before=num-(num/i)*i;
			
			if(current<factor){
				count+=next*i;
			}
			else if(current==factor){
				count+=next*i+before+1;
			}
			else if(current>factor)count+=(next+1)*i;
			
			i*=10;
		}
		return count;
	}
编辑于 2017-04-02 10:56:59 回复(4)
Python
LiuHDme头像 LiuHDme 
def count_digit(n, x):
    high = n // 10
    cur = n % 10
    low = 0
    digit = 1
    res = 0
    while high != 0 or cur != 0:
        if 0 <= cur < x:
            res += high * digit
        elif cur == x:
            if x == 0:
                res += (high - 1) * digit + low + 1
            else:
                res += high * digit + low + 1
        elif cur > x:
            if x == 0:
                res += high * digit
            else:
                res += (high + 1) * digit
        low += cur * digit
        cur = high % 10
        high //= 10
        digit *= 10
    return res


if __name__ == '__main__':
    n = int(input())
    for i in range(9):
        print(count_digit(n, i), end=' ')
    print(count_digit(n, 9), end='')
发表于 2021-03-13 13:42:18 回复(0)
牛客511771125号头像 牛客511771125号 
#include <iostream>
#include <algorithm>
#include<cmath>

using namespace std;

int main()
{
	int a[10] = { 0,0,0,0,0,0,0,0,0,0 };
	int num;
	cin >> num;
	for (int i = 0; i <= 9; i++)
	{
		int digit = 1;
		int temp = 0;
		while (num / digit != 0)
		{
			int qian = num / 10 / digit;
			int cur = (num / digit) % 10;
			int hou = num % digit;
			if (cur > i)
			{
				if (i != 0)
					temp += (qian + 1) * digit;
				else temp += qian * digit;
			}
			else if (cur == i)
			{
				if (i != 0)
					temp += qian * digit + hou + 1;
				else temp += (qian - 1) * digit + hou + 1;
			}
			else
			{
				temp += qian * digit;
			}
			digit *= 10;
		}
		a[i] = temp;
	}
	cout << a[0];
	for (int i = 1; i <= 9; i++)
	{
		cout << ' ' << a[i];
	}
}

发表于 2020-08-04 11:16:02 回复(0)
Python
牛客313237858号头像 牛客313237858号
def pcount(x, n):
    a, b, c, i, m = 1, 0, 0, 1, 0
    while a:
        k = x // i
        a = k // 10
        b = k % 10
        c = x % i
        if n > b:
            m += a * i
        elif n == b:
            m += ((a-bool(n==0)) * i + c + 1)
        else:
            m += (a + bool(n)) * i
        i *=10
    return m

inum = int(input())
onum = str(pcount(inum, 0))
for j in range(1, 10):
    onum += (' ' + str(pcount(inum, j)))
print(onum)


编辑于 2020-04-07 16:26:49 回复(0)
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)
逗比请来的猴子头像 逗比请来的猴子 
import java.util.Scanner;

/*
 * 本文内容主要参考：https://blog.csdn.net/zjkc050818/article/details/66474150
 * 关键之处在于针对不同的位置分别统计可能出现的的次数，然后汇总返回
 * */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] count = new int[10];
            help(count, n);
            System.out.print(count[0]);
            for (int i = 1; i < 10; i++) {
                System.out.print(" " + count[i]);
            }
            System.out.println();
        }
    }

    private static void help(int[] count, int n) {
        for (int i = 1; n / i >= 1; i *= 10) {
            int before = n / (i * 10);
            int current = n % (i * 10) / i;
            int after = n % i;

//            针对0进行特殊处理
            if (current == 0) {
                count[0] += (before - 1) * i + after + 1;
            } else {
                count[0] += before * i;
            }

//            对于1-9的元素进行统计
            for (int j = 1; j < 10; j++) {
                if (j < current) {
//                    对于0这种情况需要增加1处理
                    count[j] += (1 + before) * i;
                } else if (j == current) {
                    count[j] += before * i + after + 1;
                } else {
                    count[j] += before * i;
                }
            }
        }
    }
}
发表于 2018-04-15 19:02:06 回复(0)
冯嘉龙头像 冯嘉龙 
/*
    思路：对整数n进行取位运算（自己瞎起的名字，意思是取出个位、十位...）
          比较当前位和需要统计的数字，寻找规律如下：
        （i表示当前的位数，i=10表示比较十位数字；
          next表示当前位的后几位数字，before表示当前位的前几位数字
          例如：n=123456，i=100，则当前位为百位数字4，next表示123，before表示56）
         当统计数字为0时：
             1> 当前位==0：    count += (next - 1) * i + num % i +1;
             2> 当前位!=0：    count += next * i;
          当统计数字不为0时：
              1> 当前位 > 统计数字：    count += (next+1)*i;
              2> 当前位 = 统计数字：    count += next*i + before + 1;
              3> 当前位 < 统计数字：    count += next*i;
*/
//代码如下：
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        for (byte i = 0; i < 10; i++) {
            System.out.print(getCount(n, i));
            if (i != 9) {
                System.out.print(" ");
            }
        }
             scanner.close();
    }
    private static long getCount(long num, byte factor) {
        long count = 0;
        long current = 0, next = 0, before = 0;
        long i = 1;
        while ((num / i) != 0) {
            current = (num / i) % 10;// 取出第几位的数字
            next = num / (i * 10);// 得到current的高位数字
            before = num - (num / i) * i;// 得到current的低位数字
            // 比较current和factor的大小
            if (factor != 0) {
                if (current > factor)
                    count += (next + 1) * i;
                else if (current == factor)
                    count += next * i + before + 1;
                else if (current < factor)
                    count += next * i;
            } else if (factor == 0) {
                if ((num / i) % 10 == factor)
                    count += (next - 1) * i + num % i + 1;
                else
                    count += next * i;
            }
            i *= 10;
        }
        return count;
    }
}

发表于 2018-02-02 23:22:49 回复(0)
牛客9600109号头像 牛客9600109号
from collections import Counter
Counter(''.join([str(x) for x in range(1, N)]))
发表于 2017-11-26 17:25:24 回复(0)
绝无*仅有头像 绝无*仅有
#用python字典，代码比较简单
def page(n):
     resultDict = {}
    for i in range(1,n+1):
         for n in str(i):
            if n in resultDict:
                resultDict[n]+=1
             else:
                resultDict[n]=1
      numList = list(resultDict.keys())
      numList.sort()
      for r in numList:
            if r != "9":
                print(resultDict[r],end=" ")
            else:
                print(resultDict[r])
page(999)
发表于 2017-11-09 14:51:32 回复(0)
传说中的汽水枪头像 传说中的汽水枪 
/**
 * 时间复杂度是O(n x log10(n))
 * */
public static int[] countOfNumber(int number) {
    int[] resultArray = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    if (number < 1) {
        return resultArray;
    }
    for (int i = 1; i < number + 1; i++) {
        String iString = String.valueOf(i);
        for (int j = 0; j < iString.length(); j++) {
            String jString = iString.substring(j, j + 1);
            int key = Integer.parseInt(jString);
            int value = resultArray[key];
            resultArray[key] = value + 1;
        }
    }
    return resultArray;
}
编辑于 2017-11-04 16:55:38 回复(0)
__王_星___头像 __王_星___ 
import string

def count(number, c_list):
    next_number = number -1
    if 1 == number:
        c_list[1] += 1
        return 
    while 0 != number:
        c_list[number%10] += 1
        number = number/10
    count(next_number, c_list)



if __name__ == '__main__':
    input_num = string.atoi(raw_input())
    c_list = [0,0,0,0,0,0,0,0,0,0]
    count(input_num, c_list)
    print ' '.join([str(a) for a in c_list])
    

发表于 2017-11-02 16:26:35 回复(0)
牛客375006号头像 牛客375006号 
#include <iostream>
using namespace std;

int digitCount(long num, short digit) {
    int i = 1, count = 0;
    while (num / i > 0) {
        long before = num / (i * 10);
        if (digit == 0) {   //对于0要特殊处理
            before--;
        }
        long after = num - num / i * i;
        short current = num / i % 10;
        if (current == digit) {
            count += before * i + after + 1;
        } else if (current > digit) {
            count += (before + 1) * i;
        } else if (current < digit) {
            count += before * i;
        }
        i *= 10;
    }
    return count;
}

int main(int argc, const char * argv[]) {
    long num;
    cin >> num;
    for (int i = 0; i < 10; i++) {
        int k = digitCount(num, i);
        cout << k;
        if (i != 9) {
            cout << ' ';
        }
    }
    return 0;
}
发表于 2017-10-23 17:23:06 回复(0)
Java
hello古斯卡头像 hello古斯卡

参考博客：统计页码

发表于 2017-10-05 15:09:20 回复(0)
Java
jakiewoo_vp9头像 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)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 动态规划 测试开发工程师 数学 大数据开发工程师 Java工程师 牛客
来自：【2017】牛客模考（...
难度：
36条回答 14010浏览

热门推荐

通过挑战的用户

相关试题

页码统计

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号