力扣(LeetCode)310

栏目: 编程工具 · 发布时间: 6年前

内容简介:题目地址:题目描述:

题目地址:

https://leetcode-cn.com/probl...

题目描述:

对于一个具有树特征的无向图,我们可选择任何一个节点作为根。图因此可以成为树,在所有可能的树中,具有最小高度的树被称为最小高度树。给出这样的一个图,写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点,标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表(每一个边都是一对标签)。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边, [0, 1]和 [1, 0] 是相同的,因此不会同时出现在 edges 里。

解答:

这一题就是求最短路径,不过求的是每一个点到任意一点的最短路径。

我们可以使用 弗洛伊德 算法来求解。可惜的是该算法的复杂度是O(N三次方)。

不过还有别的方法来求最短路径,宽度优先搜索,对于权值相同的图,可以用宽度优先搜索来求解某一点到

任意一点的最短路径。宽度优先是O(N)的复杂度。求解N个点的,于是就可以把复杂度变为O(N二次方)。

注意:下面的代码是隐含使用宽度优先搜索,没有使用队列。

java ac代码:

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    
        int[][] matrix = new int[n][n];
        int max = Integer.MAX_VALUE;
         for(int i = 0;i < n;i++)
            for(int j = 0;j < n;j++)
                matrix[i][j] = max;
        
         for(int i = 0;i < edges.length;i++){
            int begin = edges[i][0];
            int end = edges[i][1];  
            matrix[begin][end] = 1;
            matrix[end][begin] = 1;
            for(int j = 0;j < n;j++)
                if(matrix[begin][j] == max&&matrix[end][j] != max)
                    matrix[begin][j] = matrix[j][begin] = 1+matrix[end][j];
                else if(matrix[end][j] == max&&matrix[begin][j] != max)
                    matrix[end][j] = matrix[j][end] = 1+matrix[begin][j];
                    
         }
        
         for(int i = 0;i < n;i++)
            matrix[i][i] = 0;
                         
         
         
          
           HashMap<Integer,Integer>map = new HashMap(1<<10);
           int min = max;  
          for(int i = 0;i < n;i++){
               int temp = -1;
               for(int j = 0;j < n;j++)
               temp = Math.max(temp,matrix[i][j]);
               map.put(i,temp);
              min = Math.min(temp,min);
            }
           List<Integer> ans = new ArrayList(n);
           for(Map.Entry<Integer,Integer> entry:map.entrySet())
               if(entry.getValue() == min)ans.add(entry.getKey());
        
        
        return ans;
    }
    
    
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

ActionScript 3.0 Cookbook

ActionScript 3.0 Cookbook

Joey Lott、Darron Schall、Keith Peters / Adobe Dev Library / 2006-10-11 / GBP 28.50

Well before Ajax and Microsoft's Windows Presentation Foundation hit the scene, Macromedia offered the first method for building web pages with the responsiveness and functionality of desktop programs......一起来看看 《ActionScript 3.0 Cookbook》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具