列表

详情

LCP 62. 交通枢纽

为了缓解「力扣嘉年华」期间的人流压力，组委会在活动期间开设了一些交通专线。path[i] = [a, b] 表示有一条从地点 a通往地点 b 的 单向 交通专线。 若存在一个地点，满足以下要求，我们则称之为 交通枢纽：

请返回交通专线的 交通枢纽。若不存在，则返回 -1。

注意：

示例 1：

输入：path = [[0,1],[0,3],[1,3],[2,0],[2,3]]

输出：3

解释：如下图所示： 地点 0,1,2 各有一条通往地点 3 的交通专线， 且地点 3 不存在任何通往其他地点的交通专线。 image.png{:width=200px}

示例 2：

输入：path = [[0,3],[1,0],[1,3],[2,0],[3,0],[3,2]]

输出：-1

解释：如下图所示：不存在满足 交通枢纽 的地点。 image.png{:width=200px}

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int transportationHub(vector<vector<int>>& path) { } };

golang 解法, 执行用时: 12 ms, 内存消耗: 6.6 MB, 提交时间: 2022-11-21 15:19:49 

func transportationHub(path [][]int) int {
	nodes := map[int]struct{}{}
	outDeg := map[int]int{}
	inDeg := map[int]int{}
	for _, p := range path {
		x, y := p[0], p[1]
		nodes[x] = struct{}{}
		nodes[y] = struct{}{}
		outDeg[x]++
		inDeg[y]++
	}
	for x := range nodes {
		if outDeg[x] == 0 && inDeg[x] == len(nodes)-1 {
			return x
		}
	}
	return -1
}

python3 解法, 执行用时: 44 ms, 内存消耗: 15.2 MB, 提交时间: 2022-11-21 15:19:24 

class Solution:
    def transportationHub(self, path: List[List[int]]) -> int:
        nodes = set()
        out_deg = Counter()
        in_deg = Counter()
        for x, y in path:
            nodes.add(x)
            nodes.add(y)
            out_deg[x] += 1
            in_deg[y] += 1
        for x in nodes:
            if out_deg[x] == 0 and in_deg[x] == len(nodes) - 1:
                return x
        return -1

上一题

© 2024 leetcode.cn