Kimi LeetCode 3791. 给定范围内平衡整数的数目 Python3实现

以下是 LeetCode 3791. 给定范围内平衡整数的数目 的 Python3 实现。题目理解一个整数是平衡的当且仅当1. 至少包含两位数字2. 奇数位数字之和等于偶数位数字之和最左边数字位置为1约束1 low high 10^15需要使用数位 DP。Python3 实现pythonfrom functools import lru_cacheclass Solution:def countBalanced(self, low: int, high: int) - int:# 如果 high 11范围内没有至少两位的数直接返回0if high 11:return 0# 计算 [0, x] 中平衡整数的个数def calc(x: int) - int:s str(x)n len(s)lru_cache(maxsizeNone)def dfs(pos: int, diff: int, is_limit: bool, is_num: bool) - int:# pos: 当前处理到的位置# diff: 奇数位和 - 偶数位和# is_limit: 是否受上界限制# is_num: 是否已经填了非前导零的数字if pos n:# 必须至少两位且差值为0return 1 if is_num and diff 0 else 0res 0up int(s[pos]) if is_limit else 9for 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(maxsizeNone)def dfs(pos: int, diff: int, is_limit: bool, started: bool, digit_count: int) - int:if pos n:# 必须已经开始至少一位且至少两位且差值为0return 1 if started and digit_count 2 and diff 0 else 0res 0up int(s[pos]) if is_limit else 9for d in range(up 1):if not started and d 0:# 还是前导零res dfs(pos 1, diff, False, False, 0)else:# 当前是第 digit_count1 位从1开始计数new_count digit_count 1# 奇数位加偶数位减new_diff diff d if new_count % 2 1 else diff - dres dfs(pos 1, new_diff, is_limit and d up, True, new_count)return resreturn dfs(0, 0, True, False, 0)return count(high) - count(low - 1)更简洁的版本不带前导零处理因为题目要求至少两位pythonfrom functools import lru_cacheclass Solution:def countBalanced(self, low: int, high: int) - int:def count(x: int) - int:if x 11:return 0s str(x)n len(s)lru_cache(maxsizeNone)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 0res 0up int(s[pos]) if is_limit else 9for d in range(up 1):# pos 从0开始对应第1位奇数位# 奇数位pos%20即第1,3,5...位加 d# 偶数位pos%21即第2,4,6...位减 dnew_diff diff d if pos % 2 0 else diff - dres dfs(pos 1, new_diff, is_limit and d up)return resreturn dfs(0, 0, True)return count(high) - count(low - 1)复杂度分析- 时间复杂度O(log M × D²)其中 M highD 10- 空间复杂度O(log M × D)主要是 lru_cache 的缓存空间关键要点1. 数位奇偶性pos % 2 0 对应第1、3、5...位奇数位从1开始计数加 d否则减 d2. 差值 diffdiff 奇数位和 - 偶数位和最终需要 diff 03. 范围计算count(high) - count(low - 1) 得到 [low, high] 范围内的平衡整数个数4. 边界处理x 11 时返回0因为单个数字不可能平衡