2

この問題https://www.hackerrank.com/challenges/cut-the-treeを解決しようとするとき、 私は常に葉を選んで切り取り、その重みをそれが接続するノードに結合しようとしていました。PriorityQueue を使用してすべてのノードを格納し、隣接するノードのサイズを優先度として使用していました。しかし、いくつかのテスト ケースを試していると、優先キュー プロパティに違反しているように見えます。つまり、非リーフ ノードがリーフ ノードの前に表示される可能性があります。PriorityQueue は自動的に更新されますか、それとも更新する関数を呼び出す必要がありますか。私の一時的な解決策は、リストを使用してすべての葉を保存することです。

以下は私のコードです：

public class Solution {
    private static class Node implements Comparable<Node> {
        int index;
        int value;
        Map<Integer, Node> adj;

        public Node(int index, int value) {
            this.index = index;
            this.value = value;
            this.adj = new HashMap<Integer, Node>();
        }

        @Override
        public int compareTo(Node n) {
            return adj.size() - n.adj.size();
        }
    }

    public static void main(String[] args) {

        BufferedReader br = null;
        try {
            br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));

            int total = 0;

            int N = Integer.parseInt(br.readLine());
            String[] strs = br.readLine().split(" ");
            HashMap<Integer, Node> nodes = new HashMap<Integer, Node>();

            for (int i = 0; i < N; i++) {
                int value = Integer.parseInt(strs[i]);
                nodes.put(i, new Node(i, value));
                total += value;
            }

            for (int i = 0; i < N - 1; i++) {
                strs = br.readLine().split(" ");
                int n1 = Integer.parseInt(strs[0]) - 1;
                int n2 = Integer.parseInt(strs[1]) - 1;

                nodes.get(n1).adj.put(n2, nodes.get(n2));
                nodes.get(n2).adj.put(n1, nodes.get(n1));
            }

            // PriorityQueue<Node> pq = new PriorityQueue<Node>(nodes.values());
            // while (!pq.isEmpty()) {
            // Node n = pq.poll();
            // System.out.println(n.index + " " + n.adj.size());
            // }
            // NOTE: java's PriorityQueue doesn't support update, cannot use it
            // LAME DESIGN. use a LinkedList instead

            List<Node> leaves = new LinkedList<Node>();
            for (Node node : nodes.values()) {
                if (node.adj.size() == 1) {
                    leaves.add(node);
                }
            }

            int minDiff = Integer.MAX_VALUE;

            while (!leaves.isEmpty()) {
                // get a leaf node
                // Node leaf = pq.poll();
                Node leaf = leaves.get(0);

                leaves.remove(0);
                if (leaf.adj.size() <= 0)// last node
                    break;

                int diff = Math.abs((total - leaf.value) - leaf.value);
                if (diff < minDiff)
                    minDiff = diff;

                // combind leaf to it's connection
                Node conn = null;
                for (Node node : leaf.adj.values()) {
                    conn = node;
                }

                conn.value += leaf.value;
                conn.adj.remove(leaf.index);
                if (conn.adj.size() == 1)
                    leaves.add(conn);
                nodes.remove(leaf.index);
            }

            System.out.println(minDiff);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

ありがとう。

4

2 に答える 2

2

標準の Java PriorityQueue は更新をサポートしていません。アイテムを削除する必要がある場合は、独自の minHeap を実装する必要があります。ヒープ内のアイテムをいくつか削除したら、heapify を呼び出します。

実装と説明はここにあります！

于 2014-12-18T18:29:20.327 に答える