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因为单个数字不可能平衡

相关新闻

2FAuth安全架构深度解析:从数据加密到RFC合规的实战指南

2FAuth安全架构深度解析:从数据加密到RFC合规的实战指南

1. 项目概述:为什么我们需要重新审视2FAuth的安全性?最近在部署和审计内部的双因素认证系统时,我花了大量时间深入研究一个开源项目:2FAuth。它不仅仅是一个简单的TOTP令牌生成器,其设计背后蕴含了许多对安全性和合规性…

2026/7/31 2:02:10 阅读更多 →
国产SPI Flash在Linux系统下的驱动适配与移植实战

国产SPI Flash在Linux系统下的驱动适配与移植实战

1. 项目概述:当国产平台遇上国产Flash最近在基于复旦微电子的FMQL系列平台(可以理解为国产化的ZYNQ)进行Linux系统开发时,遇到了一个挺典型但又有点棘手的问题:系统引导程序U-Boot和Linux内核无法正确识别板载的国产SP…

2026/7/31 2:02:10 阅读更多 →
GoF设计模式——建造者模式

GoF设计模式——建造者模式

h5打开以查看 为什么需要建造者模式? 在 GoF设计模式——抽象工厂模式 中,抽象工厂解决了"一族产品要风格统一"的问题——一个工厂负责一整套产品,选了工厂就等于选了整套风格。 但不管是工厂方法还是抽象工厂,都只管"产出什么",不管"怎么一步…

2026/7/31 2:01:10 阅读更多 →

最新新闻

Kali Linux 中文环境配置完全指南:从系统语言到输入法

Kali Linux 中文环境配置完全指南:从系统语言到输入法

一、Kali Linux 中文环境概述Kali Linux 作为一款专注于渗透测试和安全审计的 Linux 发行版,默认使用英文界面。对于中文用户来说,配置中文环境不仅能提高工作效率,还能避免因语言障碍导致的误操作。本文将详细介绍 Kali Linux 中文环境的完整…

2026/7/31 2:41:22 阅读更多 →
常见的7个Jmeter压测问题

常见的7个Jmeter压测问题

根据在之前的压测过程碰到的问题,今天稍微总结总结,以后方便自己查找。 一、单台Mac进行压测时候,压测客户端Jmeter启动超过2000个线程,Jmeter报OOM错误,如何解决? 解答:单台Mac配置内存为8G&…

2026/7/31 2:41:22 阅读更多 →
Python数据分析实战:从数学建模到可视化呈现的完整项目指南

Python数据分析实战:从数学建模到可视化呈现的完整项目指南

1. 项目缘起:为什么我们需要一个融合数学建模、分析与可视化的课程设计?在数据驱动的时代,无论是商业决策、科学研究还是日常运营,从海量数据中提炼洞察的能力已成为一项核心技能。然而,我观察到许多初学者&#xff0c…

2026/7/31 2:41:22 阅读更多 →
层次分析法实战:用yaahp量化决策,告别主观判断

层次分析法实战:用yaahp量化决策,告别主观判断

1. 项目概述:从决策焦虑到量化清晰 做项目评审、方案选型,或者哪怕只是团队内部评个优秀员工,你是不是也经常遇到这种场面?几个人围在一起,各说各的好,A方案技术领先但成本高,B方案风险低但周期…

2026/7/31 2:41:22 阅读更多 →
SWFNet:当脉冲神经网络遇见小波变换——VVC压缩360度视频质量增强的新范式

SWFNet:当脉冲神经网络遇见小波变换——VVC压缩360度视频质量增强的新范式

论文标题:SWFNet: A Spiking-Wavelet Fusion Network for Frame-Level Quality Enhancement of VVC-Compressed 360-Degree Video 发表期刊:IEEE Transactions on Circuits and Systems for Video Technology (TCSVT), 2026 DOI:10.1109/TCSV…

2026/7/31 2:41:22 阅读更多 →
嵌入式视觉跟踪系统开发:MaixCAM与无刷电机云台适配实战

嵌入式视觉跟踪系统开发:MaixCAM与无刷电机云台适配实战

在嵌入式视觉项目中,将高性能的AI摄像头与精密运动控制设备结合,往往能实现令人惊艳的效果。最近在开发一个智能跟踪系统时,遇到了MaixCAM与轮趣无刷电机云台的适配需求,发现相关资料比较零散。本文将完整记录从硬件选型、通信协议…

2026/7/31 2:40:22 阅读更多 →

日新闻

物理复制比逻辑复制好在哪?数据库复制原理详解

物理复制比逻辑复制好在哪?数据库复制原理详解

数据库复制是把主库数据同步到备库的机制,分为逻辑复制和物理复制两种。逻辑复制传输的是 SQL 语句或行变更事件,物理复制传输的是存储引擎底层的物理日志。阿里云 PolarDB(云原生数据库)采用物理复制,在同步延迟、数据…

2026/7/31 0:00:34 阅读更多 →
BilibiliDown:3分钟学会B站视频下载的终极指南

BilibiliDown:3分钟学会B站视频下载的终极指南

BilibiliDown:3分钟学会B站视频下载的终极指南 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader 😳 项目地址: https://gitcode.com/gh_mirrors/bi/Bilib…

2026/7/31 0:00:34 阅读更多 →
有哪些游戏数据AI平台?游戏行业Data+AI融合方案盘点

有哪些游戏数据AI平台?游戏行业Data+AI融合方案盘点

当前,游戏行业的“DataAI融合”已从概念验证进入价值落地阶段。根据IDC 2025年数据,中国AI游戏云市场规模已达18.6亿元;同时,游戏研发环节AI渗透率高达86%,生成式AI内容普及率超过50%。面对庞大的市场,游戏…

2026/7/31 0:00:34 阅读更多 →

周新闻

深度学习道路桥梁裂缝检测系统 道路桥梁裂缝检测数据集 道路桥梁病害识别检测数据集

深度学习道路桥梁裂缝检测系统 道路桥梁裂缝检测数据集 道路桥梁病害识别检测数据集

深度学习道路桥梁裂缝检测系统 数据集6000张 完整源码已标注数据集训练好的模型环境配置教程程序运行说明文档,可以直接使用!系统支持图片、视频、摄像头等多种方式检测裂缝,功能强大实用。 1数据集6000张 8各类别

2026/7/31 1:03:03 阅读更多 →
深度学习YOLO模型如何训练 PUBG 绝地求生目标检测数据集

深度学习YOLO模型如何训练 PUBG 绝地求生目标检测数据集

pubg数据集 精选原图1.42万数据 1.49万标签 无任何重复、算法增强或冗余图像! pubg绝地求生目标检测数据集 1分类:e_body,14905个标签,txt格式 共计14244张图,99%为640*640尺寸图像 适合yolo目标检测、AI训练关键词&am…

2026/7/29 14:34:28 阅读更多 →
Apex英雄目标检测数据集 深度学习框架YOLO如何训练APEX数据集

Apex英雄目标检测数据集 深度学习框架YOLO如何训练APEX数据集

Apex检测数据集数据集详情检测类别: allies enemy tag图片总量:7247张训练集:5139张验证集:1425张测试集:683张标注状态:全部已标注,即拿即用数据格式:支持YOLO格式及其他格式&#…

2026/7/29 15:00:03 阅读更多 →

月新闻