Kimi LeetCode 3791. 给定范围内平衡整数的数目 Java实现
以下是 LeetCode 3791. 给定范围内平衡整数的数目 的 Java 实现。
题目理解
一个整数是平衡的，当且仅当：
1. 至少包含两位数字
2. 奇数位数字之和等于偶数位数字之和（最左边数字位置为1）
例如：`121` 是平衡的（奇数位 1+1=2，偶数位 2=2），而 `1234` 不是（奇数位 1+3=4，偶数位 2+4=6）。
约束：`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 实现
```java
class Solution {
private char[] num;
private Long[][] f;
private final int base = 90;
public long countBalanced(long low, long high) {
// 如果 high < 11，范围内没有至少两位的数，直接返回0
if (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%2==0）加 i，偶数位（pos%2==1）减 i
res += 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 = high`，`D = 10`
- 空间复杂度：`O(log² M × D)`，主要是记忆化数组的空间
关键要点
1. base 偏移：差值 `diff` 可能为负数，用 `base = 90` 做偏移，使数组下标非负
2. pos 的奇偶性：`pos % 2 == 0` 对应第1、3、5...位（奇数位，从1开始计数），加 `i`；否则减 `i`
3. 边界处理：`low < 11` 时调整为11，因为单个数字不可能平衡
4. 记忆化数组：`Long[][]` 用 `null` 判断是否已计算，避免重复搜索
参考来源：