LeetCode 310: Árboles de altura mínima
Publicando mi código para un problema de LeetCode, si desea revisarlo, hágalo. ¡Gracias por tu tiempo!
Problema
Para un gráfico no dirigido con características de árbol, podemos elegir cualquier nodo como raíz. El gráfico de resultado es entonces un árbol enraizado. Entre todos los posibles árboles enraizados, los que tienen una altura mínima se denominan árboles de altura mínima (MHT). Dado ese gráfico, escriba una función para encontrar todos los MHT y devuelva una lista de sus etiquetas raíz.
Formato
El gráfico contiene n nodos que están etiquetados de 0 a n - 1. Se le dará el número n y una lista de bordes no dirigidos (cada borde es un par de etiquetas).
Puede asumir que no aparecerán bordes duplicados en los bordes. Dado que todos los bordes no están dirigidos, [0, 1] es lo mismo que [1, 0] y, por tanto, no aparecerán juntos en los bordes.
Ejemplo 1 :
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
Output: [1]
Ejemplo 2:
Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
Output: [3, 4]
Nota:
Según la definición de árbol en Wikipedia: “un árbol es un gráfico no dirigido en el que dos vértices cualesquiera están conectados por exactamente una ruta. En otras palabras, cualquier gráfico conectado sin ciclos simples es un árbol ". La altura de un árbol enraizado es el número de bordes en el camino descendente más largo entre la raíz y una hoja.
Código
// 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;
}
};
};
Referencias
Problema
Discutir
Wiki
Respuestas
Un bucle triplemente anidado siempre da miedo. Especialmente con while (true)
.
Lo primero es lo primero, confía en ti mismo. El nodo hoja (y ptr_a
contiene solo hojas) tiene solo un vecino. los
for (const auto& node : graph[leaf].neighbors)
bucle es efectivamente
auto& node = graph[leaf].neighbors.begin();
En segundo lugar, no hay bucles desnudos, por favor. Y más funciones por favor. los
for (const auto& leaf : *ptr_a)
ciruelas pasas del árbol. Factorizarlo en una prune_leaves
función, que devolvería un conjunto (técnicamente un vector) de las nuevas hojas:
leaves = prune_leaves(leaves, graph);
En tercer lugar, el bucle exterior terminará naturalmente cuando queden menos de 3 hojas.
Finalmente, separe la IO de la lógica empresarial. Dicho esto, un código similar a
graph = build_graph();
leaves = collect_leaves(graph);
while (leaves.size() < 3) {
leaves = prune_leaves(leaves, graph);
}
return leaves;
ganaría mi respaldo. Observe cómo ptr_a
y ptr_b
, que no son los nombres más descriptivos, desaparecen.