leetcode-1791:找出星型图的中心节点

简介: leetcode-1791:找出星型图的中心节点

题目

参考链接

有一个无向的 星型 图,由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点,并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。

给你一个二维整数数组 edges ,其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。请你找出并返回 edges 所表示星型图的中心节点。

示例 1:

输入:edges = [[1,2],[2,3],[4,2]]
输出:2
解释:如上图所示,节点 2 与其他每个节点都相连,所以节点 2 是中心节点。

示例 2:

输入:edges = [[1,2],[5,1],[1,3],[1,4]]
输出:1

解题

方法一:

查找出现n次的节点

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        int n=edges.size();
        unordered_map<int,int> map;
        for(vector<int>& edge:edges){
            map[edge[0]]++;
            map[edge[1]]++;
        }
        for(auto it=map.begin();it!=map.end();it++){
            if(it->second==n){
                return it->first;
            }
        }
        return -1;
    }
};

方法二:

可以任选两条边,然后寻找这两条边的公共节点,该节点即为星型图的中心节点。

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        return edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] ? edges[0][0] : edges[0][1];
    }
};


相关文章
|
21天前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
13 0
LeetCode第二十四题(两两交换链表中的节点)
|
21天前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
36 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
21天前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
10 0
|
3月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
3月前
|
Python
【Leetcode刷题Python】450. 删除二叉搜索树中的节点
LeetCode上538号问题"把二叉搜索树转换为累加树"的Python实现,使用反向中序遍历并记录节点值之和来更新每个节点的新值。
36 4
【Leetcode刷题Python】450. 删除二叉搜索树中的节点
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
49 5
|
3月前
|
Python
【Leetcode刷题Python】222. 完全二叉树的节点个数
LeetCode第222题"完全二叉树的节点个数"的Python代码实现,通过递归和深度优先遍历的方法来计算给定完全二叉树的节点总数。
31 5
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
40 4
|
5月前
|
算法 数据可视化 数据挖掘
哈希表+DFS快速解决力扣129题:求根节点到叶节点数字之和
哈希表+DFS快速解决力扣129题:求根节点到叶节点数字之和
|
6月前
|
存储
【LeetCode】剑指 Offer 54. 二叉搜索树的第k大节点
【LeetCode】剑指 Offer 54. 二叉搜索树的第k大节点
44 1