2026-09-24：统计范围内的好整数。用go语言，有三个整数 l、r、k。 对于一个整数，把它写成十进制形式后，如果任意两个挨着的数字之间的差的绝对值都不超过 k，就认为这个整数满足条件。

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。

对于 10，abs(1 - 0) = 1。

对于 11，abs(1 - 1) = 0。

对于 12，abs(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 = 10，lowS = "10"；
  • r = 15，highS = "15"；
  • n = 2；
  • diffLH = 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前面的零。

此时有两种选择：

  1. 继续不填有效数字

    也就是当前位仍然保持前导零，相当于跳过这一位。

    递归到下一位置，前一位记为0，下界仍然受限制，但上界不再受限制，因为最高位填了0，一定小于r的最高位。

    这个分支直接累加到结果中。

  2. 从当前位开始填有效数字 既然开始填有效数字，就不能填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 = 10，r = 15，k = 1；
  • 好整数有10、11、12；
  • 因为：
    • 10：abs(1 - 0) = 1；
    • 11：abs(1 - 1) = 0；
    • 12：abs(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("fmt""strconv")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)int64dfs=func(i,preint,limitLow,limitHighbool)(resint64){ifi==n{return1// 找到一个好数}if!limitLow&&!limitHigh{p:=&memo[i][pre]if*p>=0{return*p}deferfunc(){*p=res}()}lo:=0iflimitLow&&i>=diffLH{lo=int(lowS[i-diffLH]-'0')}hi:=9iflimitHigh{hi=int(highS[i]-'0')}d:=loiflimitLow&&i<diffLH{// 不填数字，上界不受约束res=dfs(i+1,0,true,false)d=1// 下面填数字，从 1 开始填}// 如果在 diffLH 之前填过数字，那么 limitLow 一定是 falseisFirst:=limitLow&&i<=diffLHfor;d<=hi;d++{ifisFirst||abs(d-pre)<=k{res+=dfs(i+1,d,limitLow&&d==lo,limitHigh&&d==hi)}}return}// pre 的初始值随意returndfs(0,0,true,true)}funcabs(xint)int{ifx<0{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_s=str(l)high_s=str(r)n=len(high_s)diff_lh=n-len(low_s)# memo[i][pre] 表示在位置 i，前一位数字为 pre，且不受上下界限制时的结果memo=[[-1]*10for_inrange(n)]defdfs(i,pre,limit_low,limit_high):ifi==n:return1ifnotlimit_lowandnotlimit_high:ifmemo[i][pre]>=0:returnmemo[i][pre]res=0lo=0iflimit_lowandi>=diff_lh:lo=int(low_s[i-diff_lh])hi=9iflimit_high:hi=int(high_s[i])d=lo# 如果还在补前导零阶段，可以选择继续不填数字iflimit_lowandi<diff_lh:res=dfs(i+1,0,True,False)d=1# 接下来如果填数字，从 1 开始is_first=limit_lowandi<=diff_lhwhiled<=hi:ifis_firstorabs(d-pre)<=k:res+=dfs(i+1,d,limit_lowandd==lo,limit_highandd==hi)d+=1ifnotlimit_lowandnotlimit_high:memo[i][pre]=resreturnresreturndfs(0,0,True,True)if__name__=="__main__":l=10r=15k=1print(good_integers(l,r,k))

C++完整代码如下：

#include#include#include#include#includeusingnamespacestd;longlonggoodIntegers(longlongl,longlongr,intk){string lowS=to_string(l);string highS=to_string(r);intn=highS.size();intdiffLH=n-lowS.size();vector<vector<longlong>>memo(n,vector<longlong>(10,-1));function<longlong(int,int,bool,bool)>dfs=[&](inti,intpre,boollimitLow,boollimitHigh)->longlong{if(i==n){return1;// 找到一个好数}if(!limitLow&&!limitHigh){if(memo[i][pre]>=0){returnmemo[i][pre];}}longlongres=0;intlo=0;if(limitLow&&i>=diffLH){lo=lowS[i-diffLH]-'0';}inthi=9;if(limitHigh){hi=highS[i]-'0';}intd=lo;if(limitLow&&i<diffLH){// 不填数字，上界不受约束res=dfs(i+1,0,true,false);d=1;// 下面填数字，从 1 开始填}boolisFirst=limitLow&&i<=diffLH;for(;d<=hi;++d){if(isFirst||abs(d-pre)<=k){res+=dfs(i+1,d,limitLow&&d==lo,limitHigh&&d==hi);}}if(!limitLow&&!limitHigh){memo[i][pre]=res;}returnres;};returndfs(0,0,true,true);}intmain(){longlongl=10;longlongr=15;intk=1;longlongresult=goodIntegers(l,r,k);cout<<result<<endl;return0;}