資訊專欄INFORMATION COLUMN
摘要：題目鏈接圖的題，和差不多。來解，每次放入只有一個的現(xiàn)在的。然后直到只剩最上面一層。注意考慮多帶帶的和別的不相連。比如這種情況，就有三個點都不和別的相連。還有的時候就要返回。
Minimum Height Trees
題目鏈接：https://leetcode.com/problems...
圖的題，和course schedule差不多。bfs來解，每次放入只有一個edge的node（現(xiàn)在的leaf）。然后直到只剩最上面一層。注意考慮多帶帶的node（和別的node不相連）。比如: [[1,2], [2,3]], n = 6這種情況，就有[0, 4, 5]三個點都不和別的node相連。還有[], n = 2的時候就要返回[0, 1]。
public class Solution {
public List findMinHeightTrees(int n, int[][] edges) {
// adjacent set
Set[] set = new HashSet[n];
for(int i = 0; i < n; i++) set[i] = new HashSet();
for(int[] edge : edges) {
set[edge[0]].add(edge[1]);
set[edge[1]].add(edge[0]);
}
// use queue to do bfs
LinkedList q = new LinkedList();
List edge_case = new ArrayList();
for(int i = 0; i < set.length; i++) {
if(set[i].size() == 1) q.add(i);
if(set[i].size() == 0) edge_case.add(i);
}
// if cycle
if(q.size() == 0) return edge_case;
int count = edge_case.size();
while(count + q.size() < n) {
int size = q.size();
count += size;
while(size-- > 0) {
int node = q.remove();
int parent = set[node].iterator().next();
set[node].remove(parent);
set[parent].remove(node);
if(set[parent].size() == 1) q.add(parent);
}
}
return q;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66635.html
摘要：可以從頭邊同時進(jìn)行，查看葉子節(jié)點并加入到葉子節(jié)點鏈表遍歷一遍后，葉子節(jié)點鏈表為。將葉子節(jié)點保存下來。這個時候就會有第二層葉子節(jié)點那些在列表當(dāng)中為的點，用同樣的方法進(jìn)行剝除。最后留在葉子節(jié)點里面的點即可以為根。 題目： For a undirected graph with tree characteristics, we can choose any node as the root...
摘要：現(xiàn)在要求在這樣一棵生成樹中，找到生成樹的高度最低的所有根節(jié)點。然后利用鄰接表的相關(guān)屬性來判斷當(dāng)前節(jié)點是否是葉節(jié)點。度數(shù)為一的頂點就是葉節(jié)點。這里使用異或的原因是對同一個值進(jìn)行兩次異或即可以回到最初值。 題目 For an undirected graph with tree characteristics, we can choose any node as the root. The...
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 ...
摘要：所以這篇文章希望幫助大家理解一下。我沒有在算法上展開太多，因為很多算法相似，如果展開容易喧賓奪主。等過段時間我會加入一些實驗數(shù)據(jù)和代碼進(jìn)這篇文章，最近比較懶不想安裝數(shù)據(jù)庫安裝實在太煩了。 這是我寫的一篇研究生申請的writing sample，關(guān)于數(shù)據(jù)庫索引的，對關(guān)系型數(shù)據(jù)庫的索引從數(shù)據(jù)結(jié)構(gòu)到用途再到作用對象簡單分析了一下，因為我發(fā)現(xiàn)在實際工作中，index是個好東西，但是很多DBA并...
閱讀 1772·2021-11-24 09:39
閱讀 1571·2021-11-16 11:54
閱讀 3509·2021-11-11 16:55
閱讀 1682·2021-10-14 09:43
閱讀 1456·2019-08-30 15:55
閱讀 1247·2019-08-30 15:54
閱讀 3434·2019-08-30 15:53
閱讀 1352·2019-08-30 14:18
