欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實現(xiàn)最小高度樹

 更新時間:2022年04月08日 16:28:51   作者:&小小白&  
本文主要介紹了Java實現(xiàn)最小高度樹,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

題設(shè)要求

樹是一個無向圖,其中任何兩個頂點只通過一條路徑連接。 換句話說,一個任何沒有簡單環(huán)路的連通圖都是一棵樹。

給你一棵包含 n 個節(jié)點的樹,標記為 0 到 n - 1 。給定數(shù)字 n 和一個有 n - 1 條無向邊的 edges 列表(每一個邊都是一對標簽),其中 edges[i] = [ai, bi] 表示樹中節(jié)點 ai 和 bi 之間存在一條無向邊。

可選擇樹中任何一個節(jié)點作為根。當選擇節(jié)點 x 作為根節(jié)點時,設(shè)結(jié)果樹的高度為 h 。在所有可能的樹中,具有最小高度的樹(即,min(h))被稱為 最小高度樹 。

請你找到所有的 最小高度樹 并按 任意順序 返回它們的根節(jié)點標簽列表。

樹的 高度 是指根節(jié)點和葉子節(jié)點之間最長向下路徑上邊的數(shù)量。

示例 1:

請?zhí)砑訄D片描述

輸入:n = 4, edges = [[1,0],[1,2],[1,3]]
輸出:[1]
解釋:如圖所示,當根是標簽為 1 的節(jié)點時,樹的高度是 1 ,這是唯一的最小高度樹。

示例 2:

請?zhí)砑訄D片描述

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

提示:
1 <= n <= 2 * 104
edges.length == n - 1
0 <= ai, bi < n
ai != bi
所有 (ai, bi) 互不相同
給定的輸入保證是一棵樹,并且不會有重復(fù)的邊

解題思路

?  由上述兩個圖我們可以得出結(jié)論:題中需要求解的是樹里面的中心節(jié)點,而每個樹的中心節(jié)點不會超過兩個。

?  而我們想要求得樹里面的中心節(jié)點,我們就可以逐層FBS(也就是逐層將出度為一的葉子節(jié)點剪掉),直至剪到最后一層,就可以將結(jié)果輸出了!

算法

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<Integer>();
        //如果只有一個節(jié)點,則它就是最小高度樹
        if(n == 1){
            res.add(0);
            return res;
        }

        //每個節(jié)點的鄰居數(shù)量
        int [] degree = new int[n];
        //每個節(jié)點的鄰居
        HashMap<Integer,List<Integer>> map = new HashMap<>();

        for(int [] edge : edges){
            int a = edge[0];
            int b = edge[1];

            degree[a]++;
            degree[b]++;

            if(map.get(a) == null){
                map.put(a,new ArrayList<Integer>());//key:節(jié)點   value:鄰居
            }

            if(map.get(b) == null){
                map.put(b,new ArrayList<Integer>());//key:節(jié)點   value:鄰居
            }

            map.get(a).add(b);
            map.get(b).add(a);
        }

        //建立隊列
        LinkedList<Integer> leafNodes = new LinkedList<Integer>();//表示葉子節(jié)點
        //將所有度為1的節(jié)點入隊
        for(int i = 0;i < degree.length;i++){
            if(degree[i] == 1){
                leafNodes.add(i);
            }
        }

        while(leafNodes.size() > 0){
            res.clear();
            //每一層節(jié)點的數(shù)量
            int size = leafNodes.size();

            for(int i = 0;i < size;i++){
                int leaf = leafNodes.poll();
                //將當前節(jié)點加入到結(jié)果集
                res.add(leaf);

                List<Integer> neighbors = map.get(leaf);
                //將出度減一,也就是將最外層的葉子節(jié)點剪掉
                for(int neighbor : neighbors){
                    degree[neighbor]--;
                    if(degree[neighbor] == 1){
                        //葉子節(jié)點入隊
                        leafNodes.add(neighbor);
                    }
                }
            }
        }
        return res;
    }
}

到此這篇關(guān)于Java實現(xiàn)最小高度樹的文章就介紹到這了,更多相關(guān)Java 最小高度樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • java  多線程的三種構(gòu)建方法

    java 多線程的三種構(gòu)建方法

    這篇文章主要介紹了java 多線程的三種構(gòu)建方法的相關(guān)資料,這里提供三種實現(xiàn)方法,希望大家能夠掌握,很重要的基礎(chǔ)知識,需要的朋友可以參考下
    2017-09-09
  • Java中的static關(guān)鍵字全面解析

    Java中的static關(guān)鍵字全面解析

    這篇文章主要介紹了Java中的static關(guān)鍵字全面解析的相關(guān)資料,非常不錯,具有參考借鑒價值,需要的朋友可以參考下
    2016-06-06
  • Java實現(xiàn)馬踏棋盤算法

    Java實現(xiàn)馬踏棋盤算法

    這篇文章主要為大家詳細介紹了Java實現(xiàn)馬踏棋盤算法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-02-02
  • Spring是怎么擴展解析xml接口的

    Spring是怎么擴展解析xml接口的

    這篇文章主要介紹了Spring是怎么擴展解析xml接口的,文章圍繞主題展開詳細的內(nèi)容介紹,具有一定的參考價值,需要的小伙伴可以參考一下
    2022-08-08
  • SpringBoot中實現(xiàn)定時任務(wù)的幾種方式

    SpringBoot中實現(xiàn)定時任務(wù)的幾種方式

    定時任務(wù)在我們項目開發(fā)中也是很重要的,對于某些場景必須要用定時任務(wù)?,如定時發(fā)送郵件啊,定時統(tǒng)計數(shù)據(jù)等,這篇文章主要講講項目中實現(xiàn)定時任務(wù)的幾種方式,需要的朋友可以參考下
    2023-05-05
  • Spring boot實現(xiàn)一個簡單的ioc(1)

    Spring boot實現(xiàn)一個簡單的ioc(1)

    這篇文章主要為大家詳細介紹了Spring boot實現(xiàn)一個簡單的ioc,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-04-04
  • 解決mybatis-plus動態(tài)數(shù)據(jù)源切換不生效的問題

    解決mybatis-plus動態(tài)數(shù)據(jù)源切換不生效的問題

    本文主要介紹了解決mybatis-plus動態(tài)數(shù)據(jù)源切換不生效的問題,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-01-01
  • Java 基礎(chǔ)--Arrays工具類詳解

    Java 基礎(chǔ)--Arrays工具類詳解

    這篇文章主要介紹了Java Arrays工具類用法,結(jié)合實例形式分析了java Arrays工具類針對數(shù)組元素修改、復(fù)制、排序等操作使用技巧與相關(guān)注意事項,需要的朋友可以參考下
    2021-09-09
  • 詳解springboot設(shè)置cors跨域請求的兩種方式

    詳解springboot設(shè)置cors跨域請求的兩種方式

    這篇文章主要介紹了詳解springboot設(shè)置cors跨域請求的兩種方式,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-11-11
  • Spring Cloud Gateway重試機制的實現(xiàn)

    Spring Cloud Gateway重試機制的實現(xiàn)

    這篇文章主要介紹了Spring Cloud Gateway重試機制的實現(xiàn),小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2019-03-03

最新評論