LeetCode 310：最小の高さの木
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]
注意：
ウィキペディアのツリーの定義によると、「ツリーは、任意の2つの頂点が正確に1つのパスで接続されている無向グラフです。言い換えれば、単純なサイクルのない接続されたグラフはすべてツリーです。」根付いた木の高さは、根と葉の間の最長の下向きパス上のエッジの数です。
コード
// 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;
}
};
};
参考文献
問題
話し合います
ウィキ
回答
三重にネストされたループは常に怖いように見えます。特にwhile (true)。
まず最初に、自分を信頼してください。リーフノード（およびリーフptr_aのみを含む）には、隣接ノードが1つだけあります。ザ・
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_aandがどのようにptr_b消えるかに注意してください。