2026-09-24统计范围内的好整数。用go语言有三个整数 l、r、k。对于一个整数把它写成十进制形式后如果任意两个挨着的数字之间的差的绝对值都不超过 k就认为这个整数满足条件。现在需要统计从 l 到 r 这个闭区间内包括 l 和 r一共有多少个满足条件的整数。其中两个数 x 和 y 的绝对差表示为 abs(x - y)。10 l r 1000000000000000。0 k 9。输入 l 10, r 15, k 1。输出 3。解释范围内的好整数有 10、11 和 12。对于 10abs(1 - 0) 1。对于 11abs(1 - 1) 0。对于 12abs(1 - 2) 1。所有这些差值都至多为 k 1。因此答案为 3。题目来自力扣3966。1. 把范围转成十进制字符串先把l和r转成十进制字符串lowS表示l的十进制形式highS表示r的十进制形式以highS的长度作为总位数n计算diffLH n - len(lowS)表示l比r少多少位。因为后面统一按r的位数来处理所以相当于在l的前面补上diffLH个前导零。例如l 10lowS 10r 15highS 15n 2diffLH 2 - 2 0。2. 定义记忆化数组准备一个二维记忆化数组memo第一维表示当前处理到第几位范围是0到n - 1第二维表示前一位数字范围是0到9初始值全部设为-1表示还没有计算过。它记录的是当当前位不受下界和上界限制时从第i位开始前一位数字为pre后面还能构造出多少个好数。3. 递归函数的含义递归函数大致有四个参数i当前正在处理第几位pre上一位已经填过的数字limitLow当前是否还受到下界l的限制limitHigh当前是否还受到上界r的限制。递归函数返回的是从第i位开始按照规则继续填数字最终能形成多少个好数。4. 递归终止条件如果i n说明所有位都已经处理完形成了一个完整的整数。这个整数一定在[l, r]范围内并且过程中已经检查过相邻数位差所以它是一个好数返回1。5. 记忆化查询与保存如果当前既不受下界限制也不受上界限制说明后面的数字可以自由选择只依赖于当前位数i前一位数字pre。这时先查memo[i][pre]如果已经计算过直接返回如果没有计算过就继续计算计算完后把结果保存到memo[i][pre]。这样避免重复计算相同状态。6. 确定当前位可选数字的上下界当前位能填哪些数字由下界和上界共同决定。下界lo默认下界是0。如果当前还受下界限制并且当前位已经到达l的有效位也就是i diffLH那么下界就取lowS中对应位置的数字对应下标是i - diffLH因为前面diffLH位是给l补的前导零。如果当前还在补前导零阶段即i diffLH那么下界仍然是0。上界hi默认上界是9。如果当前还受上界限制那么上界就是highS当前位的数字。7. 处理前导零和补位阶段如果当前还受下界限制并且当前位i diffLH说明还没有真正开始填有效数字还在补l前面的零。此时有两种选择继续不填有效数字也就是当前位仍然保持前导零相当于跳过这一位。递归到下一位置前一位记为0下界仍然受限制但上界不再受限制因为最高位填了0一定小于r的最高位。这个分支直接累加到结果中。从当前位开始填有效数字既然开始填有效数字就不能填0所以候选数字从1开始而不是从lo开始。8. 判断是否是第一位有效数字用isFirst表示当前是否正在填第一位有效数字。判断条件是当前还受下界限制并且当前位i diffLH。如果是第一位有效数字那么前面没有真正有效的相邻数字前导零不算相邻数位所以不需要检查abs(d - pre) k。如果不是第一位有效数字就必须检查当前要填的数字d和前一位数字pre的差的绝对值是否不超过k。9. 枚举当前位数字并递归当前位的候选数字从下界开始到上界结束。对于每一个候选数字d如果它是第一位有效数字直接允许否则检查abs(d - pre) k如果满足条件就递归处理下一位。递归时下一位的前一位数字变成d下界限制更新为原来是否受下界限制并且当前位是否正好等于下界lo上界限制更新为原来是否受上界限制并且当前位是否正好等于上界hi。把所有合法分支的结果累加起来就是当前状态的结果。10. 初始调用最开始从第0位开始前一位数字可以随便设为0同时既受下界限制也受上界限制。所以初始调用是位置0前一位0下界限制为真上界限制为真。最终返回的就是[l, r]范围内好整数的数量。例如题目样例l 10r 15k 1好整数有10、11、12因为10abs(1 - 0) 111abs(1 - 1) 012abs(1 - 2) 1其他数字如13、14、15的相邻差都超过1所以结果输出3。时间复杂度设n是r的十进制位数最大不超过16。递归状态主要由当前位数i最多n种前一位数字pre最多10种是否受下界限制最多2种是否受上界限制最多2种。但记忆化只在既不受下界限制也不受上界限制时生效因此实际记忆化状态是n × 10个。每个状态最多枚举当前位10个数字所以总计算量大约是O(n × 10 × 10) O(n)因为10 × 10是常数所以时间复杂度可以看作O(n)其中n是r的位数最大为16。额外空间复杂度额外空间主要来自记忆化数组memo大小是n × 10递归调用栈深度最多n层。所以总额外空间复杂度是O(n × 10 n) O(n × 10) O(n)同样因为n最大只有16实际空间非常小。Go完整代码如下packagemainimport(fmtstrconv)funcgoodIntegers(l,rint64,kint)int64{lowS:strconv.FormatInt(l,10)highS:strconv.FormatInt(r,10)n:len(highS)diffLH:n-len(lowS)memo:make([][10]int64,n)fori:rangememo{forj:rangememo[i]{memo[i][j]-1}}vardfsfunc(int,int,bool,bool)int64dfsfunc(i,preint,limitLow,limitHighbool)(resint64){ifin{return1// 找到一个好数}if!limitLow!limitHigh{p:memo[i][pre]if*p0{return*p}deferfunc(){*pres}()}lo:0iflimitLowidiffLH{loint(lowS[i-diffLH]-0)}hi:9iflimitHigh{hiint(highS[i]-0)}d:loiflimitLowidiffLH{// 不填数字上界不受约束resdfs(i1,0,true,false)d1// 下面填数字从 1 开始填}// 如果在 diffLH 之前填过数字那么 limitLow 一定是 falseisFirst:limitLowidiffLHfor;dhi;d{ifisFirst||abs(d-pre)k{resdfs(i1,d,limitLowdlo,limitHighdhi)}}return}// pre 的初始值随意returndfs(0,0,true,true)}funcabs(xint)int{ifx0{return-x}returnx}funcmain(){l:int64(10)r:int64(15)k:1result:goodIntegers(l,r,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defgood_integers(l,r,k):low_sstr(l)high_sstr(r)nlen(high_s)diff_lhn-len(low_s)# memo[i][pre] 表示在位置 i前一位数字为 pre且不受上下界限制时的结果memo[[-1]*10for_inrange(n)]defdfs(i,pre,limit_low,limit_high):ifin:return1ifnotlimit_lowandnotlimit_high:ifmemo[i][pre]0:returnmemo[i][pre]res0lo0iflimit_lowandidiff_lh:loint(low_s[i-diff_lh])hi9iflimit_high:hiint(high_s[i])dlo# 如果还在补前导零阶段可以选择继续不填数字iflimit_lowandidiff_lh:resdfs(i1,0,True,False)d1# 接下来如果填数字从 1 开始is_firstlimit_lowandidiff_lhwhiledhi:ifis_firstorabs(d-pre)k:resdfs(i1,d,limit_lowanddlo,limit_highanddhi)d1ifnotlimit_lowandnotlimit_high:memo[i][pre]resreturnresreturndfs(0,0,True,True)if__name____main__:l10r15k1print(good_integers(l,r,k))C完整代码如下#includeiostream#includestring#includevector#includefunctional#includecstdlibusingnamespacestd;longlonggoodIntegers(longlongl,longlongr,intk){string lowSto_string(l);string highSto_string(r);intnhighS.size();intdiffLHn-lowS.size();vectorvectorlonglongmemo(n,vectorlonglong(10,-1));functionlonglong(int,int,bool,bool)dfs[](inti,intpre,boollimitLow,boollimitHigh)-longlong{if(in){return1;// 找到一个好数}if(!limitLow!limitHigh){if(memo[i][pre]0){returnmemo[i][pre];}}longlongres0;intlo0;if(limitLowidiffLH){lolowS[i-diffLH]-0;}inthi9;if(limitHigh){hihighS[i]-0;}intdlo;if(limitLowidiffLH){// 不填数字上界不受约束resdfs(i1,0,true,false);d1;// 下面填数字从 1 开始填}boolisFirstlimitLowidiffLH;for(;dhi;d){if(isFirst||abs(d-pre)k){resdfs(i1,d,limitLowdlo,limitHighdhi);}}if(!limitLow!limitHigh){memo[i][pre]res;}returnres;};returndfs(0,0,true,true);}intmain(){longlongl10;longlongr15;intk1;longlongresultgoodIntegers(l,r,k);coutresultendl;return0;}