以下是 LeetCode 3791. 给定范围内平衡整数的数目 的 Java 实现。题目理解一个整数是平衡的当且仅当1. 至少包含两位数字2. 奇数位数字之和等于偶数位数字之和最左边数字位置为1例如121 是平衡的奇数位 112偶数位 22而 1234 不是奇数位 134偶数位 246。约束1 low high 10^15直接暴力枚举不可行需要使用数位 DP。解题思路核心思想计算 [1, high] 中平衡整数的个数减去 [1, low-1] 中平衡整数的个数。数位 DP 状态定义dfs(pos, diff, lim)- pos当前处理到第几位- diff奇数位和减去偶数位和的差值- lim是否受上界限制base 90 作为偏移量因为最多15位每位最大9差值范围 [-90, 90]。Java 实现javaclass Solution {private char[] num;private Long[][] f;private final int base 90;public long countBalanced(long low, long high) {// 如果 high 11范围内没有至少两位的数直接返回0if (high 11) {return 0;}// low 至少要从11开始因为10不是平衡的11才是low Math.max(low, 11);// 计算 [1, low-1] 中平衡整数的个数num String.valueOf(low - 1).toCharArray();f new Long[num.length][base 1 | 1];long a dfs(0, 0, true);// 计算 [1, high] 中平衡整数的个数num String.valueOf(high).toCharArray();f new Long[num.length][base 1 | 1];long b dfs(0, 0, true);// 结果为两者的差return b - a;}private long dfs(int pos, int diff, boolean lim) {// 所有位处理完毕if (pos num.length) {return diff 0 ? 1 : 0;}// 记忆化不受限制时直接返回已计算的结果if (!lim f[pos][diff base] ! null) {return f[pos][diff base];}// 当前位能填的最大数字int up lim ? num[pos] - 0 : 9;long res 0;for (int i 0; i up; i) {// pos 从0开始对应第1位奇数位// 奇数位pos%20加 i偶数位pos%21减 ires dfs(pos 1, diff i * (pos % 2 0 ? 1 : -1), lim i up);}// 保存不受限制时的结果if (!lim) {f[pos][diff base] res;}return res;}}复杂度分析- 时间复杂度O(log² M × D²)其中 M highD 10- 空间复杂度O(log² M × D)主要是记忆化数组的空间关键要点1. base 偏移差值 diff 可能为负数用 base 90 做偏移使数组下标非负2. pos 的奇偶性pos % 2 0 对应第1、3、5...位奇数位从1开始计数加 i否则减 i3. 边界处理low 11 时调整为11因为单个数字不可能平衡4. 记忆化数组Long[][] 用 null 判断是否已计算避免重复搜索参考来源