LeetCode 310: ต้นไม้ความสูงขั้นต่ำ

Question

การโพสต์รหัสของฉันสำหรับปัญหา LeetCode หากคุณต้องการตรวจสอบโปรดดำเนินการดังกล่าว ขอขอบคุณสำหรับเวลาของคุณ!

ปัญหา

สำหรับกราฟที่ไม่มีทิศทางที่มีลักษณะแบบต้นไม้เราสามารถเลือกโหนดใดก็ได้เป็นรูท จากนั้นกราฟผลลัพธ์จะเป็นต้นไม้ที่ถูกรูท ในบรรดาต้นไม้ที่มีรากที่เป็นไปได้ทั้งหมดต้นไม้ที่มีความสูงต่ำสุดเรียกว่าต้นไม้ที่มีความสูงต่ำสุด (MHTs) จากกราฟดังกล่าวให้เขียนฟังก์ชันเพื่อค้นหา MHT ทั้งหมดและส่งคืนรายการป้ายกำกับราก

รูปแบบ

กราฟประกอบด้วยโหนดที่มีป้ายกำกับตั้งแต่ 0 ถึง n - 1 คุณจะได้รับหมายเลข n และรายการของขอบที่ไม่ได้กำหนดทิศทาง (ขอบแต่ละด้านคือคู่ของป้ายกำกับ)

คุณสามารถสันนิษฐานได้ว่าจะไม่มีขอบที่ซ้ำกันปรากฏในขอบ เนื่องจากขอบทั้งหมดไม่มีการกำหนดทิศทาง [0, 1] จึงเหมือนกับ [1, 0] ดังนั้นจึงจะไม่ปรากฏร่วมกันที่ขอบ

ตัวอย่างที่ 1:

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

        0
        |
        1
       / \
      2   3 

Output: [1]

ตัวอย่างที่ 2:

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

บันทึก:

ตามคำจำกัดความของต้นไม้ในวิกิพีเดีย:“ ต้นไม้คือกราฟที่ไม่มีทิศทางซึ่งจุดยอดสองจุดเชื่อมต่อกันด้วยเส้นทางเดียว กล่าวอีกนัยหนึ่งกราฟที่เชื่อมต่อโดยไม่มีวัฏจักรง่ายๆก็คือต้นไม้” ความสูงของต้นไม้ที่หยั่งรากคือจำนวนของขอบบนทางลงที่ยาวที่สุดระหว่างรากและใบไม้

รหัส

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

อ้างอิง

• ปัญหา

• อภิปราย

• วิกิ

Answer 1

ลูปที่ซ้อนกันสามเท่ามักดูน่ากลัว while (true)โดยเฉพาะอย่างยิ่งกับ

สิ่งแรกแรกเชื่อตัวเอง โหนดใบไม้ (และptr_aมีเฉพาะใบไม้) มีเพื่อนบ้านเพียงคนเดียว

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

loop ได้อย่างมีประสิทธิภาพ

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

ประการที่สองโปรดอย่าลูปเปล่า และฟังก์ชั่นอื่น ๆ โปรด

for (const auto& leaf : *ptr_a)

ลูกพรุนออกจากต้นไม้ แยกตัวประกอบออกเป็นprune_leavesฟังก์ชันซึ่งจะส่งคืนเซต (ในทางเทคนิคคือเวกเตอร์) ของใบไม้ใหม่:

leaves = prune_leaves(leaves, graph);

ประการที่สามวงนอกจะสิ้นสุดลงตามธรรมชาติเมื่อเหลือน้อยกว่า 3 ใบ

สุดท้ายแยก IO ออกจากตรรกะทางธุรกิจ ที่กล่าวว่าเป็นรหัสตามบรรทัดของ

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

จะชนะการรับรองของฉัน สังเกตว่าptr_aและptr_b- ซึ่งไม่ใช่ชื่อที่อธิบายได้มากที่สุด - หายไปอย่างไร