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基础边界过滤函数接收low和high两个超大整数int64类型首先判断如果high 11直接返回0因为最小的平衡数是11没有符合条件的数把low修正为max(low, 11)排除1-10这些无效数字缩小计算范围。阶段2数字格式化与预处理将修正后的low和high转换成字符串目的方便逐位处理每一位数字数位DP的核心操作计算high的字符串长度n最大数字的位数示例中high100字符串是100长度n3计算diffLHhigh的位数 -low的位数用于后续限制低位数字的枚举范围初始化记忆化数组memo二维数组第一维是当前处理到第几位0~n-1第二维是奇偶位差值的存储位作用缓存已经计算过的状态避免重复递归大幅提升效率。阶段3核心逻辑 —— 数位DFS递归深度优先搜索定义递归函数dfs这是数位DP的核心参数含义i当前正在处理第i位数字从0开始对应数字的最高位diff奇数位和 - 偶数位和的差值最终diff0就是平衡数limitLow布尔值当前位是否受low的下限约束limitHigh布尔值当前位是否受high的上限约束。递归执行流程子步骤1递归终止条件当i n所有位数处理完毕判断diff是否等于0等于0 → 是平衡数返回1计数1不等于0 → 不是平衡数返回0。子步骤2记忆化缓存读取如果当前不受low和high的数字限制可以自由枚举0-9计算记忆数组的下标将差值偏移为非负数防止数组越界如果该状态已经计算过 → 直接返回缓存的结果不重复计算如果没计算过 → defer延迟存储结果计算完成后写入缓存。子步骤3确定当前位的枚举范围根据limitLow和limitHigh限制当前位能选的数字下限lo受约束时low对应位的数字不受约束时0上限hi受约束时high对应位的数字不受约束时9示例处理100的百位时hi只能是1不能超过high的数字。子步骤4枚举当前位的所有合法数字循环遍历从lo到hi的每一个数字d更新差值diff第i位是奇数位i%20diff diff d第i位是偶数位i%21diff diff - d更新约束条件下一位的limitLow 当前约束 且 当前选的数字下限下一位的limitHigh 当前约束 且 当前选的数字上限递归调用下一位累加所有合法结果。子步骤5返回累计结果将当前位所有枚举情况的结果求和返回给上一层递归。阶段4返回最终答案启动递归dfs(0, 0, true, true)从第0位开始初始差值为0同时受low和high约束函数返回的就是[low, high]内平衡整数的总数量。二、针对示例输入的执行验证输入low1high100过滤high100≥11low修正为11格式化low“11”2位high“100”3位n3递归枚举所有11~100的两位数、三位数两位数11~99奇数位十位偶数位个位十位个位 → 11、22…99共9个三位数100奇数位百位个位101偶数位十位01≠0 → 不合法最终结果9与题目输出一致。三、时间复杂度 额外空间复杂度1. 时间复杂度O(位数 × 最大差值 × 10)核心变量数字最大位数n10¹⁵对应15位奇偶位最大差值每位最大9总差值≤15×9135每位枚举数字0~9共10种选择总计算量15 × 135 × 10 20250常数级极小计算量本质O(1) 常数时间复杂度因为位数固定最大15无变量级增长。2. 额外空间复杂度O(位数 × 最大差值)核心占用记忆化数组memo大小15位数 × 135最大差值2025个int64元素递归栈空间最大深度数字位数15可忽略本质O(1) 常数空间复杂度。总结代码核心是数位DP记忆化递归专门解决超大范围数字的数位统计问题执行流程边界过滤→数字格式化→记忆化DFS逐位枚举→统计合法平衡数时间复杂度O(1)常数级额外空间复杂度O(1)常数级。Go完整代码如下packagemainimport(fmtstrconv)funccountBalanced(low,highint64)int64{// 最小的满足要求的数是 11ifhigh11{return0}lowmax(low,11)lowS:strconv.FormatInt(low,10)highS:strconv.FormatInt(high,10)n:len(highS)diffLH:n-len(lowS)memo:make([][]int64,n)fori:rangememo{// diff 至少 floor(n/2) * 9至多 ceil(n/2) * 9值域大小 n * 9memo[i]make([]int64,n*91)}vardfsfunc(int,int,bool,bool)int64dfsfunc(i,diffint,limitLow,limitHighbool)(resint64){ifin{ifdiff!0{// 不合法return0}return1}if!limitLow!limitHigh{p:memo[i][diffn/2*9]// 保证下标非负if*p0{return*p-1}deferfunc(){*pres1}()// 记忆化的时候加一这样 memo 可以初始化成 0}lo:0iflimitLowidiffLH{loint(lowS[i-diffLH]-0)}hi:9iflimitHigh{hiint(highS[i]-0)}ford:lo;dhi;d{// 下一个位置奇偶性翻转resdfs(i1,diff(1-i%2*2)*d,limitLowdlo,limitHighdhi)}return}returndfs(0,0,true,true)}funcmain(){low:int64(1)high:int64(100)result:countBalanced(low,high)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defcount_balanced(low:int,high:int)-int:ifhigh11:return0lowmax(low,11)low_strstr(low)high_strstr(high)nlen(high_str)diff_lhn-len(low_str)# 记忆化数组memo[i][diff_offset]# diff 的取值范围[-max_diff, max_diff]max_diff (n // 2 (n % 2)) * 9max_possible_diff((n1)//2)*9memo[[-1]*(2*max_possible_diff1)for_inrange(n)]defdfs(i:int,diff:int,limit_low:bool,limit_high:bool)-int:ifin:return1ifdiff0else0# 记忆化只有当不受 low 和 high 限制时才能复用ifnotlimit_lowandnotlimit_high:idxdiffmax_possible_diffifmemo[i][idx]!-1:returnmemo[i][idx]lo0iflimit_lowandidiff_lh:loint(low_str[i-diff_lh])hi9iflimit_high:hiint(high_str[i])total0fordinrange(lo,hi1):# 根据位置 i 的奇偶性决定 diff 的增减# i0 是最高位视为偶数位与 Go 版本一致sign1ifi%20else-1totaldfs(i1,diffsign*d,limit_lowanddlo,limit_highanddhi)ifnotlimit_lowandnotlimit_high:memo[i][diffmax_possible_diff]totalreturntotalreturndfs(0,0,True,True)if__name____main__:low_val1high_val100resultcount_balanced(low_val,high_val)print(result)C完整代码如下#includeiostream#includestring#includevector#includefunctional#includealgorithm#includecstringusingnamespacestd;longlongcountBalanced(longlonglow,longlonghigh){// 最小的满足要求的数是 11if(high11){return0;}lowmax(low,11LL);string lowSto_string(low);string highSto_string(high);intnhighS.length();intdiffLHn-lowS.length();// 初始化记忆化数组使用 -1 表示未计算vectorvectorlonglongmemo(n,vectorlonglong(n*91,-1));// 使用函数对象实现递归functionlonglong(int,int,bool,bool)dfs[](inti,intdiff,boollimitLow,boollimitHigh)-longlong{if(in){returndiff0?1:0;}if(!limitLow!limitHigh){intidxdiffn/2*9;if(idx0idxn*91memo[i][idx]!-1){returnmemo[i][idx];}}intlo0;if(limitLowidiffLH){lolowS[i-diffLH]-0;}inthi9;if(limitHigh){hihighS[i]-0;}longlongres0;for(intdlo;dhi;d){// 下一个位置奇偶性翻转resdfs(i1,diff(1-i%2*2)*d,limitLowdlo,limitHighdhi);}if(!limitLow!limitHigh){intidxdiffn/2*9;if(idx0idxn*91){memo[i][idx]res;}}returnres;};returndfs(0,0,true,true);}intmain(){longlonglow1;longlonghigh100;longlongresultcountBalanced(low,high);coutresultendl;return0;}