LeetCode 310: Alberi ad altezza minima

Aug 20 2020

Inserendo il mio codice per un problema con LeetCode, se desideri esaminarlo, fallo. Grazie per il tuo tempo!

Problema

Per un grafo non orientato con caratteristiche ad albero, possiamo scegliere qualsiasi nodo come radice. Il grafico del risultato è quindi un albero con radici. Tra tutti i possibili alberi radicati, quelli con altezza minima sono chiamati alberi di altezza minima (MHT). Dato un tale grafico, scrivi una funzione per trovare tutti gli MHT e restituire un elenco delle loro etichette radice.

Formato

Il grafico contiene n nodi che sono etichettati da 0 an - 1. Ti verrà dato il numero ne un elenco di bordi non orientati (ogni bordo è una coppia di etichette).

Puoi presumere che nessun bordo duplicato apparirà nei bordi. Poiché tutti i bordi non sono orientati, [0, 1] è uguale a [1, 0] e quindi non apparirà insieme nei bordi.

Esempio 1 :

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

Output: [1]

Esempio 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:

Secondo la definizione di albero su Wikipedia: “un albero è un grafo non orientato in cui due vertici qualsiasi sono collegati da esattamente un percorso. In altre parole, qualsiasi grafo connesso senza cicli semplici è un albero ". L'altezza di un albero radicato è il numero di bordi sul percorso discendente più lungo tra la radice e una foglia.

Codice

// 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;
            }
        };
};


Riferimenti

  • Problema

  • Discutere

  • Wiki

Risposte

2 vnp Aug 21 2020 at 00:20

Un triplo anello annidato sembra sempre spaventoso. Soprattutto con while (true).

Per prima cosa, fidati di te stesso. Il nodo foglia (e ptr_acontiene solo foglie) ha un solo vicino. Il

for (const auto& node : graph[leaf].neighbors)

loop è efficace

auto& node = graph[leaf].neighbors.begin();

Secondo, niente loop nudi per favore. E altre funzioni per favore. Il

for (const auto& leaf : *ptr_a)

prugne foglie dall'albero. Fattorizzalo in una prune_leavesfunzione, che restituirebbe un insieme (tecnicamente un vettore) delle nuove foglie:

leaves = prune_leaves(leaves, graph);

Terzo, l'anello esterno terminerà naturalmente quando rimangono meno di 3 foglie.

Infine, separa l'IO dalla logica di business. Detto questo, un codice sulla falsariga di

    graph = build_graph();
    leaves = collect_leaves(graph);
    while (leaves.size() < 3) {
        leaves = prune_leaves(leaves, graph);
    }
    return leaves;

avrebbe vinto la mia approvazione. Notare come ptr_ae ptr_b- che non sono i nomi più descrittivi - scompaiono.