华为9.7笔试,第一题树节点,欢迎讨论不同方法,指出不足~

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();

        HashSet<Node> nodes = new HashSet<>();
        HashSet<Node> father = new HashSet<>();
        //为孩子节点确定父节点
        for (int i = 0; i < m; i++) {
            String[] tmp = scanner.nextLine().split(" ");
            Node parent = new Node(Integer.parseInt(tmp[0]));
            father.add(parent);
            for (int j = 1; j < tmp.length; j++) {
                int k = Integer.parseInt(tmp[j]);
                Node child = new Node(k, parent);
                nodes.add(child);
            }
        }
        //如果父节点也为孩子节点,把父节点的父节点找到
        t1:for (Node node2 :
                father) {
            for (Node node1 :
                    nodes) {
                if (node1.parent != null && node2.val == node1.val) {
                    node2.parent = node1.parent;
                    continue t1;
                }
            }
            //如果是根节点
            nodes.add(node2);
        }

        int onePoint = scanner.nextInt();
        int twoPoint = scanner.nextInt();
        Node one = null, two = null;
        
        //从所有节点找到连个目标点
        for (Node node :
                nodes) {
            if (node.val == onePoint) {
                one = node;
            }
            if (node.val == twoPoint) {
                two = node;
            }
        }
        
        //这里有没有简介一些的写法
        //获取两个节点的父关系节点
        ArrayList<Node> k1 = new ArrayList<>();
        k1.add(one);
        ArrayList<Node> k2 = new ArrayList<>();
        k1.add(two);
        ArrayList<Node> p1 = getParents(one.parent, k1);
        ArrayList<Node> p2 = getParents(two.parent, k2);
        
        //查看两个节点距离
        int sum = 0;
        for (Node node1 :
                p1) {
            sum++;
            int tmp = 0;
            for (Node node2 :
                    p2) {
                tmp++;
                if (node1.val == node2.val) {
                    sum += tmp;
                    System.out.println(sum - 1);
                    return;
                }
            }
        }
        System.out.println(-1);
    }

    public static ArrayList<Node> getParents(Node node, ArrayList<Node> arr) {
        if (node == null)
            return arr;
        arr.add(node);
        return getParents(node.parent, arr);
    }
}

class Node {
    Node parent;
    final int val;

    public Node(int val) {
        this.val = val;
    }

    public Node(int val, Node parent) {
        this.val = val;
        this.parent = parent;
    }

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

        Node node = (Node) o;

        if (val != node.val) return false;
        return parent == null || parent.equals(node.parent);
    }

    @Override
    public int hashCode() {
        int result = parent == null ? 0 : parent.hashCode();
        result = 31 * result + val;
        return result;
    }
}

#华为笔试##华为机试##华为机考#
全部评论
楼主收到测评了嘛?
1
送花
回复
分享
发布于 2022-09-08 12:00 广西
老哥,这个代码ac了吗
点赞
送花
回复
分享
发布于 2022-09-08 17:40 四川
滴滴
校招火热招聘中
官网直投
老哥帮忙看下我这个代码能过吗?
点赞
送花
回复
分享
发布于 2022-09-08 22:00 广东
您的时间复杂度大概是o(nlog(n))可能会有一部分过不去…
点赞
送花
回复
分享
发布于 2022-09-08 23:32 上海
能说一下题目吗
点赞
送花
回复
分享
发布于 2022-09-09 23:43 江苏
题目是猪的那个吗
点赞
送花
回复
分享
发布于 2022-09-21 16:09 上海

相关推荐

点赞 8 评论
分享
牛客网
牛客企业服务