LeetCode 310: Pohon Tinggi Minimum

Question

Memposting kode saya untuk masalah LeetCode, jika Anda ingin meninjau, silakan lakukan. Terima kasih atas waktu Anda!

Masalah

Untuk graf tak berarah dengan karakteristik pohon, kita bisa memilih sembarang simpul sebagai root. Grafik hasil kemudian menjadi pohon berakar. Di antara semua pohon yang mungkin berakar, pohon dengan tinggi minimum disebut pohon tinggi minimum (MHT). Dengan grafik seperti itu, tulis fungsi untuk menemukan semua MHT dan mengembalikan daftar label akarnya.

Format

Grafik berisi n node yang diberi label dari 0 sampai n - 1. Anda akan diberi nomor n dan daftar tepi yang tidak berarah (setiap tepi adalah sepasang label).

Anda dapat berasumsi bahwa tidak ada tepi duplikat yang akan muncul di tepi. Karena semua tepi tidak diarahkan, [0, 1] sama dengan [1, 0] dan karenanya tidak akan muncul bersama-sama di tepi.

Contoh 1 :

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

        0
        |
        1
       / \
      2   3 

Output: [1]

Contoh 2:

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

catatan:

Menurut definisi pohon di Wikipedia: “pohon adalah grafik yang tidak berarah di mana dua simpul dihubungkan oleh tepat satu jalur. Dengan kata lain, setiap grafik yang terhubung tanpa siklus sederhana adalah pohon. ” Tinggi pohon yang berakar adalah jumlah tepi pada jalur menurun terpanjang antara akar dan daun.

Kode

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

Referensi

• Masalah

• Bahas

• Wiki

Answer 1

Lingkaran bersarang tiga kali lipat selalu terlihat menakutkan. Apalagi dengan while (true).

Hal pertama yang pertama, percayalah pada diri sendiri. Simpul daun (dan yang ptr_ahanya berisi daun) hanya memiliki satu tetangga. Itu

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

loop secara efektif

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

Kedua, jangan lakukan loop telanjang. Dan lebih banyak fungsi tolong. Itu

for (const auto& leaf : *ptr_a)

plum daun dari pohon. Faktorkan menjadi sebuah prune_leavesfungsi, yang akan mengembalikan satu set (secara teknis adalah vektor) daun baru:

leaves = prune_leaves(leaves, graph);

Ketiga, lingkaran luar secara alami akan berhenti ketika kurang dari 3 daun yang tersisa.

Terakhir, pisahkan IO dari logika bisnis. Yang mengatakan, kode di sepanjang baris

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

akan memenangkan dukungan saya. Perhatikan bagaimana ptr_adan ptr_b- yang bukan merupakan nama yang paling deskriptif - menghilang.