👋
LeetCode 2020-11-04: Minimum Height Trees
LeetCode の daily problem に挑戦した記録です。
今日の問題は Minimum Height Trees (medium)。
問題の概要
- エッジ (辺) の配列で表現された閉路 (cycle) を持たないグラフ、すなわち木が与えられる
- このグラフ上の頂点のうち、その頂点を木のルートとしてみたときに高さ (ルートから最も遠い葉までの距離) が最小となる頂点を列挙する
考え方
- 前日までとは打って変わってちょっと難しい問題になった気がする…
- グラフアルゴリズムを駆使して任意のノード間の距離をすべて求め (空間計算量
O(n^2))、その結果を用いて頂点を列挙すればいいのだろうか… 🤔- いやいや、もっと簡単なアルゴリズムがありそうだ…
- あーなるほど、これは葉ノードを順に刈り取っていけばいいやつですね！
- 入力として与えられたグラフより、葉ノードに相当する頂点、すなわち次数が 1 の頂点を列挙する
- 列挙された頂点を削除しつつ、その頂点に連結している先の頂点の次数を 1 減らす
- 次数 1 の頂点を削除したグラフを次の入力として、1. の処理に戻って繰り返す。ただしグラフの頂点の数が一定数以下になったら処理を止める
- 上記の処理をループで回すとして、ループの停止条件を考えてみよう
- Hint にもあるけど minimum height trees のルートとなる頂点は果たしていくつ存在しうるのだろうか？
-
(0) - (1) - (2)みたいなグラフであれば 1 つ ((1)) になる -
(0) - (1) - (2) - (3)みたいなグラフであれば 2 つ ((1) - (2)) になる - 実は、どのグラフも葉ノードを刈り続けていくと、上記のどちらかのグラフに行き着く
-
- そういうわけで、minimum height trees になりうる頂点はグラフ中に最大でも 2 つしか存在し得ない
- ゆえに、ループの停止条件は「グラフ中の頂点数が 2 以下になった」となる
- Hint にもあるけど minimum height trees のルートとなる頂点は果たしていくつ存在しうるのだろうか？
- アルゴリズムは定まったのであとはこれをどうやって実装するかを考えてみよう
- エッジの配列だと扱いづらいので、隣接リスト でグラフを表現してみよう
- 処理の都合を考えると、
Map<Integer, Set<Integer>>で表すのがいいかな？- Map のキーが頂点の番号 (0 以上 n 未満)、
Setがその頂点に連結している他の頂点の番号を表す
- Map のキーが頂点の番号 (0 以上 n 未満)、
- この Map で保持する頂点のうち、連結する頂点の数が 1 となる (
Set#size() == 1となる) 頂点を削除対象として列挙する - 削除対象の頂点を削除する際に、それに連結する頂点の連結リスト (
Set) から削除される頂点を除去 (Set#remove()) しよう
- この HashMap/HashSet を使う方法で実装 → submit → 一発 accept 🤗
- Runtime はというと、112ms で
Your runtime beats 7.61 % of java submissions.😱 - ここまで遅いのはアルゴリズム的に筋が悪い、とかなのだろうか…
- Runtime はというと、112ms で
- HashMap/HashSet を使わない方法を考えてみよう
-
List<List<Integer>>で隣接リストを表すようにしよう- 外側のリストの添字が頂点の番号を表し、内側のリストで隣接する頂点の番号を保持する
- ここで葉ノードを削除する方法を改めてみる
- HashMap/HashSet を使う方法では、隣接する頂点を実際に
Setに入れて必要に応じて削除をしていたが実はこれは必ずしも必要な操作ではない - 要は、各頂点の次数を別途管理しておいてその次数が 1 となった頂点を削除対象として列挙していけばいい
- HashMap/HashSet を使う方法では、隣接する頂点を実際に
-
- 入れ子 List を使う方法で実装し直し → submit → accept 👍
- Runtime は 9ms まで縮められて
Your runtime beats 96.62 % of java submissions.まで来た！ - アルゴリズムの筋はそんなに悪くはなくて、よりオーバーヘッドの小さいデータ構造を採用するのがよさそうですね
- Runtime は 9ms まで縮められて
- さらなる改善
- List を使うとどうしても諸々のオーバーヘッドが生じがちなので、
int[][]で隣接リストを表現してみよう - ただし、各頂点に隣接する頂点の数を事前に把握する必要がある
- エッジ配列を先に走査して隣接する頂点の数を数えよう
- List を使うとどうしても諸々のオーバーヘッドが生じがちなので、
-
int[][]を使って実装 → submit → accept-
Your runtime beats 100.00 % of java submissions.達成 🎉 - あれ？ runtime は 4ms なんだけど、これはヒストグラム上の最速 6ms より速い結果になってるな…
-
コード
HashMap/HashSet を使う実装
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
Map<Integer, Set<Integer>> adjacenciesMap = new HashMap<>();
for (int i = 0; i < n; i++) {
adjacenciesMap.put(i, new HashSet<>());
}
for (int[] edge : edges) {
adjacenciesMap.get(edge[0]).add(edge[1]);
adjacenciesMap.get(edge[1]).add(edge[0]);
}
List<Map.Entry<Integer, Set<Integer>>> removedEntries = new ArrayList<>();
while (adjacenciesMap.size() > 2) {
removedEntries.clear();
for (Iterator<Map.Entry<Integer, Set<Integer>>> i = adjacenciesMap.entrySet().iterator(); i.hasNext(); ) {
Map.Entry<Integer, Set<Integer>> entry = i.next();
Set<Integer> adjacencies = entry.getValue();
if (adjacencies.size() == 1) {
removedEntries.add(entry);
i.remove();
}
}
for (Map.Entry<Integer, Set<Integer>> entry : removedEntries) {
adjacenciesMap.get(entry.getValue().iterator().next()).remove(entry.getKey());
}
}
return new ArrayList<>(adjacenciesMap.keySet());
}
}
入れ子 List を使う実装
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) {
return Collections.singletonList(0);
}
List<List<Integer>> adjacencyLists = new ArrayList<>();
for (int i = 0; i < n; i++) {
adjacencyLists.add(new ArrayList<>());
}
for (int[] edge : edges) {
adjacencyLists.get(edge[0]).add(edge[1]);
adjacencyLists.get(edge[1]).add(edge[0]);
}
int[] numEdges = new int[n];
List<Integer> leaves = new ArrayList<>();
for (int i = 0, limit = adjacencyLists.size(); i < limit; i++) {
List<Integer> list = adjacencyLists.get(i);
numEdges[i] = list.size();
if (numEdges[i] == 1) {
leaves.add(i);
}
}
int numNodesRemaining = n;
List<Integer> nextLeaves = new ArrayList<>();
while (numNodesRemaining > 2) {
for (int leaf : leaves) {
List<Integer> list = adjacencyLists.get(leaf);
for (int index : list) {
if (--numEdges[index] == 1) {
nextLeaves.add(index);
}
}
}
numNodesRemaining -= leaves.size();
List<Integer> t = leaves;
leaves = nextLeaves;
nextLeaves = t;
nextLeaves.clear();
}
return leaves;
}
}
int[][] を使う実装
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) {
return Collections.singletonList(0);
}
int[] numEdges = new int[n];
for (int[] edge : edges) {
numEdges[edge[0]]++;
numEdges[edge[1]]++;
}
int[][] adjacencyArrays = new int[n][];
for (int i = 0; i < n; i++) {
adjacencyArrays[i] = new int[numEdges[i]];
}
int[] work = new int[n];
for (int[] edge : edges) {
adjacencyArrays[edge[0]][work[edge[0]]++] = edge[1];
adjacencyArrays[edge[1]][work[edge[1]]++] = edge[0];
}
int leafCount = 0;
for (int i = 0; i < n; i++) {
if (work[i] == 1) {
work[leafCount++] = i;
}
}
int[] work2 = new int[n];
int nextLeafCount;
int numNodesRemaining = n;
while (numNodesRemaining > 2) {
nextLeafCount = 0;
for (int i = 0; i < leafCount; i++) {
int leaf = work[i];
for (int index : adjacencyArrays[leaf]) {
if (--numEdges[index] == 1) {
work2[nextLeafCount++] = index;
}
}
}
numNodesRemaining -= leafCount;
int[] w = work;
work = work2;
work2 = w;
leafCount = nextLeafCount;
}
return leafCount == 2 ? Arrays.asList(work[0], work[1]) : Collections.singletonList(work[0]);
}
}
Discussion