北京pk10官网 2026-05-07: 给定界限内均衡整数的数量。用go言语, 给定两个整数
2026-05-07：给定界限内均衡整数的数量。用go言语，给定两个整数 low 和 high，统计在闭区间 [low， high] 内痛快“均衡”条目的整数个数。
对某个整数，先要求它至少是两位数。接着把它的每一位数字按位置从左到右编号，最左边是第 1 位。将通盘在奇数位上的数字相加，得到奇数位数字和；再把通盘在偶数位上的数字相加，得到偶数位数字和。若是这两个和很是，则该整数被称为“均衡整数”。
最终，你需要复返区间 [low， high] 中通盘均衡整数的数量。
1
输入： 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
3. 把low修正为max(low， 11)，抹杀1-10这些无效数字，削弱计较界限。
阶段2：数字体式化与预处理
1. 将修正后的low和high调度成字符串：
• 目的：便捷逐位处理每一位数字（数位DP的中枢操作）；
2. 计较high的字符串长度n（最大数字的位数）：
• 示例中high=100，字符串是"100"，长度n=3；
3. 计较diffLH：high的位数 - low的位数，用于后续截止低位数字的罗列界限；
4. 动手化挂念化数组（memo）：
• 二维数组：第一维是现时处理到第几位（0~n-1），第二维是奇偶位差值的存储位；
• 作用：缓存一经计较过的景色，幸免类似递归，大幅进步成果。
阶段3：中枢逻辑 —— 数位DFS递归（深度优先搜索）
界说递归函数dfs，这是数位DP的中枢，参数含义：
• i：现时正在处理第i位数字（从0动手，对应数字的最高位）；
• diff：奇数位和 - 偶数位和的差值（最终diff=0等于均衡数）；
• limitLow：布尔值，现时位是否受low的下限敛迹；
• limitHigh：布尔值，现时位是否受high的上限敛迹。
递归履行过程：
子体式1：递归隔断条目
当i == n（通盘位数处理结束）：
• 判断diff是否等于0：
等于0 → 是均衡数，复返1（计数+1）；
不等于0 → 不是均衡数，复返0。
子体式2：挂念化缓存读取
若是现时不受low和high的数字截止（不错目田罗列0-9）：
1. 计较挂念数组的下标（将差值偏移为非负数，堤防数组越界）；
2. 若是该景色一经计较过 → 径直复返缓存的结果，不类似计较；
3. 若是没计较过 → defer延长存储结果，计较完成后写入缓存。
子体式3：笃定现时位的罗列界限
说明limitLow和limitHigh，截止现时位能选的数字：
• 下限lo：受敛迹时=low对应位的数字，不受敛迹时=0；
• 上限hi：受敛迹时=high对应位的数字，不受敛迹时=9；
• 示例：处理100的百位时，pk10官网hi只但是1，不成进步high的数字。
子体式4：罗列现时位的通盘正当数字
轮回遍历从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)（常数级）。
Go圆善代码如下：
package main
import (
"fmt"
"strconv"
)
func countBalanced(low， high int64)int64 {
// 最小的痛快要求的数是 11
if high
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
// 下一个位置奇偶性翻转
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
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++圆善代码如下：
#include
#include
#include
#include
#include
#include
using namespace std;
long long countBalanced(long long low， long long high) {
// 最小的痛快要求的数是 11
if (high
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 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
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
// 下一个位置奇偶性翻转
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
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
return0;
}
咱们确信东谈主工智能为鄙俗东谈主提供了一种“增强器具”，并努力于于共享全方向的AI学问。在这里，您不错找到最新的AI科普著述、器具评测、进步成果的阴私以及行业瞻念察。
迎接神志“福大大架构师逐日一题”，发音问可得到口试资料北京pk10官网，让AI助力您的已往发展。
开云·体育中国官方网站
备案号: