Minimum Height Trees

joyqi 發布于2019-08-14 17:26 / 3037人閱讀

摘要：題目鏈接圖的題，和差不多。來解，每次放入只有一個的現在的。然后直到只剩最上面一層。注意考慮多帶帶的和別的不相連。比如這種情況，就有三個點都不和別的相連。還有的時候就要返回。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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