代码编织梦想

题目

You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays redEdges and blueEdges where:

redEdges[i] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and
blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph.
Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist.

Example 1:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]

Constraints:

1 <= n <= 100
0 <= redEdges.length, blueEdges.length <= 400
redEdges[i].length == blueEdges[j].length == 2
0 <= ai, bi, uj, vj < n

解题思路

图的最短路径的变形题,状态里保存当前节点选择的下一条路径的颜色即可
时间复杂度是 o ( V + E ) o(V + E) o(V+E),其中VE分别是节点数和边数
空间复杂度是 o ( V ) o(V) o(V)

0和1互相更换,可以使用xor
在这里插入图片描述

代码

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        import collections
        # build graph
        red_neighbors = {}
        blue_neighbors = {}
        for edge_src, edge_dst in redEdges:
            if edge_src not in red_neighbors:
                red_neighbors[edge_src] = []
            red_neighbors[edge_src].append(edge_dst)
        for edge_src, edge_dst in blueEdges:
            if edge_src not in blue_neighbors:
                blue_neighbors[edge_src] = []
            blue_neighbors[edge_src].append(edge_dst)
        # bfs
        res = [-1] * n
        neighbor_choices = [red_neighbors, blue_neighbors]
        # node_index, path_len, next_color
        queue = collections.deque([(0, 0, 0), (0, 0, 1)])
        visited_nodes = set()
        while queue:
            node, path, color = queue.popleft()
            if (node, color) in visited_nodes:
                continue
            visited_nodes.add((node, color))
            res[node] = min(path, res[node] if res[node] != -1 else path)
            for neighbor in neighbor_choices[color].get(node, []):
                queue.append((neighbor, path + 1, int(not(color))))
        return res
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sinat_41679123/article/details/128859366

leetcode week contest 146_to_be_thinking的博客-爱代码爱编程

总结:这周周赛较难,勉强做两道的水准,但是非常有意思。 1128. Number of Equivalent Domino Pairs 这个问题我先用暴力解法,显然按照数据范围复杂度10^8过不了,然后就先统一骨牌形式(小,

leetcode刷题:1129. 颜色交替的最短路径(java代码解题)_梅森上校的博客-爱代码爱编程

1129. 颜色交替的最短路径(JAVA代码解题) 在一个有向图中,节点分别标记为 0, 1, ..., n-1。这个图中的每条边不是红色就是蓝色,且存在自环或平行边。 red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地,blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有

【Leetcode】1129. 颜色交替的最短路径-爱代码爱编程

题目 在一个有向图中,节点分别标记为 0, 1, ..., n-1。这个图中的每条边不是红色就是蓝色,且存在自环或平行边。 red_edges中的每一个 [i, j]对表示从节点i到节点j的红色有向边。类似地,blue_edges 中的每一个[i, j]对表示从节点 i 到节点j的蓝色有向边。 返回长度为 n 的数组answer,其中 answer[

LeetCode 1129. Shortest Path with Alternating Colors-爱代码爱编程

文章目录 题目知识点结果实现码前思考实现代码码后反思 题目 知识点 BFS 结果 时间空间都是还好,但是不算太差了,正常机试要求都是1000ms和32MB啦,先不对自己有过多的要求了。 实现 码前思考 我一看到这道题要求最短路径——Shortest Path,我就一头钻到了Dijkstra这类算最短路径的

LeetCode 1129. Shortest Path with Alternating Colors 图着色-爱代码爱编程

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] in re

【Leetcode】1129. Shortest Path with Alternating Colors-爱代码爱编程

题目地址: https://leetcode.com/problems/shortest-path-with-alternating-colors/ 给定一个 n n n阶有向图,顶点编号是

Leetcode 1129. 颜色交替的最短路径-爱代码爱编程

1129. 颜色交替的最短路径(难!!)题目 在一个有向图中,节点分别标记为 0, 1, …, n-1。这个图中的每条边不是红色就是蓝色,且存在自环或平行边。 red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地,blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向

leetcode题目分类 & 常用代码-爱代码爱编程

leetcode题目分类 & 常用代码 题目分类1、DFS+BFS2、递归+回溯常用代码Uthash递归 + 回溯并查集DFS、BFShash + 滑动窗口 题目分类 1、DFS+BFS https://leetcode-cn.com/problems/number-of-provinces/ https://leetcode-cn

leetcode 1129 (bfs)-爱代码爱编程

Thoughts on leetcode 1129 1. We need to insert the node of the other color to the priority queue 2. We don't need to keep track of the number of layers. Instead, we keep track o

leetcode1129题(图的bfs)_ff_y的博客-爱代码爱编程

在一个有向图中,节点分别标记为 0, 1, …, n-1。图中每条边为红色或者蓝色,且存在自环或平行边。red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地,blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。返回长度为 n 的数组 answer,其中 answer[X]

1129. 颜色交替的最短路径_蓝莓侠的博客-爱代码爱编程

在一个有向图中,节点分别标记为 0, 1, …, n-1。图中每条边为红色或者蓝色,且存在自环或平行边。 red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地,blue_edge

acwing leetcode 题目分类——配套基础课进阶课_啊枫_jiangchufeng的博客-爱代码爱编程

LeetCode 题目分类——配套基础课进阶课 1.基础 二分(满足一个条件的最值问题) LeetCode33 https://leetcode.com/problems/search-in-rotated-sorte

leetcode_binarytree_1129. shortest path with alternating colors 颜色交替的最短路径【bfs求最短路径】【java】【中等】_shortest path with orange and black edges-爱代码爱编程

一,题目描述 英文描述 You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there co