1009 数字1的数量

1 秒 131,072 KB 80 分 5 级题

题目描述

给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。
例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。

输入

输入N(1 <= N <= 10^9)

输出

输出包含1的个数

输入样例

12

输出样例

5

解析:
这题有点难受，我自己是不会做的。百度了，大家都说是数学逻辑或则数位dp。看了篇博客，得出自己的理解
大佬的链接

个人理解:
  看了大佬的博客，在做dp的时候是在打表，首先把一个10进制数分不同位来确定第i 位为数j 所包含的1的数量。dp[i][j] 即表示第i 位为数j 所包含的1的数量
    例如：假设我现在是第2位为1，即dp[2][1] ，它就表示19及以前的所有数包含的1的数目
    再如：假设是第3位为2，即dp[3][2] ，它表示299及以前的所有数中1的数量。
  总之，dp[i][j] 表示的是第 i 位为数 j的最大的数及之前的所有数中1的数量。

  生成dp[][]的公式：(不知道怎么写公式，就直接加代码了)

	if(j==0) {//j表示这个数是几
		dp[i][j] = dp[i-1][9];			
	} else {
		dp[i][j] = dp[i-1][9] + dp[i][j-1] + (int)Math.pow((j==1?1:0) * 10, i-1); 
		//另外在这里有个问题，今天写了个bug
		//上面的 (j==1?1:0) * 10，这样写是做了三目运算之后再乘10
		//如果写成了 j==1?1 : 0 * 10，就是先0*10，再做三目运算
		//三目运算符的两个运算符所分割的三个部分，每个部分单独成为三目运算的一部分，如果要把结果用在其他的运算中，必须打括号。
	}

  在计算1的个数的时候还需要考虑到一个问题，假设我们的数是255，一次对每一位数进行处理。首先处理2，因为上面说到了dp存的数据计算方式，所以先加dp[3][1] ，（因为dp[3][2] 表示的是1-299之间的1的数量，所以加的是dp[3][1]），然后依次处理的剩下的位数。
  当处理的某一位数是1时，需要加上比他位数低的数组成的数。例如：135，在加了dp[3][0], dp[2][2], dp[1][5] 之后，我们会忽略一部分，100-135中作为百位的1没有计算，所以还要加上（35+1）。

完整AC代码：（在看大佬博客的时候，不知道为什么他会使用long long, 后来把dp全部输出之后才发现，结果会超出int的数据范围，所以设置为long long， 但是下面的代码过题却是没问题的）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		Scanner input = new Scanner(System.in);
		
		int[][] dp = new int[11][11];
		for(int i=1; i<=9; i++) {
			dp[1][i] = 1; 
		}
		
		for(int i=2; i<=10; i++) {
			for(int j=0; j<=9; j++) {
				if(j==0) {
					dp[i][j] = dp[i-1][9];
				}
				else {
					dp[i][j] = dp[i-1][9] + dp[i][j-1] + (int)Math.pow((j==1?1:0) * 10, i-1); 
				}
				
			}
		}

		int n = input.nextInt();
		int m = n;
		
		int[] pos = new int[11];
		int index = 0;
		while(n>0) {
			pos[++index] = n%10;
			n /= 10;
		}
		
		int[] add = new int[11];
		for(int i=index; i>=1; i--) {
			int tmp = (int)Math.pow(10, i-1);
			add[i] = m%tmp; 
		}
		
		int ans = 0;
		for(int i=index; i>=1; i--) {
			if(i>1) {
				ans += pos[i]>0 ? dp[i][pos[i]-1] : 0;
				System.out.print((pos[i]>0 ? dp[i][pos[i]-1] : 0) + " ");
			} else {
				ans += dp[i][pos[i]];
				System.out.print(dp[i][pos[i]]+ " ");
			}
			if(pos[i]==1 && i>1) {
				ans += add[i]+1;
				System.out.print(add[i]+1 + " ");
			}
		}
		System.out.println(ans);
	}
}