LeetCode 310: Cây có chiều cao tối thiểu
Đăng mã của tôi cho sự cố LeetCode, nếu bạn muốn xem lại, vui lòng làm như vậy. Cảm ơn bạn đã dành thời gian!
Vấn đề
Đối với đồ thị vô hướng có đặc điểm cây, chúng ta có thể chọn bất kỳ nút nào làm gốc. Biểu đồ kết quả sau đó là một cây gốc. Trong số tất cả các cây có rễ có thể có, những cây có chiều cao tối thiểu được gọi là cây có chiều cao tối thiểu (MHT). Cho một đồ thị như vậy, hãy viết một hàm để tìm tất cả các MHT và trả về một danh sách các nhãn gốc của chúng.
định dạng
Đồ thị chứa n nút được đánh nhãn từ 0 đến n - 1. Bạn sẽ được cung cấp số n và danh sách các cạnh vô hướng (mỗi cạnh là một cặp nhãn).
Bạn có thể cho rằng không có cạnh trùng lặp nào xuất hiện trong các cạnh. Vì tất cả các cạnh là vô hướng, [0, 1] giống với [1, 0] và do đó sẽ không xuất hiện cùng nhau trong các cạnh.
Ví dụ 1 :
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
Output: [1]
Ví dụ 2:
Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
Output: [3, 4]
Ghi chú:
Theo định nghĩa về cây trên Wikipedia: “Cây là một đồ thị vô hướng trong đó hai đỉnh bất kỳ được nối với nhau bằng đúng một đường đi. Nói cách khác, bất kỳ đồ thị liên thông nào không có các chu trình đơn giản đều là cây ”. Chiều cao của cây rễ là số cạnh trên đường đi xuống dài nhất giữa rễ và lá.
Mã
// 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;
}
};
};
Người giới thiệu
Vấn đề
Bàn luận
Wiki
Trả lời
Một vòng lặp lồng nhau ba lần luôn trông đáng sợ. Đặc biệt là với while (true).
Điều đầu tiên, hãy tin tưởng vào bản thân. Nút lá (và ptr_achỉ chứa các lá duy nhất) chỉ có một lân cận. Các
for (const auto& node : graph[leaf].neighbors)
vòng lặp có hiệu quả
auto& node = graph[leaf].neighbors.begin();
Thứ hai, xin vui lòng không có vòng lặp trần truồng. Và nhiều chức năng hơn xin vui lòng. Các
for (const auto& leaf : *ptr_a)
tỉa lá khỏi cây. Tính nó thành một prune_leaveshàm, hàm này sẽ trả về một tập hợp (về mặt kỹ thuật là một vectơ) các lá mới:
leaves = prune_leaves(leaves, graph);
Thứ ba, vòng ngoài sẽ tự nhiên kết thúc khi còn lại ít hơn 3 lá.
Cuối cùng, tách IO khỏi logic nghiệp vụ. Điều đó nói rằng, một đoạn mã dọc theo dòng
graph = build_graph();
leaves = collect_leaves(graph);
while (leaves.size() < 3) {
leaves = prune_leaves(leaves, graph);
}
return leaves;
sẽ giành được sự chứng thực của tôi. Chú ý làm thế nào ptr_avà ptr_b- không phải là những tên mô tả nhất - biến mất.