- 浏览: 173235 次
- 性别:
- 来自: 济南
文章分类
最新评论
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.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
return [3, 4]
一道图的题目,我们可以每次都删除叶子节点,维护一个入度为1的队列,删除叶子节点的同时,将新的入度为0的及诶单更新到队列中,直到最后剩下一个或两个节点。代码如下:
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.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
return [3, 4]
一道图的题目,我们可以每次都删除叶子节点,维护一个入度为1的队列,删除叶子节点的同时,将新的入度为0的及诶单更新到队列中,直到最后剩下一个或两个节点。代码如下:
public class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { List<Integer>[] graph = new List[n]; Queue<Integer> queue = new LinkedList<Integer>(); List<Integer> list = new ArrayList<Integer>(); int[] degree = new int[n]; if(n == 1) { list.add(0); return list; } if(edges == null || edges.length == 0) return list; for(int i = 0; i < edges.length; i++) { if(graph[edges[i][0]] == null) graph[edges[i][0]] = new ArrayList<Integer>(); graph[edges[i][0]].add(edges[i][1]); if(graph[edges[i][1]] == null) graph[edges[i][1]] = new ArrayList<Integer>(); graph[edges[i][1]].add(edges[i][0]); degree[edges[i][0]] ++; degree[edges[i][1]] ++; } for(int i = 0; i < degree.length; i++) { if(degree[i] == 0) return list; if(degree[i] == 1) queue.offer(i); } while(!queue.isEmpty()) { list = new ArrayList<Integer>(); int count = queue.size(); for(int i = 0; i < count; i++){ int tem = queue.poll(); list.add(tem); degree[tem] --; for(int v : graph[tem]) { if(degree[v] == 0) continue; if(degree[v] == 2) queue.offer(v); degree[v] --; } } } return list; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 225Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 223You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 340Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 331Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 449Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 509Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 428Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 385Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 367All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 859Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 880Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Bulb Switcher
2016-02-28 12:12 347There are n bulbs that are init ...
相关推荐
Tall Paul
Minimum-cost Spanning Trees.docx
Minimum_Cut_Tree_Games解答
NULL 博文链接:https://shmilyaw-hotmail-com.iteye.com/blog/2010747
画流程图 \documentclass[UTF8]{ctexart} \usepackage{tikz} \usetikzlibrary{shapes,arrows} \begin{document} \tikzstyle{startstop} = [rectangle,rounded corners, minimum width=3cm,minimum height=1cm,text ...
本文设计了一个分布式的算法用于解决最小生成树的求解问题。该方案可以应用于传感器网络WSN或者其他的分布式系统优化中。
MinimumSpanningTree,最小生成树,编程语言Java
北大POJ2516-Minimum Cost 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6742534
Minimum mean square error method for stripe nonuniformity correction 是关于红外图像非均匀性校正的论文
Minimum Snap轨迹规划详解(1)轨迹规划入门
Finding fuction minimum and maximum
Minimum realization是最小化实现,希望对大家有用。
matlab开发-MinimumSpanningTree。用Matlab中的PSO、ICA和FA求解最小生成树
1. QP等式约束构建 2. 如何求d 3. 闭式法步骤 1. 先确定轨迹阶数(比如5阶),再确定 向量中的约束量(pva),进而根据各段的时间分配求得 2.
A method for the construction of minimum-redundancy codes
创建一个一定范围内的最小堆,可以进行堆排序、插入、删除、添加的操作
A Tutorial Introduction to the Minimum Description Length Principle
最小冗余阵提出阐述,RTRTRTRTRTRTRTRTRTRTRTRTRTRTRTRTRT
这是关于机器学习的电子书,高清,最新版本,经典著作,英文版