LeetCode 310: Bäume mit minimaler Höhe

Question

Wenn Sie meinen Code für ein LeetCode-Problem veröffentlichen möchten, tun Sie dies bitte. Vielen Dank für Ihre Zeit!

Problem

Für ein ungerichtetes Diagramm mit Baummerkmalen können wir einen beliebigen Knoten als Wurzel auswählen. Das Ergebnisdiagramm ist dann ein Wurzelbaum. Unter allen möglichen Wurzelbäumen werden Bäume mit minimaler Höhe als Bäume mit minimaler Höhe (MHTs) bezeichnet. Schreiben Sie in einem solchen Diagramm eine Funktion, um alle MHTs zu finden und eine Liste ihrer Stammbezeichnungen zurückzugeben.

Format

Das Diagramm enthält n Knoten, die von 0 bis n - 1 beschriftet sind. Sie erhalten die Nummer n und eine Liste ungerichteter Kanten (jede Kante ist ein Beschriftungspaar).

Sie können davon ausgehen, dass in Kanten keine doppelten Kanten angezeigt werden. Da alle Kanten ungerichtet sind, ist [0, 1] dasselbe wie [1, 0] und wird daher nicht zusammen in Kanten angezeigt.

Beispiel 1 :

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

        0
        |
        1
       / \
      2   3 

Output: [1]

Beispiel 2:

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

Hinweis:

Gemäß der Definition von Baum in Wikipedia: „Ein Baum ist ein ungerichteter Graph, in dem zwei beliebige Eckpunkte durch genau einen Pfad verbunden sind. Mit anderen Worten, jeder verbundene Graph ohne einfache Zyklen ist ein Baum. “ Die Höhe eines Wurzelbaums ist die Anzahl der Kanten auf dem längsten Abwärtspfad zwischen der Wurzel und einem Blatt.

Code

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

Verweise

• Problem

• Diskutieren

• Wiki

Answer 1

Dreifach verschachtelte Schleifen sehen immer beängstigend aus. Besonders mit while (true).

Als erstes vertraue dir selbst. Der Blattknoten (und der ptr_aenthält nur Blätter) hat nur einen Nachbarn. Das

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

Schleife ist effektiv

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

Zweitens bitte keine nackten Schleifen. Und noch mehr Funktionen bitte. Das

for (const auto& leaf : *ptr_a)

Pflaumenblätter vom Baum. Berücksichtigen Sie dies in einer prune_leavesFunktion, die eine Menge (technisch gesehen einen Vektor) der neuen Blätter zurückgibt:

leaves = prune_leaves(leaves, graph);

Drittens soll die äußere Schleife natürlich enden, wenn weniger als 3 Blätter übrig sind.

Trennen Sie schließlich IO von der Geschäftslogik. Das heißt, ein Code nach dem Vorbild von

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

würde meine Unterstützung gewinnen. Beachten Sie, wie ptr_aund ptr_b- was nicht die aussagekräftigsten Namen sind - verschwinden.