国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Leetcode 310. Minimum Height Trees

xuxueli / 1548人閱讀

摘要:可以從頭邊同時進行,查看葉子節點并加入到葉子節點鏈表遍歷一遍后,葉子節點鏈表為。將葉子節點保存下來。這個時候就會有第二層葉子節點那些在列表當中為的點,用同樣的方法進行剝除。最后留在葉子節點里面的點即可以為根。

題目:

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format The graph contains n nodes which are labeled from 0 to n - 1.
You will be given the number n and a list of undirected edges (each
edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all
edges are undirected, [0, 1] is the same as [1, 0] and thus will not
appear together in edges.

解法:
因為樹就是兩個點被一條線鏈接的無向圖,所以先用一個list把樹存成無向圖的列表。可以從頭邊同時進行,查看葉子節點并加入到葉子節點鏈表(遍歷一遍后,葉子節點鏈表size 為1)。 將葉子節點保存下來。這些葉子節點不用再查,但是剩余的中間節點,要依次查看,把跟第一層葉子節點有關的圖的矩陣里對應的記錄全部刪除,類似于剝除最外面一圈所有的點。 這個時候就會有第二層葉子節點(那些在列表當中size為1的點),用同樣的方法進行剝除。最后留在葉子節點list里面的點即可以為根。

代碼:

public List findMinHeightTrees(int n, int[][] edges) {
        List leaves = new ArrayList<>();
        if (n == 1) {
            leaves.add(0);
            return leaves;
        }
        
        List> adj = new ArrayList<>();
        for(int i = 0; i < n; i++) adj.add(new HashSet<>());
        for(int[] edge : edges){
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        for(int i = 0; i < n; i++) 
         if(adj.get(i).size()==1) leaves.add(i);
        while(n > 2){
            n-=leaves.size();
            List newLeaves = new ArrayList<>();
            for(int i : leaves){
                for(int j : adj.get(i)){
                    adj.get(j).remove(i);
                    if(adj.get(j).size() ==1) newLeaves.add(j);
                }
            }
            leaves = newLeaves;
        }
        return leaves;
    }

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

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66472.html

相關文章

  • leetcode310. Minimum Height Trees

    摘要:現在要求在這樣一棵生成樹中,找到生成樹的高度最低的所有根節點。然后利用鄰接表的相關屬性來判斷當前節點是否是葉節點。度數為一的頂點就是葉節點。這里使用異或的原因是對同一個值進行兩次異或即可以回到最初值。 題目 For an undirected graph with tree characteristics, we can choose any node as the root. The...

    xiaoxiaozi 評論0 收藏0
  • Minimum Height Trees

    摘要:題目鏈接圖的題,和差不多。來解,每次放入只有一個的現在的。然后直到只剩最上面一層。注意考慮單獨的和別的不相連。比如這種情況,就有三個點都不和別的相連。還有的時候就要返回。 Minimum Height Trees 題目鏈接:https://leetcode.com/problems... 圖的題,和course schedule差不多。bfs來解,每次放入只有一個edge的node(現...

    joyqi 評論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 評論0 收藏0
  • [LeetCode] 253. Meeting Rooms II

    Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required. Example 1: Input: [[0, 30],[5,...

    mengera88 評論0 收藏0
  • [LeetCode] 96. Unique Binary Search Trees I &

    Unique Binary Search Trees Problem Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? Example Given n = 3, there are a total of 5 unique BSTs. 1 3 3...

    nidaye 評論0 收藏0

發表評論

0條評論

xuxueli

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<