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。
准备一个二维记忆化数组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开始。
用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助力您的未来发展。
热门跟贴