LeetCode 310: Minimum Yükseklikteki Ağaçlar
Bir LeetCode problemi için kodumu gönderiyorum, incelemek isterseniz, lütfen bunu yapın. Zaman ayırdığınız için teşekkür ederim!
Sorun
Ağaç özelliklerine sahip yönsüz bir grafik için, kök olarak herhangi bir düğümü seçebiliriz. Sonuç grafiği daha sonra köklü bir ağaçtır. Tüm olası köklü ağaçlar arasında minimum yüksekliği olanlara minimum yükseklikteki ağaçlar (MHT'ler) denir. Böyle bir grafik verildiğinde, tüm MHT'leri bulmak ve kök etiketlerinin bir listesini döndürmek için bir işlev yazın.
Biçim
Grafik, 0'dan n - 1'e kadar etiketlenmiş düğümler içerir. Size n sayısı ve yönlendirilmemiş kenarların bir listesi verilecektir (her kenar bir çift etikettir).
Kenarlarda yinelenen kenarların görünmeyeceğini varsayabilirsiniz. Tüm kenarlar yönlendirilmediğinden [0, 1], [1, 0] ile aynıdır ve bu nedenle kenarlarda birlikte görünmez.
Örnek 1 :
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
Output: [1]
Örnek 2:
Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
Output: [3, 4]
Not:
Wikipedia'daki ağacın tanımına göre: “ağaç, herhangi iki köşenin tam olarak bir yolla birbirine bağlandığı, yönsüz bir grafiktir. Diğer bir deyişle, basit döngüleri olmayan her bağlantılı grafik bir ağaçtır. " Köklü bir ağacın yüksekliği, kök ile bir yaprak arasındaki en uzun aşağı doğru yoldaki kenarların sayısıdır.
Kod
// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
return 0;
}();
// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
#include <unordered_set>
#include <algorithm>
static const struct Solution {
using ValueType = std::uint_fast16_t;
static const std::vector<int> findMinHeightTrees(
const int n,
const std::vector<std::vector<int>>& edges
) {
std::vector<int> buff_a;
std::vector<int> buff_b;
std::vector<int>* ptr_a = &buff_a;
std::vector<int>* ptr_b = &buff_b;
if (n == 1) {
buff_a.emplace_back(0);
return buff_a;
}
if (n == 2) {
buff_a.emplace_back(0);
buff_a.emplace_back(1);
return buff_a;
}
std::vector<Node> graph(n);
for (const auto& edge : edges) {
graph[edge[0]].neighbors.insert(edge[1]);
graph[edge[1]].neighbors.insert(edge[0]);
}
for (ValueType node = 0; node < n; ++node) {
if (graph[node].isLeaf()) {
ptr_a->emplace_back(node);
}
}
while (true) {
for (const auto& leaf : *ptr_a) {
for (const auto& node : graph[leaf].neighbors) {
graph[node].neighbors.erase(leaf);
if (graph[node].isLeaf()) {
ptr_b->emplace_back(node);
}
}
}
if (ptr_b->empty()) {
return *ptr_a;
}
ptr_a->clear();
std::swap(ptr_a, ptr_b);
}
}
private:
static const struct Node {
std::unordered_set<ValueType> neighbors;
const bool isLeaf() {
return std::size(neighbors) == 1;
}
};
};
Referanslar
Sorun
Tartışma
Wiki
Yanıtlar
Üç kat iç içe geçmiş döngüler her zaman korkutucu görünür. Özellikle while (true).
İlk önce kendinize güvenin. Yaprak düğümün (ve ptr_ayalnızca yaprakları içerir) yalnızca bir komşusu vardır.
for (const auto& node : graph[leaf].neighbors)
döngü etkilidir
auto& node = graph[leaf].neighbors.begin();
İkincisi, lütfen çıplak döngü olmasın. Ve daha fazla fonksiyon lütfen.
for (const auto& leaf : *ptr_a)
ağaçtan kuru erik yaprakları. prune_leavesYeni yaprakların bir kümesini (teknik olarak bir vektör) döndürecek bir fonksiyona çarpanını ayırın:
leaves = prune_leaves(leaves, graph);
Üçüncü olarak, 3 yapraktan daha az yaprak kaldığında dış döngü doğal olarak sona erecektir.
Son olarak, IO'yu iş mantığından ayırın. Bununla birlikte, satırları boyunca bir kod
graph = build_graph();
leaves = collect_leaves(graph);
while (leaves.size() < 3) {
leaves = prune_leaves(leaves, graph);
}
return leaves;
onayımı kazanacaktı. Bildirim nasıl ptr_ave ptr_b- en açıklayıcı değil isimleri hangi - kaybolur.