核心思想
数位dp的尝试方式并不特殊，绝大多数都是线性展开，类似从左往右的尝试 数位dp是在数字的每一位上进行线性展开而已 不同的题目有不同的限制，解题核心在于：可能性的整理、排列组合的相关知识
解决数位dp的问题 ，推荐使用记忆化搜索的方式，可能性的展开会很好写，不必刻意追求进一步改写 递归写出来问题就解决了，位数多就挂缓存，位数不多甚至不挂缓存也能通过
例题
1、 windy数
题目描述： 不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，在 a 和 b 之间，包括 a 和 b ，总共有多少个 windy 数？ 输入只有一行两个整数，分别表示 a 和 b。 输出一行一个整数表示答案。 输入输出样例 输入 1 10 输出 9 输入 25 50 输出 20 说明/提示 数据规模与约定 对于全部的测试点，保证 1≤a≤b≤2×109。
解题思路：
这个题是同样可以用上一节的 084、数位dp-上的思路，只不过这里面加了windy数的判断
windy数与上一位的数有关，这就意味着递归的过程必须把上一位的数也带上，那么这里我们就用当pre=10的时候表示上一位没有取值，0-9表示上一位取值多少
整体的大思路就是：0b的windy数数目-0a-1的windy数数目
主要就在于求解windy数的数目可能性分析，就在之前的数位dp模版上加上windy数判定条件就可以了
代码如下：
package main.java.class085;
import java.io.*;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_WindyNumber
* @description: windy数
* // 不含前导零且相邻两个数字之差至少为2的正整数被称为windy数
* // windy想知道[a,b]范围上总共有多少个windy数
* // 测试链接 : https://www.luogu.com.cn/problem/P2657
* @author: zs宝
* @create: 2025-10-13 10:28
* @Version 1.0
**/public class Code01_WindyNumber {
public static int MAXLEN=11;
public static int[][][]dp=new int[MAXLEN][11][2];
public static int a,b;
public static void build(int len){
for(int i=0;i<=len;i++){
for(int j=0;j<11;j++){
dp[i][j][0]=-1;
dp[i][j][1]=-1;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader buffer=new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in=new StreamTokenizer(buffer);
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken()!=StreamTokenizer.TT_EOF){
a=(int)in.nval;
in.nextToken();
b=(int)in.nval;
out.println(compute());
}
out.flush();
out.close();
buffer.close();
}
public static int compute(){
return cnt(b)-cnt(a-1);
}
public static int cnt(int nums){
if(nums==0){
return 1;
}
int len=1;
int offset=1;
int temp=nums/10;
while (temp>0){
len++;
offset*=10;
temp/=10;
}
build(len);
//求解0-a之间有多少windy数
return f(nums,offset,len,10,0);
}
/**
* 返回 从nums的第i位开始，windy数的个数
* @param nums 数值
* @param offset 辅助求出nums在i位上的数值，由i而来
* @param i 当前第几位
* @param pre 前一位的数值为多少，若为10，则说明前一位没有取值
* @param free 只有1或者0。若为1则说明前一位的数比nums对应位上的数小，当前及后续位的数值在<=nums的条件下可以随便取；若为0则说明前一位的数与nums对应位上的数相等，当前及后续位的数值在<=nums的条件下不可以随便取
* @return
*/
public static int f(int nums,int offset,int i,int pre,int free){
//走到第0位说明找到一个符合条件的数值
if(i==0){
return 1;
}
if(dp[i][pre][free]!=-1){
return dp[i][pre][free];
}
//求出nums当前第i位上的数值
int cur=nums/offset%10;
int ans=0;
//当free==0是，即当前位不能随便取值
if(free==0){
//当free==0且pre=10(之前的数没有取值时),只有一种情况，当前位为最高位
if(pre==10){
//可以接着当前位置不取数值
ans+=f(nums,offset/10,i-1,10,1);
//当前位置取值的时候
for(int p=1;p<cur;p++){
ans+=f(nums,offset/10,i-1,p,1);
}
//当前位取cur时
if(cur!=0){
ans+=f(nums,offset/10,i-1,cur,0);
}
}else {
//当free==0且之前的数有取值时
for(int p=0;p<cur;p++){
if(p<=pre-2 || p>=pre+2){
ans+=f(nums,offset/10,i-1,p,1);
}
}
if(cur>=pre+2 || cur<=pre-2){
ans+=f(nums,offset/10,i-1,cur,0);
}
}
}else{
//当free==1时，说明在比nums小的条件下，当前位置可以随便取值
if(pre==10){
//前一位没有取值时
//仍然可以接着当前位不取值
ans+=f(nums,offset/10,i-1,10,1);
//当前位取值
for(int p=1;p<=9;p++){
ans+=f(nums,offset/10,i-1,p,1);
}
}else{
//前一位取了值
for(int p=0;p<=9;p++){
if(p<=pre-2 || p>=pre+2){
ans+=f(nums,offset/10,i-1,p,1);
}
}
}
}
dp[i][pre][free]=ans;
return ans;
}
}2、萌数
题目描述： 如果一个数字，存在长度至少为2的回文子串，那么这种数字被称为萌数 比如101、110、111、1234321、45568 求[l, r]范围上，有多少个萌数 由于答案可能很大，所以输出答案对1000000007求余
解题思路：
这个题的大思路和之前的题类似，都是：
0r的萌数-0l的萌数
最后检查l是不是萌数，是的话最终结果+1
但是这个题如何判断一个很数是不是萌数呢？
判断一个数是不是萌数，正面去想，找不到直接判断的思路
那么这个时候就可以从反面想，如何判断一个数不是萌数
通过观察，我们发现萌数一定会出现num[i]== num[i-1] || num[i] == num[i-1]这样的结构，那么非萌数就一定不包含这样的结构
萌数的个数=总个数-非萌数的数量
注意，这个题还有一个需要非常注意的点
给定的数据，其位数最大可达到1000，这就表明给定的数值已经超过了long的最大范围，我们不能直接读取，而是以字符串的形式读取，注意这里的读取方法代码
同时注意，这里的总个数的同余原理
代码如下
package main.java.class085;
import java.io.*;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_MengNumber
* @description: 萌数
* // 如果一个数字，存在长度至少为2的回文子串，那么这种数字被称为萌数
* // 比如101、110、111、1234321、45568
* // 求[l,r]范围上，有多少个萌数
* // 由于答案可能很大，所以输出答案对1000000007求余
* // 测试链接 : https://www.luogu.com.cn/problem/P3413
* @author: zs宝
* @create: 2025-10-14 09:05
* @Version 1.0
**/public class Code02_MengNumber {
public static int MAXN=1001;
public static int MOD=1000000007;
public static int[][][][]dp=new int[MAXN][11][11][2];
public static void main(String[] args) throws IOException {
BufferedReader buffer=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
//注意这里的读取数据的方法，数据位数最大可达到1000，明显超过long的最大范围，只能以string数组读取
//记住这里的读取数据方式
String[]strs=buffer.readLine().split(" ");
out.println(compute(strs[0].toCharArray(),strs[1].toCharArray()));
out.flush();
out.close();
buffer.close();
}
public static int compute(char[] l, char[] r){
//分别计算0-r的萌数，0-l的萌数
int ans=(cnt(r)-cnt(l)+MOD)%MOD;
if(check(l)){
ans=(ans+1)%MOD;
}
return ans;
}
/**
* 计算0-num有多少萌数
* @param num
* @return
*/
public static int cnt(char[]num){
int n=num.length;
//给定的数值，题目不可能最高位为0，除非给的数值就是0
if(num[0]=='0'){
return 0;
}
//注意题目的数据位数最大位1000，不能以常规的转换方式进行计算
//计算0-all范围的萌数有多少
//所有数-非萌数
//先对所有数用同余原理求解
long all=0;
long base=1;
for(int i=n-1;i>=0;i--){
all=(all+(num[i]-'0')*base)%MOD;
base=(base*10)%MOD;
}
build(n);
return (int)(all-f(num,0,10,10,0)+MOD)%MOD;
}
/**
*初始化dp数组
* @param n
*/
public static void build(int n){
for(int i=0;i<n;i++){
for(int j=0;j<11;j++){
for(int k=0;k<11;k++){
for(int w=0;w<2;w++){
dp[i][j][k][w]=-1;
}
}
}
}
}
/**
* 计算从num的高位第i为向低位开始算起，非萌数有多少
* @param num
* @param i 第i位
* @param pp 第i位的前两位上的数值，为10表示前2位未取数值
* @param p 第i为的前一位上的数值，为10表示前1位未取数值
* @param free 在小于num的条件下，当前位的数值能否随意选择。1表示可以随意取值，0表示不能随意取值
* @return
*/
public static int f(char[]num,int i,int pp,int p,int free){
if(i==num.length){
return 1;
}
if(dp[i][pp][p][free]!=-1){
return dp[i][pp][p][free];
}
int cur=num[i]-'0';
int ans=0;
//不能随意选取数值的时候
if(free==0){
if(pp==10 && p==10){
//接着什么都不取值
ans=(ans+f(num,i+1,10,10,1))%MOD;
//取值
//free=0，pp=10,p=10是只有最高为才会出现的情况
for(int pick=1;pick<cur;pick++){
ans=(ans+f(num,i+1,10,pick,1))%MOD;
}
//当取的值和cur相同时
ans=(ans+f(num,i+1,10,cur,0))%MOD;
} else if (pp == 10 && p != 10) {
//前一位有值，但是前2为无值的时候
//既然前一位已经开始取值，后续的都必须取值
for(int pick=0;pick<cur;pick++){
if(pick!=p){
ans=(ans+f(num,i+1,p,pick,1))%MOD;
}
}
//判读当前位和num去相同的值能否
if(cur!=p){
ans=(ans+f(num,i+1,p,cur,0))%MOD;
}
}else if (pp!=10 && p!=10){
//前一位有值，前二位也有值的时候
for(int pick=0;pick<cur;pick++){
if(pick!=p && pick!=pp){
ans=(ans+f(num,i+1,p,pick,1))%MOD;
}
}
if(cur!=pp && cur!=p){
ans=(ans+f(num,i+1,p,cur,0))%MOD;
}
}
}else{
//free==1,当前位在比num小的条件下可以取任意值
if(pp==10 && p==10){
//接着什么都不取值
ans=(ans+f(num,i+1,10,10,1))%MOD;
//取值
//free=0，pp=10,p=10是只有最高为才会出现的情况
for(int pick=0;pick<=9;pick++){
ans=(ans+f(num,i+1,10,pick,1))%MOD;
}
} else if (pp == 10 && p != 10) {
//前一位有值，但是前2为无值的时候
//既然前一位已经开始取值，后续的都必须取值
for(int pick=0;pick<=9;pick++){
if(pick!=p){
ans=(ans+f(num,i+1,p,pick,1))%MOD;
}
}
}else if (pp!=10 && p!=10){
//前一位有值，前二位也有值的时候
for(int pick=0;pick<=9;pick++){
if(pick!=p && pick!=pp){
ans=(ans+f(num,i+1,p,pick,1))%MOD;
}
}
}
}
dp[i][pp][p][free]=ans;
return ans;
}
//检查nums是否是萌数
public static boolean check(char[]num){
int n=num.length;
boolean flag=false;
for(int i=1;i<n;i++){
if(i-1>=0 && num[i]==num[i-1]){
flag=true;
break;
}
if(i-2>=0 && num[i]==num[i-2]){
flag=true;
break;
}
}
return flag;
}
}3、不含连续1的非负整数
题目描述： 给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。
示例 1:
输入: n = 5 输出: 5 解释: 下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示： 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 其中，只有整数 3 违反规则（有两个连续的 1 ），其他 5 个满足规则。
示例 2:
输入: n = 1 输出: 2
示例 3:
输入: n = 2 输出: 3
提示:
1 <= n <= 109
解法思路：
第一种思路，数位dp基本模版的讨论各种情况，暴力递归
先将给定的数值的二进制位求出来，并保存到一个数组中去
然后就按照数位dp的基本模版讨论取的数值比给定的n小的情况，同时加上不能有连续1的条件
相当于递归需要还剩下几位i, 前一位取的数值为多少pre，当前位是否可以随意取值0/1
但是这种解法我最开始犯了一个错误
我想判定每一位的情况是否为1，我用的是
n & (1<<i), 这个代码确实可以判定当前位是不是1，但是当当前位为1的时候，它得到的值不一定为1，既要判断当前位是否为1，又要可以为1就得到1的值，应该表达式为(n >> k) & 1
第二中思路，观察不同位数满足不能有连续1的数值个数规律，
可以发现，这就是一个斐波拉契数列
运用打表的方式，减少递归的计算
详细的思路流程，已经写在代码注释中
代码如下：
package main.java.class085;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_IntegersWithoutConsecutiveOnes
* @description: 不含连续1的非负整数
* // 给定一个正整数n，请你统计在[0, n]范围的非负整数中
* // 有多少个整数的二进制表示中不存在连续的1
* // 测试链接 : https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/
* @author: zs宝
* @create: 2025-10-14 10:18
* @Version 1.0
**/public class Code03_IntegersWithoutConsecutiveOnes {
class Solution {
public int findIntegers(int n) {
return findIntegers3(n);
}
//暴力递归的解法
public int findIntegers1(int n) {
//提取出n的每一位的数值
int[]nums=new int[32];
//计算最高位的位置
int start=32;
for(int i=0,k=31;i<32;i++,k--){
nums[i] = (n >> k) & 1;
if (start == 32 && nums[i] == 1) {
start = i;
}
}
int[][][]dp=new int[32][3][2];
for(int i=0;i<32;i++){
for(int j=0;j<3;j++){
for(int k=0;k<2;k++){
dp[i][j][k]=-1;
}
}
}
return f1(nums,start,2,0,dp);
}
/**
numsz:最大值的位数组
i:当前来到第几位
pre:前一位的数值是多少0/1,如果位2说明前一位没有取值
free：在比nums取值小的条件下，当前位是否可以任意选值，0表示不想，1表示行
*/
public int f1(int[]nums,int i,int pre,int free,int[][][]dp){
if(i==32){
return 1;
}
if(dp[i][pre][free]!=-1){
return dp[i][pre][free];
}
int ans=0;
int cur=nums[i];
if(free==0){
//前一位没有选择,且free=0，不能随意选择数字
//说明当前来到的位是最高位
if(pre==2){
if(cur==1){
//当前位置可以去0/1
ans+=f1(nums,i+1,1,0,dp);
ans+=f1(nums,i+1,0,1,dp);
}else{
ans+=f1(nums,i+1,0,0,dp);
}
}else if(pre==1){
//如果前一个位为1，则当前位只能取0
if(cur==1){
ans+=f1(nums,i+1,0,1,dp);
}else{
ans+=f1(nums,i+1,0,0,dp);
}
}else{
//pre==0时
if(cur==1){
//当前位置可以去0/1
ans+=f1(nums,i+1,1,0,dp);
ans+=f1(nums,i+1,0,1,dp);
}else{
ans+=f1(nums,i+1,0,0,dp);
}
}
}else{
//free==1时
if(pre==2){
ans+=f1(nums,i+1,1,1,dp);
ans+=f1(nums,i+1,0,1,dp);
}else if(pre==1){
ans+=f1(nums,i+1,0,1,dp);
}else{
ans+=f1(nums,i+1,1,1,dp);
ans+=f1(nums,i+1,0,1,dp);
}
}
dp[i][pre][free]=ans;
return ans;
}
//观察规律，打表加速计算
public int findIntegers2(int n) {
//位数组，表示当只有几位时，不存在连续1的个数有多少
//cnt[len] : 二进制如果有len位，所有二进制状态中不存在连续的1的状态有多少个，辅助数组
//如 总共只有0位：只有0一个数 所以有1个
//总共有1位，0,1总共2个数符合要求
//总共有2位，00,01,10 符合要求，总共有3个数符合要求
//依次类推,找到规律，cnt[i]=cnt[i-1]+cnt[i-2]
int []cnt=new int[31];
cnt[0]=1;
cnt[1]=2;
for(int i=2;i<31;i++){
cnt[i]=cnt[i-1]+cnt[i-2];
}
//返回结果
return f2(cnt,n,30);
}
/**
从num二进制形式的高位开始，当前来到第i位，之前的位完全和num一样
返回<=num且不存在连续的1的状态有多少个
*/
public int f2(int[]cnt,int num,int i){
if(i==-1){
//走完所有位
return 1;
}
int ans=0;
if((num & (1<<i))!=0){
//当当前位上的值为1时
//前面的位数取值又和num一样
//当满足比num值小的条件，当前位可以取0
//一旦取0，那么下一位第i-1位取什么值都可以
//而我们要求的不含连续1的数值个数
//当第i位取0时，后面的1~i-1位就可以自由发挥，只要满足二进制不含连续的1即可
//而多少位满足条件的二进制个数我们已经通过打表cnt得到了,现在只需要从中取出来即可
//要的是1~i-1位满足条件的二进制个数，由于cnt的下标是从0开始，即共有i-1位的值对应在cnt下标i-1+1上的值
//即cnt[i]
ans+=cnt[i];
//而当前位能否取1，必须看第i+1位是否为1，因为不能取连续的1，并且f2函数调用时就是保证每位取值和num一样
if((num & (1<<(i+1)))!=0){
//若第i+1位为1
//则第i位不能取1
//而f2函数调用时就是保证每位取值和num一样
//所以后续不能再接着递归调用了
return ans;
}
}
//当第i位取和num一样的值时，此时要接着往后调可能性
ans+=f2(cnt,num,i-1);
return ans;
}
//方法2的递归改为迭代
public int findIntegers3(int num) {
//位数组，表示当只有几位时，不存在连续1的个数有多少
//cnt[len] : 二进制如果有len位，所有二进制状态中不存在连续的1的状态有多少个，辅助数组
//如 总共只有0位：只有0一个数 所以有1个
//总共有1位，0,1总共2个数符合要求
//总共有2位，00,01,10 符合要求，总共有3个数符合要求
//依次类推,找到规律，cnt[i]=cnt[i-1]+cnt[i-2]
int []cnt=new int[31];
cnt[0]=1;
cnt[1]=2;
for(int i=2;i<31;i++){
cnt[i]=cnt[i-1]+cnt[i-2];
}
int ans=0;
for(int i=30;i>=-1;i--){
if(i==-1){
ans++;
break;
}
if((num & (1<<i))!=0){
ans+=cnt[i];
if((num & (1<<(i+1)))!=0){
return ans;
}
}
}
//返回结果
return ans;
}
}
}4、范围内的数字计数
题目描述： 给定两个正整数a和b，求在[a, b]范围上的所有整数中 某个数码d出现了多少次 1 <= a, b
解题思路：
对给定的数值，的每一位个十百千万位分别取为d做分类讨论
而这时又要对当前位（取为d的这一位）上的数值做讨论
当当前位上的数值cur< d时，
假设数值为345289，这个时候我们要考虑百位上的数值2与给定数值d (假设为4的关系)
345 2 89，对于前面的345, 取0-344时（共有345个值），让2变成4丝毫不会影响取的数值比原本数值小的这个条件。注意这里要注意d若等于0，那么前面的取值0-344不能取0，因为全部取0可能造成最终取值为0，但要求的范围是>=1
而当高3位在0-344时，低2位的89其实完全可以取到0-99（共有100个值），不影响值比345289小
所以个数为345* 100
当当前位上的数值cur>d时,
假设数值为345289，这个时候我们要考虑千位上的数值5与给定数值d (假设为4的关系)
34 5 289 ，对于前面高位的0-33（共34个值）都可以有34* 1000（289三位数值0-999共1000个数值）
而由于5>4，所以除了有cur< d的情况外，当高几位为34 4 时后面3位仍然可以取0-999（共1000个数值）
当当前位上的数值cur== d时
假设数值为345289，这个时候我们要考虑万位上的数值4与给定数值d (假设为4的关系)
3 4 5289，对于前面的高位0-2（共3个值）都可以有3* 10000（5289四位数值0-9999共10000个数值）
而由于4== 4，所以除了有cur< d的情况外，当高几位为3 4 时后面4位只能取0-5289（共5289+1个数值）
代码如下
package main.java.class085;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_DigitCount1
* @description: 范围内的数字计数
* // 给定两个正整数a和b，求在[a,b]范围上的所有整数中
* // 1 <= a, b
* // 某个数码d出现了多少次
* // 测试链接 : https://leetcode.cn/problems/digit-count-in-range/
* @author: zs宝
* @create: 2025-10-15 10:39
* @Version 1.0
**/public class Code04_DigitCount1 {
public static int digitsCount(int d, int a, int b) {
return count(b, d) - count(a - 1, d);
}
// 统计1~num范围上所有的数中，数码d出现了多少次
// 注意是1~num范围，不是0~num范围
public static int count(int num, int d) {
int ans=0;
for(int right=1,temp=num,left,cur;temp!=0;right*=10,temp/=10){
// 情况1：
// d != 0
// 1 ~ 30583 , d = 5 // cur < d的情况
// 个位cur=3 : 0000~3057 5
// 个位上没有额外加
//
// cur > d的情况
// 十位cur=8 : 000~304 5 0~9
// 十位上额外加 : 305 5 0~9 // // cur == d的情况
// 百位cur=5 : 00~29 5 00~99
// 百位上额外加 : 30 5 00~83 // ... // 情况2：
// d == 0
// 1 ~ 30583 d = 0 // cur > d的情况
// 个位cur=3 : 0001~3057 0
// 个位上额外加 : 3058 0 // // cur > d的情况
// 十位cur=8 : 001~304 0 0~9
// 十位上额外加 : 305 0 0~9 // // cur > d的情况
// 百位cur=5 : 01~29 0 00~99
// 百位上额外加 : 30 0 00~99 // // cur == d的情况
// 千位cur=0 : 1~2 0 000~099
// 千位上额外加 : 3 0 000~583 //当前来讨论temp的最低位作为d的时候的可能数
//其左边的数有多少
left=temp/10;
//当前讨论的位置上的数值为多少
cur=temp%10;
if(d==0){
left--;
}
//先讨论无论是cur>d,<d,=d都会有的情况，即所有类型情况都包含当cur<d时的讨论,但是cur==d或者cur>d又都有自己的单独讨论
ans+=left*right;
//接着讨论如果cur=d或者cur>d的情况
if(cur>d){
ans+=right;
} else if (cur==d) {
ans+=num%right+1;
}
}
return ans;
}
}5、数字计数
题目描述： 给定两个正整数 a 和 b，求在 [a,b] 中的所有整数中，每个数码（digit）各出现了多少次。
输入格式
仅包含一行两个整数 a,b，含义如上所述。
输出格式
包含一行十个整数，分别表示 0∼9 在 [a,b] 中出现了多少次。
输入输出样例
输入 #1复制
1 99
输出 #1复制
9 20 20 20 20 20 20 20 20 20
说明/提示
数据规模与约定
对于 30% 的数据，保证 1≤a≤b≤106；
对于 100% 的数据，保证 1≤a≤b≤1012。
解题思路：
和第4题思路一致，只是本题不再给定d, 而是将d=0-9都算一遍
代码如下
package main.java.class085;
import java.io.*;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code05_DigitCount
* @description: 范围内的数字计数
* // 给定两个正整数a和b，求在[a,b]范围上的所有整数中
* // 每个数码(digit)各出现了多少次
* // 1 <= a, b
* // 测试链接 : https://www.luogu.com.cn/problem/P2602
* @author: zs宝
* @create: 2025-10-15 11:32
* @Version 1.0
**/public class Code05_DigitCount {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
long a = (long) in.nval;
in.nextToken();
long b = (long) in.nval;
for (int i = 0; i < 9; i++) {
out.print(digitsCount(i, a, b) + " ");
}
out.println(digitsCount(9, a, b));
}
out.flush();
out.close();
br.close();
}
public static long digitsCount(int d, long a, long b) {
return count(b, d) - count(a - 1, d);
}
// 统计1~num范围上所有的数中，数码d出现了多少次
// 注意是1~num范围，不是0~num范围
public static long count(long num, int d) {
long ans=0;
for(long right=1,temp=num,left,cur;temp!=0;right*=10,temp/=10){
// 情况1：
// d != 0
// 1 ~ 30583 , d = 5 // cur < d的情况
// 个位cur=3 : 0000~3057 5
// 个位上没有额外加
//
// cur > d的情况
// 十位cur=8 : 000~304 5 0~9
// 十位上额外加 : 305 5 0~9 // // cur == d的情况
// 百位cur=5 : 00~29 5 00~99
// 百位上额外加 : 30 5 00~83 // ... // 情况2：
// d == 0
// 1 ~ 30583 d = 0 // cur > d的情况
// 个位cur=3 : 0001~3057 0
// 个位上额外加 : 3058 0 // // cur > d的情况
// 十位cur=8 : 001~304 0 0~9
// 十位上额外加 : 305 0 0~9 // // cur > d的情况
// 百位cur=5 : 01~29 0 00~99
// 百位上额外加 : 30 0 00~99 // // cur == d的情况
// 千位cur=0 : 1~2 0 000~099
// 千位上额外加 : 3 0 000~583 //当前来讨论temp的最低位作为d的时候的可能数
//其左边的数有多少
left=temp/10;
//当前讨论的位置上的数值为多少
cur=temp%10;
if(d==0){
left--;
}
//先讨论无论是cur>d,<d,=d都会有的情况，即所有类型情况都包含当cur<d时的讨论,但是cur==d或者cur>d又都有自己的单独讨论
ans+=left*right;
//接着讨论如果cur=d或者cur>d的情况
if(cur>d){
ans+=right;
} else if (cur==d) {
ans+=num%right+1;
}
}
return ans;
}
}6、数字1的个数
题目描述： 给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13 输出：6
示例 2：
输入：n = 0 输出：0
提示：
0 <= n <= 109
解题思路：
这个题和4、[范围内的数字计数](https://leetcode.cn/problems/digit-count-in-range/) 题的思路一致
只不过这个题将d给定为了1，并且范围为1-n
代码如下
package main.java.class085;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code06_DigitCount3
* @description: 数字1的个数
* // 给定一个整数n
* // 计算所有小于等于n的非负整数中数字1出现的个数
* // 测试链接 : https://leetcode.cn/problems/number-of-digit-one/
* @author: zs宝
* @create: 2025-10-15 11:39
* @Version 1.0
**/public class Code06_DigitCount3 {
class Solution {
public int countDigitOne(int n) {
return digitsCount(1,n);
}
public static int digitsCount(int d, int b) {
return count(b, d) ;
}
// 统计1~num范围上所有的数中，数码d出现了多少次
// 注意是1~num范围，不是0~num范围
public static int count(int num, int d) {
int ans=0;
for(int right=1,temp=num,left,cur;temp!=0;right*=10,temp/=10){
// 情况1：
// d != 0
// 1 ~ 30583 , d = 5 // cur < d的情况
// 个位cur=3 : 0000~3057 5
// 个位上没有额外加
//
// cur > d的情况
// 十位cur=8 : 000~304 5 0~9
// 十位上额外加 : 305 5 0~9 // // cur == d的情况
// 百位cur=5 : 00~29 5 00~99
// 百位上额外加 : 30 5 00~83 // ... // 情况2：
// d == 0
// 1 ~ 30583 d = 0 // cur > d的情况
// 个位cur=3 : 0001~3057 0
// 个位上额外加 : 3058 0 // // cur > d的情况
// 十位cur=8 : 001~304 0 0~9
// 十位上额外加 : 305 0 0~9 // // cur > d的情况
// 百位cur=5 : 01~29 0 00~99
// 百位上额外加 : 30 0 00~99 // // cur == d的情况
// 千位cur=0 : 1~2 0 000~099
// 千位上额外加 : 3 0 000~583 //当前来讨论temp的最低位作为d的时候的可能数
//其左边的数有多少
left=temp/10;
//当前讨论的位置上的数值为多少
cur=temp%10;
if(d==0){
left--;
}
//先讨论无论是cur>d,<d,=d都会有的情况，即所有类型情况都包含当cur<d时的讨论,但是cur==d或者cur>d又都有自己的单独讨论
ans+=left*right;
//接着讨论如果cur=d或者cur>d的情况
if(cur>d){
ans+=right;
} else if (cur==d) {
ans+=num%right+1;
}
}
return ans;
}
}
}