Minimum Height Trees

joyqi 发布于2019-08-14 17:26 / 3018人阅读

摘要：题目链接图的题，和差不多。来解，每次放入只有一个的现在的。然后直到只剩最上面一层。注意考虑多带带的和别的不相连。比如这种情况，就有三个点都不和别的相连。还有的时候就要返回。

Minimum Height Trees

题目链接：https://leetcode.com/problems...

图的题，和course schedule差不多。bfs来解，每次放入只有一个edge的node（现在的leaf）。然后直到只剩最上面一层。注意考虑多带带的node（和别的node不相连）。比如: [[1,2], [2,3]], n = 6这种情况，就有[0, 4, 5]三个点都不和别的node相连。还有[], n = 2的时候就要返回[0, 1]。

public class Solution {
    public List findMinHeightTrees(int n, int[][] edges) {
        // adjacent set
        Set[] set = new HashSet[n];
        for(int i = 0; i < n; i++) set[i] = new HashSet();
        for(int[] edge : edges) {
            set[edge[0]].add(edge[1]);
            set[edge[1]].add(edge[0]);
        }
        
        // use queue to do bfs
        LinkedList q = new LinkedList();
        List edge_case = new ArrayList();
        for(int i = 0; i < set.length; i++) {
            if(set[i].size() == 1) q.add(i);
            if(set[i].size() == 0) edge_case.add(i);
        }
        // if cycle
        if(q.size() == 0) return edge_case;
        
        int count = edge_case.size();
        while(count + q.size() < n) {
            int size = q.size();
            count += size;
            while(size-- > 0) {
                int node = q.remove();
                int parent = set[node].iterator().next();
                set[node].remove(parent);
                set[parent].remove(node);
                if(set[parent].size() == 1) q.add(parent);
            }
        }
        return q;
    }
}

云服务器 GPU云服务器 Minimum Trees height() height

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66635.html

Leetcode 310. Minimum Height Trees

摘要：可以从头边同时进行，查看叶子节点并加入到叶子节点链表遍历一遍后，叶子节点链表为。将叶子节点保存下来。这个时候就会有第二层叶子节点那些在列表当中为的点，用同样的方法进行剥除。最后留在叶子节点里面的点即可以为根。题目： For a undirected graph with tree characteristics, we can choose any node as the root...

xuxueli 2019-08-14 17:11 评论0 收藏0
leetcode310. Minimum Height Trees

摘要：现在要求在这样一棵生成树中，找到生成树的高度最低的所有根节点。然后利用邻接表的相关属性来判断当前节点是否是叶节点。度数为一的顶点就是叶节点。这里使用异或的原因是对同一个值进行两次异或即可以回到最初值。题目 For an undirected graph with tree characteristics, we can choose any node as the root. The...

xiaoxiaozi 2019-08-16 13:46 评论0 收藏0
[LeetCode] 675. Cut Off Trees for Golf Event

Problem You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map: 0 represents the obstacle cant be reached.1 represents the ground ...

MudOnTire 2019-08-16 13:58 评论0 收藏0
A Brief Introduce of Database Index（索引简介）

摘要：所以这篇文章希望帮助大家理解一下。我没有在算法上展开太多，因为很多算法相似，如果展开容易喧宾夺主。等过段时间我会加入一些实验数据和代码进这篇文章，最近比较懒不想安装数据库安装实在太烦了。这是我写的一篇研究生申请的writing sample，关于数据库索引的，对关系型数据库的索引从数据结构到用途再到作用对象简单分析了一下，因为我发现在实际工作中，index是个好东西，但是很多DBA并...

marek 2019-06-25 18:23 评论0 收藏0