Kimi LeetCode 3791. 给定范围内平衡整数的数目 Python3实现
以下是 LeetCode 3791. 给定范围内平衡整数的数目 的 Python3 实现。
题目理解
一个整数是平衡的，当且仅当：
1. 至少包含两位数字
2. 奇数位数字之和等于偶数位数字之和（最左边数字位置为1）
约束：`1 <= low <= high <= 10^15`，需要使用数位 DP。
Python3 实现
```python
from functools import lru_cache
class Solution:
def countBalanced(self, low: int, high: int) -> int:
# 如果 high < 11，范围内没有至少两位的数，直接返回0
if high < 11:
return 0
# 计算 [0, x] 中平衡整数的个数
def calc(x: int) -> int:
s = str(x)
n = len(s)
@lru_cache(maxsize=None)
def dfs(pos: int, diff: int, is_limit: bool, is_num: bool) -> int:
# pos: 当前处理到的位置
# diff: 奇数位和 - 偶数位和
# is_limit: 是否受上界限制
# is_num: 是否已经填了非前导零的数字
if pos == n:
# 必须至少两位，且差值为0
return 1 if is_num and diff == 0 else 0
res = 0
up = int(s[pos]) if is_limit else 9
for d in range(up + 1):
if not is_num and d == 0:
# 前导零，继续跳过
res += dfs(pos + 1, diff, False, False)
else:
# 计算当前位的贡献
# pos 从0开始，对应第1位（奇数位）
if is_num:
# 已经有数字了，当前位根据 pos 的奇偶性
# pos 是字符串索引，已经填了前导零后的实际位置需要重新算
# 这里用 digit_count 记录已经填了多少位
pass # 下面用另一种更清晰的方式
return res
# 上面的写法不太对，换一种更清晰的
pass
# 重新写，不用 is_num，直接处理
def count(x: int) -> int:
s = str(x)
n = len(s)
@lru_cache(maxsize=None)
def dfs(pos: int, diff: int, is_limit: bool, started: bool, digit_count: int) -> int:
if pos == n:
# 必须已经开始（至少一位），且至少两位，且差值为0
return 1 if started and digit_count >= 2 and diff == 0 else 0
res = 0
up = int(s[pos]) if is_limit else 9
for d in range(up + 1):
if not started and d == 0:
# 还是前导零
res += dfs(pos + 1, diff, False, False, 0)
else:
# 当前是第 digit_count+1 位（从1开始计数）
new_count = digit_count + 1
# 奇数位加，偶数位减
new_diff = diff + d if new_count % 2 == 1 else diff - d
res += dfs(pos + 1, new_diff, is_limit and d == up, True, new_count)
return res
return dfs(0, 0, True, False, 0)
return count(high) - count(low - 1)
```
更简洁的版本（不带前导零处理，因为题目要求至少两位）
```python
from functools import lru_cache
class Solution:
def countBalanced(self, low: int, high: int) -> int:
def count(x: int) -> int:
if x < 11:
return 0
s = str(x)
n = len(s)
@lru_cache(maxsize=None)
def dfs(pos: int, diff: int, is_limit: bool) -> int:
# pos: 当前处理到的位置 (0-indexed)
# diff: 奇数位和 - 偶数位和
# is_limit: 是否受上界限制
if pos == n:
return 1 if diff == 0 else 0
res = 0
up = int(s[pos]) if is_limit else 9
for d in range(up + 1):
# pos 从0开始，对应第1位（奇数位）
# 奇数位（pos%2==0，即第1,3,5...位）加 d
# 偶数位（pos%2==1，即第2,4,6...位）减 d
new_diff = diff + d if pos % 2 == 0 else diff - d
res += dfs(pos + 1, new_diff, is_limit and d == up)
return res
return dfs(0, 0, True)
return count(high) - count(low - 1)
```
复杂度分析
- 时间复杂度：`O(log M × D²)`，其中 `M = high`，`D = 10`
- 空间复杂度：`O(log M × D)`，主要是 `lru_cache` 的缓存空间
关键要点
1. 数位奇偶性：`pos % 2 == 0` 对应第1、3、5...位（奇数位，从1开始计数），加 `d`；否则减 `d`
2. 差值 diff：`diff = 奇数位和 - 偶数位和`，最终需要 `diff == 0`
3. 范围计算：`count(high) - count(low - 1)` 得到 `[low, high]` 范围内的平衡整数个数
4. 边界处理：`x < 11` 时返回0，因为单个数字不可能平衡