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);
}
}