题解 | #求二叉树的层序遍历#

我们采用K算法实现
//步骤：
/**
*1.我们先定义一些基础图结构，图节点(Node)，图的边(Edge)，图(Graph)
*2.通过二维数组构建我们熟悉的图结构
*3.构建一个堆,以边为单位，每次都取最小边出来，看是否与之前的边构成环，不构成加入
*3.1构建一个并查集合，用来判断是否在形成环：采用集合形式实现
*3.2开始先每个点以自己为节点各成一个集合例如：题目一共A，B, C 三个村庄，开始集合为A->{A},B->{B}, C->{C}
* 当取A->B这条边时：比较A和B的两个集合是否相同，不相同则不会形成环，则将B的集合元素加到A的集合中（合并），同时更新B的集合：A->{A，B},B->{A,B}, C->{C}
*依次往复，
*4.最后将边集合的权值加起来，就是答案

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        //我们采用K算法实现
        //步骤：
        /**
        *1.我们先定义一些基础图结构，图节点(Node)，图的边(Edge)，图(Graph)
        *2.通过二维数组构建我们熟悉的图结构
        *3.构建一个堆,以边为单位，每次都取最小边出来，看是否与之前的边构成环，不构成加入
        *3.1构建一个并查集合，用来判断是否在形成环：采用集合形式实现
        *4.最后将边集合的权值加起来，就是答案
        */
        //2.
        Graph graph = new Graph(cost);
        //3.
        Queue<Edge> queue= 
            new PriorityQueue<Edge>(/*定义一个比较器*/Comparator.comparingInt(a -> a.weight));//小根堆
        for(Edge edge : graph.edges) {
            queue.add(edge);
        }
        //3.1
        Mysets allsets = new Mysets(graph);
        int miniValue = 0;
        while(!queue.isEmpty()) {
            Edge edge = queue.poll();
            if(!allsets.isSameSet(edge.from, edge.to)){
                allsets.mergeSet(edge.from, edge.to);
                miniValue += edge.weight;
            }
        }
        return miniValue;
    }
    //1.1定义图结构Node
    class Node {
        public int value;//值
        public int in;//入度
        public int out;//出度
        public ArrayList<Node> nexts;//指向的所有节点
        public ArrayList<Edge> myEdges;

        public Node(int value) {
            this.value = value;
            this.in = 0;
            this.out = 0;
            this.nexts = new ArrayList<Node>();
            this.myEdges = new ArrayList<Edge>();
        }
    }
    //1.2定义图结构边Edge
    class Edge {
        public Node from;//开始节点
        public Node to;//结束节点
        public int weight;//权重

        public Edge(int weight, Node from, Node to) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
    //1.3定义图结构Graph
    class Graph {
        public HashMap<Integer,Node> nodes;
        public HashSet<Edge> edges;

        public Graph (int [][] array) {
            HashSet<Integer> set = new HashSet<Integer>();
            nodes = new HashMap<Integer,Node>();
            edges = new HashSet<Edge>();
            for(int i = 0; i< array.length; i++) {
                Integer from = array[i][0];
                Integer to = array[i][1];
                int weight = array[i][2];
                //构建nodes
                if(!nodes.containsKey(from)) {
                    nodes.put(from, new Node(from));
                }
                if(!nodes.containsKey(to)) {
                    nodes.put(to, new Node(to));
                }
                //构建edges
                Node fromNode = nodes.get(from);
                Node toNode = nodes.get(to);
                Edge edge = new Edge(weight,fromNode, toNode);
                edges.add(edge);
                //单独处理每个节点
                fromNode.out++;
                fromNode.nexts.add(toNode);
                fromNode.myEdges.add(edge);
                toNode.in++;
            }
        }
    }
    class Mysets {
        public HashMap <Node, ArrayList<Node>> mysets;

        public Mysets(Graph graph) {
            mysets = new HashMap<Node, ArrayList<Node>>();
            for(Node node : graph.nodes.values()) {
                ArrayList<Node> list = new ArrayList<Node>();
                list.add(node);
                mysets.put(node,list);
                ArrayList<Node> list22 = mysets.get(node);
                list.toArray();
            }
        }

        public boolean isSameSet(Node from, Node to) {
            ArrayList<Node> fromlist = mysets.get(from);
            ArrayList<Node> tolist = mysets.get(to);
            return fromlist == tolist;//内存地址相同即可
        }

        public void mergeSet(Node from, Node to) {
            ArrayList<Node> listfrom = mysets.get(from);
            for(Node toNode: mysets.get(to)) {
                listfrom.add(toNode);
                //mysets.put(to, listfrom);//这里写错了toNode不是to，调试大半天
                mysets.put(toNode, listfrom);//将toNode中集合加入from集合中
            }
        }
    }

}