侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【哈希表】交通枢纽【LCCUP 2022秋季赛】

GabrielxD
2022-09-25 / 0 评论 / 0 点赞 / 19 阅读 / 452 字 / 正在检测是否收录...

题目

LCP 61. 气温变化趋势


为了缓解「力扣嘉年华」期间的人流压力,组委会在活动期间开设了一些交通专线。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-20220925220130562

示例 2:

输入:path = [[0,3],[1,0],[1,3],[2,0],[3,0],[3,2]]
输出:-1
解释:如下图所示:不存在满足 交通枢纽 的地点。
image-20220925220243923

提示:

  • 1 <= path.length <= 1000
  • 0 <= path[i][0], path[i][1] <= 1000
  • path[i][0] 与 path[i][1] 不相等

解题

方法一:哈希表

思路

维护一个哈希表(map),假设共有 n 个节点,那么需要找到的就是一个入度为 n-1 出度为 0 的节点。

代码

class Solution {
    public int transportationHub(int[][] path) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] p : path) {
            map.put(p[0], -1);
            map.put(p[1], map.getOrDefault(p[1], 0) + 1);
        }
        int n = map.size();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == n - 1) return entry.getKey();
        }
        return -1;
    }
}
0

评论区