力扣(LeetCode)310

amuqiao 發(fā)布于2019-08-16 16:13 / 2817人閱讀

摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數找到所有的最小高度樹并返回他們的根節(jié)點。因此使用一個數組代表每個節(jié)點的入度，若入度為就是葉子節(jié)點。

題目地址：
https://leetcode-cn.com/probl...
題目描述：

對于一個具有樹特征的無向圖，我們可選擇任何一個節(jié)點作為根。圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數找到所有的最小高度樹并返回他們的根節(jié)點。

格式

該圖包含 n 個節(jié)點，標記為 0 到 n - 1。給定數字 n 和一個無向邊 edges 列表（每一個邊都是一對標簽）。

你可以假設沒有重復的邊會出現(xiàn)在 edges 中。由于所有的邊都是無向邊， [0, 1]和 [1, 0] 是相同的，因此不會同時出現(xiàn)在 edges 里。

示例 1:

輸入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / 
      2   3 

輸出: [1]
示例 2:

輸入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
       | /
        3
        |
        4
        |
        5 

輸出: [3, 4]

解答：
這一題比較有技巧，如果求任意一點到任意一點的距離，那么會時間復雜度會很大。
比較高效的做法是，每次把葉子節(jié)點從圖(把樹轉換為圖結構)刪掉。
直到只剩下1個或者2個點的時候輸出。

算法思想很簡單。但是實現(xiàn)起來有寫麻煩。如果每次都判斷葉子節(jié)點，那么效率會很低。
因此使用一個數組inDegree[]代表每個節(jié)點的入度，若入度為1就是葉子節(jié)點。
并且用一個隊列(棧也可以，只要是那種能彈出的容器即可)裝葉子節(jié)點。
然后寬度優(yōu)先搜索隊列中葉子節(jié)點，刪除節(jié)點和它們對應的邊，并加入新的葉子節(jié)點(有可能刪除葉子節(jié)點的邊之后，它的鄰接點p的入度變?yōu)?,也就是inDegree[p] = 1，此時可以把p加入隊列中)。
直到只剩下1個或者2個點停止。返回結果。

java ac代碼：
class Solution {
    public List findMinHeightTrees(int n, int[][] edges) {
    
        Listans = null;
        if(n <= 2)
        {
            ans = new ArrayList(2);
            for(int i = 0;i < n;i++)
                ans.add(i);
            return ans;
        }
        
        //去掉葉子節(jié)點，直到只剩下一個或者兩個節(jié)點。
        int[]inDegree = new int[n];
        
        //用鄰接表存儲圖。
        List[] map = new List[n];
        for(int i = 0;i < n;i++)
            map[i] = new ArrayList();
       for(int i = 0;i < edges.length;i++)
       {
           map[edges[i][0]].add(edges[i][1]);
           map[edges[i][1]].add(edges[i][0]);
           inDegree[edges[i][0]]++;
           inDegree[edges[i][1]]++;
       }
        
        int count = n;
        Queuequeue = new ArrayDeque();
            for(int i = 0;i < n;i++)
                if(inDegree[i] == 1)
                    queue.offer(i);
        while(count > 2)
        {
            int size = queue.size();
            for(int loc  = 0;loc < size;loc++)
            {
                int ii = queue.poll();
                int jj = map[ii].get(0);
               
                inDegree[jj]--;
                if(inDegree[jj] == 1)
                    queue.offer(jj);
                
                map[jj].remove(new Integer(ii));
                map[ii].remove(new Integer(jj));
                inDegree[ii] = -1;
                
                count--;
            }
        }
    
        ans = new ArrayList(queue);
        
        return ans;
    }
    
    
}

這個和力扣(LeetCode)207很像，雖然不是拓撲排序，但都是利用一個可彈出容器裝節(jié)點，然后寬度搜索容器中的節(jié)點。

云服務器 GPU云服務器力扣 LeetCode 310vps 310vps曲線

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

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

＜LeetCode天梯＞Day026 反轉鏈表（遞歸法+（迭代法）雙鏈表法） | 初級算法 | Py

摘要：關于遞歸這里提一兩點遞歸基本有這幾步遞歸的模板，終止條件，遞歸調用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學路18號的車神? ?個人主頁：應無所住而生...

imingyu 2021-11-17 09:33 評論0 收藏0
力扣(LeetCode)452

摘要：對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束坐標。可以射出的弓箭的數量沒有限制。弓箭一旦被射出之后，可以無限地前進。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數量。解答這是一道區(qū)間覆蓋問題，不太好說清楚，利用模板即可。題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方...

fanux 2019-08-16 15:20 評論0 收藏0
＜LeetCode天梯＞Day031 驗證二叉搜索樹（遞歸+中序遍歷） | 初級算法 | Pytho

摘要：有效二叉搜索樹定義如下節(jié)點的左子樹只包含小于當前節(jié)點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節(jié)點的值均小于根節(jié)點的值，根節(jié)點的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 評論0 收藏0
力扣(LeetCode)133

摘要：提示節(jié)點數介于到之間。無向圖是一個簡單圖，這意味著圖中沒有重復的邊，也沒有自環(huán)。必須將給定節(jié)點的拷貝作為對克隆圖的引用返回。這一題的做法是，使用一個來記錄，原和新的對應關系。題目地址：https://leetcode-cn.com/probl...題目描述：給定無向連通圖中一個節(jié)點的引用，返回該圖的深拷貝（克隆）。圖中的每個節(jié)點都包含它的值 val（Int）和其鄰居的列表（list...

Steve_Wang_ 2019-08-19 11:39 評論0 收藏0