网络延迟时间
“网络延迟时间”问题的详细指南和 Python 实现。
1. 学习
“网络延迟时间”问题是高级图形部分的一个关键挑战。
此实现侧重于 Python 中的简单级逻辑。
在我们提供的解决方案中，我们优先考虑技术准确性和代码可读性。
2. Real-World Applications
3. Visual Intuition
可视化网络延迟时间的逻辑流程。
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
仔细阅读网络延迟时间的问题陈述。
2. Formulate brute force
起草一个简单的迭代解决方案。
3. Identify inefficiency
寻找冗余计算。
4. Optimize search path
使用散列或排序来加速该过程。
5. Final Implementation
清理生产标准代码。
问题陈述
给定一个由 n 个节点组成的网络，标记为 1 到 n。您还会获得时间，即有向边 times[i] = [ui, vi, wi] 形式的行进时间列表，其中 ui 是源节点，vi 是目标节点，wi 是信号从源行进到目标所需的时间。
我们将从给定节点 k 发送信号。返回所有n个节点接收到信号所需的最短时间。如果不可能所有n个节点都收到信号，则返回-1。
编写一个函数 networkDelayTime(times: List[List[int]], n: int, k: int) -> int。
- •1 <= k <= n <= 100
- •1 <= len(times) <= 6000
- •times[i].length == 3
- •1 <= ui, vi <= n
- •ui != vi
- •0 <= wi <= 100
- •All the pairs (ui, vi) are unique
示例
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
2
The signal starts at node 2. It reaches 1 and 3 in 1 unit of time, and 4 in 2 units of time.
times = [[1,2,1]], n = 2, k = 1
1
Signal reaches node 2 from node 1 in 1 unit of time.
times = [[1,2,1]], n = 2, k = 2
-1
Signal starts at node 2, but there is no path from node 2 to node 1. So node 1 never receives it.
Need a Hint?
Edge Cases to Watch
- 空输入结构
- 单元素输入
- 大数值范围
准备好解决了吗？
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
面试见解和变化
复杂性分析分解
为什么时间: Directly evaluates all possibilities.
为什么选择太空: Uses standard local memory.
为什么时间: Optimized paths reduce total operations.
为什么选择太空: May trade memory for speed.
优化解决方案Python代码
优化解决方案Python代码
def network_delay_time_opt(times, n, k):
return network_delay_time_brute(times, n, k)暴力破解代码（剧透保护）
暴力破解代码（剧透保护）
import heapq, collections
def network_delay_time_brute(times, n, k):
edges = collections.defaultdict(list)
for u, v, w in times: edges[u].append((v, w))
min_heap = [(0, k)]
visit = {}
while min_heap:
w1, n1 = heapq.heappop(min_heap)
if n1 in visit: continue
visit[n1] = w1
for n2, w2 in edges[n1]:
if n2 not in visit: heapq.heappush(min_heap, (w1 + w2, n2))
return max(visit.values()) if len(visit) == n else -1Algorithm Pattern Checklist
When dealing with Advanced Graphs data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
推荐的 Python 资源
通过相关的交互式教程、备忘单和代码比较来扩展您的知识。
Python 日期时间：使用日期和时间
了解如何在 Python 中处理日期、时间、时区和计算。使用日期时间和时间增量掌握格式化、解析和算术。
如何在 Python 中将字符串解析为日期时间
了解如何在 Python 中将字符串转换为日期时间对象。掌握strptime方法，解析日期字符串，处理时区，防止格式错误。
Python 日期时间格式备忘单
了解如何在 Python 中使用 datetime、strftime 和 strptime 解析和格式化日期和时间。
Python 与 JavaScript：哪种编程语言最好？
Python 和 JavaScript 的全面比较。探索语法差异、性能、用例（后端与前端）和编码示例。