😊

LeetCoding Challenge Oct. 20: Clone Graph

2020/10/20に公開

Java

LeetCode

tech

LeetCode October Challenge の 20 日目。

今日の問題は Clone Graph。

問題の概要

与えられた無向グラフを deep copy し、その結果を返す

考え方

簡単なグラフトラバーサルの問題ですね 😇
- これもこれで、仕事でこういうタスクをこなすことはほとんどないけどな…
リストにしてもツリーにしても、テストケースを効率よく試す仕組みづくりに時間がかかるよね…
- 今回は以下のようなヘルパークラスを作り、グラフの文字列表現から Node オブジェクトをさくっと生成できるようにしたよ ♪

public class GraphHelper {
    static final Pattern PATTERN = Pattern.compile("\\[(|\\d+(,\\d)*)]");

    public static Node generateFromString(String str) {
        if (str.equals("[]")) {
            return null;
        }

        int[][] adjacencies = PATTERN.matcher(str).results()
                .map(matchResult -> matchResult.group(1))
                .map(s -> Arrays.stream(s.split(","))
                        .filter(t -> !t.isEmpty())
                        .mapToInt(Integer::valueOf).toArray())
                .toArray(int[][]::new);

        Node[] nodes = IntStream.range(0, adjacencies.length)
                .map(i -> i + 1)
                .mapToObj(Node::new)
                .toArray(Node[]::new);

        for (int i = 0; i < adjacencies.length; i++) {
            Node node = nodes[i];
            for (int j = 0; j < adjacencies[i].length; j++) {
                node.neighbors.add(nodes[adjacencies[i][j] - 1]);
            }
        }

        return nodes[0];
    }

    public static String toString(Node _node) {
        if (_node == null) {
            return "[]";
        }

        SortedSet<Node> nodes = new TreeSet<>(Comparator.comparingInt(o -> o.val));
        nodes.add(_node);

        Queue<Node> queue = new LinkedList<>();
        queue.add(_node);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            for (Node neighbor : node.neighbors) {
                if (nodes.add(neighbor)) {
                    queue.add(neighbor);
                }
            }
        }

        return nodes.stream()
                .map(n -> n.neighbors
                        .stream()
                        .map(nn -> String.valueOf(nn.val))
                        .collect(Collectors.joining(",", "[", "]")))
                .collect(Collectors.joining(",", "[", "]"));
    }

    public static class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return val == node.val;
        }

        @Override
        public int hashCode() {
            return Objects.hash(val);
        }
    }
}

さて肝心の問題はというと、まあ幅優先探索でいいよね
- 訪問すべき頂点を保持する Queue と、エンキュー済みの頂点を記録しておく Set の２つが必要になるね
- Runtime を最小にしたいので、トラバーサルは one-pass で実現しよう 💪
  - 新しい頂点に遭遇したところでその頂点のクローンを生成し、node.val の値でルックアップできる何かしらのデータ構造に生成した頂点のオブジェクトを放り込んで管理しよう
新しい頂点を保持するデータ構造は、愚直に真面目にやるなら node.val をキーに、node そのものを値とするマップ Map<Integer, Node> を構築するやり方になるかな？
- でも、問題の constraints にあるとおりノード数は最大でも 100 個、node.val は一意であり、かつ 1 以上 10 未満だそうなので、この制約を利用すればもっと手抜きができるね
- 具体的には、長さ 101 の Node の配列を作っておいて、それをマップ代わりに使っちゃうよ 🥴
  - 業務コードだとこういうコードはあまり書きたくないけど、速度重視でいくには Map#get() や Map#put() よりも、配列へのランダムアクセスの方が効率がいいはずだし…
なお新しい頂点を保持するデータ構造を使えば、エンキュー済みの頂点かどうかのチェックもこのデータ構造で代用できるね
そういうわけで実装 → submit → 一発 accept 👍
- Runtime は 24ms で、Your runtime beats 99.60 % of java submissions. 🤗
最速の 23ms のサンプルコードを見てみると two-pass で処理していて、なんでこれで最速になるのかがさっぱりわからない… 🤔

コード

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }

        Node[] newNodes = new Node[101];
        newNodes[node.val] = new Node(node.val);

        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        while (!queue.isEmpty()) {
            Node n = queue.poll();

            for (Node neighbor : n.neighbors) {
                if (newNodes[neighbor.val] == null) {
                    newNodes[neighbor.val] = new Node(neighbor.val);
                    queue.add(neighbor);
                }
                newNodes[n.val].neighbors.add(newNodes[neighbor.val]);
            }
        }

        return newNodes[1];
    }
}

問題の概要

考え方

コード

Discussion