LeetCode 310 : 최소 높이 나무

Question

LeetCode 문제에 대한 내 코드 게시, 검토를 원하시면 그렇게 해주세요. 시간 내 주셔서 감사합니다!

문제

트리 특성이있는 무 방향 그래프의 경우 모든 노드를 루트로 선택할 수 있습니다. 결과 그래프는 루트 트리가됩니다. 가능한 모든 뿌리 나무 중에서 최소 높이를 가진 나무를 최소 높이 나무 (MHT)라고합니다. 이러한 그래프가 주어지면 모든 MHT를 찾고 루트 레이블 목록을 반환하는 함수를 작성하십시오.

체재

그래프에는 0에서 n-1까지 레이블이 지정된 n 개의 노드가 포함되어 있습니다. 숫자 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]

노트 :

Wikipedia의 나무 정의에 따르면 :“나무는 두 개의 정점이 정확히 하나의 경로로 연결된 무 방향 그래프입니다. 즉, 단순한주기가없는 연결된 그래프는 모두 트리입니다.” 뿌리 나무의 높이는 뿌리와 잎 사이의 가장 긴 아래쪽 경로의 가장자리 수입니다.

암호

// 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)

루프는 효과적으로

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-가장 설명적인 이름이 아닌-이 어떻게 사라지는 지 주목하십시오 .