Kimi LeetCode 3534. 针对图的路径存在性查询 II Python3实现-北京尧图网络

以下是 LeetCode 3534. 针对图的路径存在性查询 II 的完整 Python3 实现。---核心思路1. 排序将节点按 nums 值排序。排序后同一连通分量内的节点必然连续。2. 双指针求最远跳对每个位置 i求出一步能到达的最远位置 nxt[i]。3. 倍增预处理jump[i][k] 表示从 i 连续做 2^k 次最远跳到达的位置。4. 查询先判断是否在同一连通分量再用倍增贪心求最少步数。时间复杂度O(n log n q log n)空间复杂度O(n log n)。---Python3 代码pythonfrom typing import Listclass Solution:def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) - List[int]:# 1. 按 nums 值排序记录原始下标 - 排序后位置的映射order sorted(range(n), keylambda x: nums[x])sorted_nums [nums[i] for i in order]pos [0] * n # pos[originalIndex] sortedPositionfor i, idx in enumerate(order):pos[idx] i# 2. 计算连通分量编号排序后连续段comp [0] * nfor i in range(1, n):comp[i] comp[i - 1]if sorted_nums[i] - sorted_nums[i - 1] maxDiff:comp[i] 1# 3. 双指针求 nxt[i]从排序后位置 i 一步能跳到的最远位置nxt [0] * nr 0for i in range(n):while r 1 n and sorted_nums[r 1] - sorted_nums[i] maxDiff:r 1nxt[i] r# 4. 倍增数组jump[i][k] 表示从 i 连续跳 2^k 次最远跳到达的位置LOG (n 1).bit_length()jump [[0] * LOG for _ in range(n)]for i in range(n):jump[i][0] nxt[i]for k in range(1, LOG):for i in range(n):jump[i][k] jump[jump[i][k - 1]][k - 1]# 5. 回答查询ans []for u, v in queries:if u v:ans.append(0)continuepu, pv pos[u], pos[v]if pu pv:pu, pv pv, pu# 不在同一连通分量不可达if comp[pu] ! comp[pv]:ans.append(-1)continue# 倍增贪心从高位到低位能跳就跳求最少步数cur pusteps 0for k in range(LOG - 1, -1, -1):if jump[cur][k] pv:steps 1 kcur jump[cur][k]# 最后一步一定能到达 pvans.append(steps 1)return ans---关键点说明步骤说明排序映射 pos[u] 将原始节点编号映射到排序后的位置后续操作都在排序后的数组上进行。连通分量排序后若相邻元素差 maxDiff则开启新连通分量。查询时先判断 comp[pu] comp[pv]。最远跳 nxt 由于数组已排序双指针可在 O(n) 内求出每个位置一步能覆盖的最远范围。nxt[i] 单调不降。倍增 jump 类似树上倍增但这里是区间最远跳的倍增。jump[i][k] 表示从 i 出发连续做 2^k 次贪心最远跳到达的位置。查询贪心从 pu 到 pv从高位到低位尝试如果跳 2^k 步后仍到不了 pv就先跳这 2^k 步。最终剩余距离只需一步即可覆盖。

Kimi LeetCode 3534. 针对图的路径存在性查询 II Python3实现

相关推荐

5分钟掌握RPG Maker游戏资源解密：免费开源工具全攻略

ROS2 话题与服务通信超详解（C++实战+底层原理+所有疑难问题根治）

OpenAI Codex代码生成模型：从环境配置到实战应用完整指南

更多资讯

SAP ECC企业级ERP系统核心解析：架构、模块与实操

MATLAB信号与系统实验报告写作与验收全流程

Linux proc文件系统实验：从进程观测到系统分析

深入解析proc文件系统实验：从内核模块到动态文件读写

impeccable用法解析：从英语近义词辨析到职场内容创作的无懈可击标准

Claude Code工具系统架构与注册表模式实战

今日更新

微信个人号API开发案例：图片/语音/视频消息怎么下载解析存到本地？

Python股票自动交易系统源码解析：从行情获取到风控的完整链路

视酷酷信IM源码部署指南：Java 17+MySQL 8.0.33实战配置

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？