2026-05-07：给定范围内平衡整数的数目。用go语言，给定两个整数 low 和 high，统计在闭区间 [low, high] 内满足“平衡”条件的整数个数。
对某个整数，先要求它至少是两位数。接着把它的每一位数字按位置从左到右编号，最左边是第 1 位。将所有在奇数位上的数字相加，得到奇数位数字和；再把所有在偶数位上的数字相加，得到偶数位数字和。如果这两个和相等，则该整数被称为“平衡整数”。
最终，你需要返回区间 [low, high] 中所有平衡整数的数量。
1 <= low <= high <= 1000000000000000。
输入： low = 1, high = 100。
输出： 9。
解释：
1 到 100 之间共有 9 个平衡数，分别是 11、22、33、44、55、66、77、88 和 99。
题目来自力扣3791。
平衡整数计数代码执行过程分步详解 一、代码整体执行步骤（分阶段） 阶段1：基础边界过滤
1. 函数接收
low和high两个超大整数（int64类型）；2. 首先判断：如果
high < 11，直接返回0（因为最小的平衡数是11，没有符合条件的数）；3. 把
low修正为max(low, 11)，排除1-10这些无效数字，缩小计算范围。
1. 将修正后的
low和high转换成字符串：
• 目的：方便逐位处理每一位数字（数位DP的核心操作）；
2. 计算high的字符串长度n（最大数字的位数）：
• 示例中high=100，字符串是
"100"，长度n=3；
3. 计算diffLH：high的位数 -low的位数，用于后续限制低位数字的枚举范围；
4.初始化记忆化数组（memo）：
• 二维数组：第一维是当前处理到第几位（0~n-1），第二维是奇偶位差值的存储位；
• 作用：缓存已经计算过的状态，避免重复递归，大幅提升效率。
定义递归函数dfs，这是数位DP的核心，参数含义：
•
i：当前正在处理第i位数字（从0开始，对应数字的最高位）；•
diff：奇数位和 - 偶数位和的差值（最终diff=0就是平衡数）；•
limitLow：布尔值，当前位是否受low的下限约束；•
limitHigh：布尔值，当前位是否受high的上限约束。
递归执行流程：
子步骤1：递归终止条件
当i == n（所有位数处理完毕）：
• 判断
diff是否等于0：• 等于0 → 是平衡数，返回1（计数+1）；
• 不等于0 → 不是平衡数，返回0。
如果当前不受low和high的数字限制（可以自由枚举0-9）：
1. 计算记忆数组的下标（将差值偏移为非负数，防止数组越界）；
2. 如果该状态已经计算过 → 直接返回缓存的结果，不重复计算；
3. 如果没计算过 → defer延迟存储结果，计算完成后写入缓存。
根据limitLow和limitHigh，限制当前位能选的数字：
• 下限
lo：受约束时=low对应位的数字，不受约束时=0；• 上限
hi：受约束时=high对应位的数字，不受约束时=9；• 示例：处理100的百位时，hi只能是1，不能超过high的数字。
循环遍历从lo到hi的每一个数字d：
1.更新差值diff：
• 第
i位是奇数位（i%2=0）：diff = diff + d；• 第
i位是偶数位（i%2=1）：diff = diff - d；
2.更新约束条件：
• 下一位的
limitLow= 当前约束 且 当前选的数字=下限；• 下一位的
limitHigh= 当前约束 且 当前选的数字=上限；
3. 递归调用下一位，累加所有合法结果。
子步骤5：返回累计结果
将当前位所有枚举情况的结果求和，返回给上一层递归。
阶段4：返回最终答案
启动递归dfs(0, 0, true, true)（从第0位开始，初始差值为0，同时受low和high约束），函数返回的就是[low, high]内平衡整数的总数量。
二、针对示例输入的执行验证
输入：low=1，high=100
1. 过滤：high=100≥11，low修正为11；
2. 格式化：low="11"（2位），high="100"（3位），n=3；
3. 递归枚举所有11~100的两位数、三位数：
• 两位数（11~99）：奇数位=十位，偶数位=个位，十位=个位 → 11、22…99，共9个；
• 三位数（100）：奇数位（百位+个位）=1+0=1，偶数位（十位）=0，1≠0 → 不合法；
4. 最终结果=9，与题目输出一致。
三、时间复杂度 & 额外空间复杂度 1. 时间复杂度
O(位数 × 最大差值 × 10)
• 核心变量：
1. 数字最大位数
n：10¹⁵对应15位；2. 奇偶位最大差值：每位最大9，总差值≤15×9=135；
3. 每位枚举数字：0~9共10种选择；
• 总计算量：15 × 135 × 10 =20250（常数级极小计算量）；
• 本质：O(1) 常数时间复杂度（因为位数固定最大15，无变量级增长）。
2. 额外空间复杂度
O(位数 × 最大差值)
• 核心占用：记忆化数组memo；
• 大小：15（位数） × 135（最大差值）=2025个int64元素；
• 递归栈空间：最大深度=数字位数=15，可忽略；
• 本质：O(1) 常数空间复杂度。
1. 代码核心是数位DP+记忆化递归，专门解决超大范围数字的数位统计问题；
2. 执行流程：边界过滤→数字格式化→记忆化DFS逐位枚举→统计合法平衡数；
3. 时间复杂度：O(1)（常数级）；
4. 额外空间复杂度：O(1)（常数级）。
package main
import (
"fmt"
"strconv"
)
func countBalanced(low, high int64)int64 {
// 最小的满足要求的数是 11
if high < 11 {
return0
}
low = max(low, 11)
lowS := strconv.FormatInt(low, 10)
highS := strconv.FormatInt(high, 10)
n := len(highS)
diffLH := n - len(lowS)
memo := make([][]int64, n)
for i := range memo {
// diff 至少 floor(n/2) * 9，至多 ceil(n/2) * 9，值域大小 n * 9
memo[i] = make([]int64, n*9+1)
}
var dfs func(int, int, bool, bool)int64
dfs = func(i, diff int, limitLow, limitHigh bool) (res int64) {
if i == n {
if diff != 0 { // 不合法
return0
}
return1
}
if !limitLow && !limitHigh {
p := &memo[i][diff+n/2*9] // 保证下标非负
if *p > 0 {
return *p - 1
}
deferfunc() { *p = res + 1 }() // 记忆化的时候加一，这样 memo 可以初始化成 0
}
lo := 0
if limitLow && i >= diffLH {
lo = int(lowS[i-diffLH] - '0')
}
hi := 9
if limitHigh {
hi = int(highS[i] - '0')
}
for d := lo; d <= hi; d++ {
// 下一个位置奇偶性翻转
res += dfs(i+1, diff+(1-i%2*2)*d,
limitLow && d == lo, limitHigh && d == hi)
}
return
}
return dfs(0, 0, true, true)
}func main() {
low := int64(1)
high := int64(100)
result := countBalanced(low, high)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def count_balanced(low: int, high: int) -> int:
if high < 11:
return0
low = max(low, 11)
low_str = str(low)
high_str = str(high)
n = len(high_str)
diff_lh = n - len(low_str)
# 记忆化数组：memo[i][diff_offset]
# diff 的取值范围：[-max_diff, max_diff]，max_diff = (n // 2 + (n % 2)) * 9
max_possible_diff = ((n + 1) // 2) * 9
memo = [[-1] * (2 * max_possible_diff + 1) for _ in range(n)]
def dfs(i: int, diff: int, limit_low: bool, limit_high: bool) -> int:
if i == n:
return1if diff == 0else0
# 记忆化：只有当不受 low 和 high 限制时才能复用
if not limit_low and not limit_high:
idx = diff + max_possible_diff
if memo[i][idx] != -1:
return memo[i][idx]
lo = 0
if limit_low and i >= diff_lh:
lo = int(low_str[i - diff_lh])
hi = 9
if limit_high:
hi = int(high_str[i])
total = 0
for d in range(lo, hi + 1):
# 根据位置 i 的奇偶性决定 diff 的增减
# i=0 是最高位（视为偶数位，与 Go 版本一致）
sign = 1if i % 2 == 0else-1
total += dfs(i + 1, diff + sign * d,
limit_low and d == lo,
limit_high and d == hi)
if not limit_low and not limit_high:
memo[i][diff + max_possible_diff] = total
return total
return dfs(0, 0, True, True)if __name__ == "__main__":
low_val = 1
high_val = 100
result = count_balanced(low_val, high_val)
print(result)
C++完整代码如下：
using namespace std;
long long countBalanced(long long low, long long high) {
// 最小的满足要求的数是 11
if (high < 11) {
return0;
}
low = max(low, 11LL);
string lowS = to_string(low);
string highS = to_string(high);
int n = highS.length();
int diffLH = n - lowS.length();
// 初始化记忆化数组，使用 -1 表示未计算
vector > memo(n, vector (n * 9 + 1, -1));// 使用函数对象实现递归
function int , int , bool , bool )> dfs = [&]( int i, int diff, bool limitLow, bool limitHigh) -> long long {
if (i == n) {
return diff == 0 ? 1 : 0 ;
}
if (!limitLow && !limitHigh) {
int idx = diff + n / 2 * 9 ;
if (idx >= 0 && idx < n * 9 + 1 && memo[i][idx] != -1 ) {
return memo[i][idx];
}
}
int lo = 0 ;
if (limitLow && i >= diffLH) {
lo = lowS[i - diffLH] - '0' ;
}
int hi = 9 ;
if (limitHigh) {
hi = highS[i] - '0' ;
}
long long res = 0 ;
for ( int d = lo; d <= hi; d++) {
// 下一个位置奇偶性翻转
res += dfs(i + 1 , diff + ( 1 - i % 2 * 2 ) * d,
limitLow && d == lo, limitHigh && d == hi);
}
if (!limitLow && !limitHigh) {
int idx = diff + n / 2 * 9 ;
if (idx >= 0 && idx < n * 9 + 1 ) {
memo[i][idx] = res;
}
}
return res;
};
return dfs( 0 , 0 , true , true );
}
int main() {
long long low = 1 ;
long long high = 100 ;
long long result = countBalanced(low, high);
cout << result << endl;
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴