資訊專欄INFORMATION COLUMN
摘要：題目鏈接圖的題，和差不多。來(lái)解，每次放入只有一個(gè)的現(xiàn)在的。然后直到只剩最上面一層。注意考慮多帶帶的和別的不相連。比如這種情況，就有三個(gè)點(diǎn)都不和別的相連。還有的時(shí)候就要返回。
Minimum Height Trees
題目鏈接：https://leetcode.com/problems...
圖的題，和course schedule差不多。bfs來(lái)解，每次放入只有一個(gè)edge的node（現(xiàn)在的leaf）。然后直到只剩最上面一層。注意考慮多帶帶的node（和別的node不相連）。比如: [[1,2], [2,3]], n = 6這種情況，就有[0, 4, 5]三個(gè)點(diǎn)都不和別的node相連。還有[], n = 2的時(shí)候就要返回[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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/66635.html
摘要：可以從頭邊同時(shí)進(jìn)行，查看葉子節(jié)點(diǎn)并加入到葉子節(jié)點(diǎn)鏈表遍歷一遍后，葉子節(jié)點(diǎn)鏈表為。將葉子節(jié)點(diǎn)保存下來(lái)。這個(gè)時(shí)候就會(huì)有第二層葉子節(jié)點(diǎn)那些在列表當(dāng)中為的點(diǎn)，用同樣的方法進(jìn)行剝除。最后留在葉子節(jié)點(diǎn)里面的點(diǎn)即可以為根。 題目： For a undirected graph with tree characteristics, we can choose any node as the root...
摘要：現(xiàn)在要求在這樣一棵生成樹中，找到生成樹的高度最低的所有根節(jié)點(diǎn)。然后利用鄰接表的相關(guān)屬性來(lái)判斷當(dāng)前節(jié)點(diǎn)是否是葉節(jié)點(diǎn)。度數(shù)為一的頂點(diǎn)就是葉節(jié)點(diǎn)。這里使用異或的原因是對(duì)同一個(gè)值進(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 ...
摘要：所以這篇文章希望幫助大家理解一下。我沒(méi)有在算法上展開太多，因?yàn)楹芏嗨惴ㄏ嗨?，如果展開容易喧賓奪主。等過(guò)段時(shí)間我會(huì)加入一些實(shí)驗(yàn)數(shù)據(jù)和代碼進(jìn)這篇文章，最近比較懶不想安裝數(shù)據(jù)庫(kù)安裝實(shí)在太煩了。 這是我寫的一篇研究生申請(qǐng)的writing sample，關(guān)于數(shù)據(jù)庫(kù)索引的，對(duì)關(guān)系型數(shù)據(jù)庫(kù)的索引從數(shù)據(jù)結(jié)構(gòu)到用途再到作用對(duì)象簡(jiǎn)單分析了一下，因?yàn)槲野l(fā)現(xiàn)在實(shí)際工作中，index是個(gè)好東西，但是很多DBA并...
閱讀 1837·2021-11-24 09:39
閱讀 1634·2021-11-16 11:54
閱讀 3588·2021-11-11 16:55
閱讀 1827·2021-10-14 09:43
閱讀 1507·2019-08-30 15:55
閱讀 1295·2019-08-30 15:54
閱讀 3484·2019-08-30 15:53
閱讀 1435·2019-08-30 14:18
