2026-09-24：统计范围内的好整数。用go语言，有三个整数 l、r、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完整代码如下：

package main

 import (
    "fmt"
    "strconv"
)

 func goodIntegers(l, r int64, k int)int64 {
    lowS := strconv.FormatInt(l, 10)
    highS := strconv.FormatInt(r, 10)
    n := len(highS)
    diffLH := n - len(lowS)
    memo := make([][10]int64, n)
    for i := range memo {
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

     var dfs func(int, int, bool, bool)int64
    dfs = func(i, pre int, limitLow, limitHigh bool) (res int64) {
        if i == n {
            return1// 找到一个好数
        }
        if !limitLow && !limitHigh {
            p := &memo[i][pre]
            if *p >= 0 {
                return *p
            }
            deferfunc() { *p = res }()
        }

         lo := 0
        if limitLow && i >= diffLH {
            lo = int(lowS[i-diffLH] - '0')
        }
        hi := 9
        if limitHigh {
            hi = int(highS[i] - '0')
        }

         d := lo
        if limitLow && i < diffLH {
            // 不填数字，上界不受约束
            res = dfs(i+1, 0, true, false)
            d = 1// 下面填数字，从 1 开始填
        }

         // 如果在 diffLH 之前填过数字，那么 limitLow 一定是 false
        isFirst := limitLow && i <= diffLH
        for ; d <= hi; d++ {
            if isFirst || abs(d-pre) <= k {
                res += dfs(i+1, d, limitLow && d == lo, limitHigh && d == hi)
            }
        }
        return
    }

     // pre 的初始值随意
    return dfs(0, 0, true, true)
}

 func abs(x int)int {
    if x < 0 {
        return -x
    }
    return x
}

 func main() {
    l := int64(10)
    r := int64(15)
    k := 1
    result := goodIntegers(l, r, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def good_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 _ in range(n)]

     def dfs(i, pre, limit_low, limit_high):
        if i == n:
            return1

         if not limit_low and not limit_high:
            if memo[i][pre] >= 0:
                return memo[i][pre]

         res = 0

         lo = 0
        if limit_low and i >= diff_lh:
            lo = int(low_s[i - diff_lh])

         hi = 9
        if limit_high:
            hi = int(high_s[i])

         d = lo
        # 如果还在补前导零阶段，可以选择继续不填数字
        if limit_low and i < diff_lh:
            res = dfs(i + 1, 0, True, False)
            d = 1  # 接下来如果填数字，从 1 开始

         is_first = limit_low and i <= diff_lh

         while d <= hi:
            if is_first or abs(d - pre) <= k:
                res += dfs(
                    i + 1,
                    d,
                    limit_low and d == lo,
                    limit_high and d == hi
                )
            d += 1

         if not limit_low and not limit_high:
            memo[i][pre] = res

         return res

     return dfs(0, 0, True, True)

 if __name__ == "__main__":
    l = 10
    r = 15
    k = 1
    print(good_integers(l, r, k))

C++完整代码如下：

  

  

  

  


 using namespace std;

 long long goodIntegers(long long l, long long r, int k) {
    string lowS = to_string(l);
    string highS = to_string(r);
    int n = highS.size();
    int diffLH = n - lowS.size();
    vector 
 
 > memo(n, vector 
 
 ( 
 
 10, -1));

     function 
 
 int 
 ,  
 int 
 ,  
 bool 
 ,  
 bool 
 )> dfs = [&]( 
 int 
  i,  
 int 
  pre,  
 bool 
  limitLow,  
 bool 
  limitHigh) -> long long { 
 
 
          
 if 
  (i == n) { 
 
 
              
 return 
 1 
 ;  
 // 找到一个好数 
 
 
         } 
 
 
          
 if 
  (!limitLow && !limitHigh) { 
 
 
              
 if 
  (memo[i][pre] >=  
 0 
 ) { 
 
 
                  
 return 
  memo[i][pre]; 
 
 
             } 
 
 
         } 
 
 
 
 
         long long res =  
 0 
 ; 
 
 
 
 
          
 int 
  lo =  
 0 
 ; 
 
 
          
 if 
  (limitLow && i >= diffLH) { 
 
 
             lo = lowS[i - diffLH] -  
 '0' 
 ; 
 
 
         } 
 
 
          
 int 
  hi =  
 9 
 ; 
 
 
          
 if 
  (limitHigh) { 
 
 
             hi = highS[i] -  
 '0' 
 ; 
 
 
         } 
 
 
 
 
          
 int 
  d = lo; 
 
 
          
 if 
  (limitLow && i < diffLH) { 
 
 
              
 // 不填数字，上界不受约束 
 
 
             res = dfs(i +  
 1 
 ,  
 0 
 ,  
 true 
 ,  
 false 
 ); 
 
 
             d =  
 1 
 ;  
 // 下面填数字，从 1 开始填 
 
 
         } 
 
 
 
 
          
 bool 
  isFirst = 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; 
 
 
         } 
 
 
          
 return 
  res; 
 
 
     }; 
 
 
 
 
      
 return 
  dfs( 
 0 
 ,  
 0 
 ,  
 true 
 ,  
 true 
 ); 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     long long l =  
 10 
 ; 
 
 
     long long r =  
 15 
 ; 
 
 
      
 int 
  k =  
 1 
 ; 
 
 
     long long result = goodIntegers(l, r, k); 
 
 
     cout << result << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。