【leetcode】1129. Shortest Path with Alternating Colors
2024-08-31 11:09:09
题目如下:
Consider a directed graph, with nodes labelled
0, 1, ..., n-1
. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.Each
[i, j]
inred_edges
denotes a red directed edge from nodei
to nodej
. Similarly, each[i, j]
inblue_edges
denotes a blue directed edge from nodei
to nodej
.Return an array
answer
of lengthn
, where eachanswer[X]
is the length of the shortest path from node0
to nodeX
such that the edge colors alternate along the path (or-1
if such a path doesn't exist).Example 1:
Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]Example 2:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]Example 3:
Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]Example 4:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]Example 5:
Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]Constraints:
1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n
解题思路:本题采用BFS的思想。对于每一个节点来说,分别求出其红边和蓝边作为入口的最小值。
代码如下:
class Solution(object):
def shortestAlternatingPaths(self, n, red_edges, blue_edges):
"""
:type n: int
:type red_edges: List[List[int]]
:type blue_edges: List[List[int]]
:rtype: List[int]
"""
res = [0] + [float('inf')] * (n - 1)
queue = []
red_used = [0] * len(red_edges)
blue_used = [0] * len(blue_edges)
def process(target, edges, res, color,used_list,step_count):
for inx,(i, j) in enumerate(edges):
used = used_list[inx]
if i == target and used == 0:
res[j] = min(res[j],step_count + 1)
queue.append((j, color,step_count + 1))
used_list[inx] = 1
#red
process(0, red_edges, res, 'R',red_used,0)
while len(queue) > 0:
num, color,step = queue.pop(0)
if color == 'R':
process(num, blue_edges, res, 'B',blue_used,step)
else:
process(num, red_edges, res, 'R',red_used,step) red_used = [0] * len(red_edges)
blue_used = [0] * len(blue_edges)
process(0, blue_edges, res, 'B', blue_used,0)
while len(queue) > 0:
num, color,step = queue.pop(0)
if color == 'R':
process(num, blue_edges, res, 'B',blue_used,step)
else:
process(num, red_edges, res, 'R',red_used,step) res = map(lambda x: x if x != float('inf') else -1, res)
return res
最新文章
- java byte&;0xFF
- Python之字符串小代码解析
- VBA用户控件
- Java中抽象类和接口的区别
- git之remote repository create(远程仓库创建)
- jquery.cookie中的操作
- linux用户、组管理及权限(一)
- 17---Net基础加强
- oracle 分析函数(笔记)
- laravel重要概念和知识点
- SQL Server 事务处理 回滚事务
- js刷新页面方法
- java 基础之数据类型
- ubuntu fcitx 安装 使用
- APM代码学习笔记1
- Java学习之路:详细解释Java解析XML四种方法
- Linux分区规划与xshell使用排错
- mariadb开启远程访问
- 《手机端》让多出的导航变水平拖动,不让他 float 撑下去
- HDU 1014 Uniform Generator(题解)