Zoom笔试题

zoom笔试有点难 ，这里参考牛客大佬写的答案，做下记录

1.有一颗有根树 根节点为1号节点 每个节点为红色或蓝色 假设第i个节点的权值为从根节点到该节点红蓝节点的数量之差 请你返回所有节点的权值之和
输入
第一行输入n个节点，第二行为每个节点的颜色，接下来n-1行为a、b节点之间有连接：
5
RBBRB
1 5
2 5
1 3
5 4
输出
3

思路：创建出图，然后dfs回溯计算。路径要从节点1开始。重点是构图的这种方式，图的题目做的太少了。

class ListNdoe {
    long val;
    ListNdoe next;

    public ListNdoe(long val, ListNdoe next) {
        this.val = val; //每个节点权值，即每个节点路径上红蓝色之差
        this.next = next;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc =  new Scanner(System.in);
        int root = 0;
        int n = sc.nextInt();
        System.out.println(n);
        int[] color = new int[n];//每个节点的颜色
        ListNdoe[] graph = new ListNdoe[n];//记录每个节点会和哪几个节点有连接关系
        for (int i = 0;i < n;i++) {
            graph[i] = new ListNdoe(0,null);
        }
        sc.nextLine();
        String str = sc.nextLine();
        System.out.println(str);
        for (int i = 0;i < n;i++) {
            if (str.charAt(i) == 'R') {
                color[i] = 1;//1代表红色
            }
        }
        for (int i = 0;i < n - 1;i++) { //把各个节点根据关系组合起来
            // 题目条件从1开始计，为了和数组下标对齐，都减1
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            insert(u,v,graph);
        }

        int[] visited = new int[n];
        dfs(root, visited, 0, 0, color,graph);
        long ans = 0;
        for (int i = 0;i < n;i++) {
            ans += graph[i].val;
        }
        System.out.println(ans);
    }

    // 构造节点间的连接关系
    public static void insert(int u,int v,ListNdoe[] graph) {
        ListNdoe vNode = new ListNdoe(v,graph[u].next);
        graph[u].next = vNode;
        ListNdoe uNode = new ListNdoe(u,graph[v].next);
        graph[v].next = uNode;
    }

    public static void dfs(int root, int[] visited, int red, int blue, int[] color, ListNdoe[] graph) {
        visited[root] = 1;//当前节点被访问过了
        // 判断当前节点颜色
        if (color[root] == 1) {
            red++;//红色数量加1
        } else {
            blue++;//蓝色数量加1
        }
        graph[root].val = Math.abs(red - blue);//计算出当前节点的红蓝色之差
        ListNdoe p = graph[root].next;
        while (p != null) {//继续遍历和当前节点有连接关系的节点，可以复用红蓝色节点各自的数量
            if(visited[(int)p.val]!=1){//如果遍历到的节点没有访问过
                dfs((int)p.val,visited,red,blue,color,graph);//递归计算
            }
            p = p.next;
        }
        visited[root] = 0;//回溯
    }
}

2.完成股票推荐系统设计，如果一个人关注了a又关注了b 则系统会给只关注a没关注b的人推荐关注b，请返回应该给此人推荐关注几个股票
输入
第一行输入q表示操作次数
接下来输入一次操作
共有两种操作
1.注册
格式为
1 name n 表示有一个name的人关注了n个股票
第二行输入n个字符串表示这n个股票 n个字符串不相同
2.查询
格式为
输入2 name 表示查询系统会给此人推荐多少股票
保证至少有一次查询
例
5
1 Alice 2
Zoom Apple
2 Bob
2 Alice
1 Bob 2
Apple MicroSoft
2 Bob
输入
error
0
1

思路：并查集。

class UnionSet {
    List<Integer> parent;
    List<Integer> cnt;
    List<String> company;
    HashMap<String,Integer> companyMap;

    public UnionSet(){ //构造函数
        parent = new ArrayList<>();//存储每个股票的父节点
        cnt = new ArrayList<>();//存储每个股票的子节点数量
        company = new ArrayList<>();//存储每个股票
        companyMap = new HashMap<>();//存储每个股票的下标
    }

    public void addCompany(String companyName){//加入股票
        if(companyMap.containsKey(companyName)){//如果map已经包含了
            return;
        }
        cnt.add(1);//初始化每个股票的子节点数量为1
        parent.add(cnt.size()-1);//父节点初始是自身
        company.add(companyName);//加入当前股票
        companyMap.put(companyName,company.size()-1);//key是股票，value是下标
    }

    public void union(String u,String v){//合并两支股票
        int ufather = getParent(u);//第一支股票的祖宗节点下标
        int vfather = getParent(v);//第二支股票的祖宗节点下标
        if(ufather == vfather) return;//如果相等，说不需要合并
        if(cnt.get(ufather)>cnt.get(vfather)){//把数量少的那部分合并到数量多的那部分
            parent.set(vfather,ufather);
            cnt.set(ufather,cnt.get(ufather)+cnt.get(vfather));
        }
        else{
            parent.set(ufather,vfather);
            cnt.set(vfather,cnt.get(ufather)+cnt.get(vfather));
        }
    }

    public int getParent(String cName){//获取当前股票的祖宗节点
        int idx = companyMap.get(cName);//当前股票的下标
        while(parent.get(idx)!=idx){//下标不等于父节点的下标，即自己不是祖宗节点
            parent.set(idx,parent.get(parent.get(idx)));
            idx = parent.get(idx);
        }
        return idx;//返回祖宗节点的下标
    }

    public int getSetsByCompanies(int u){
        int parent = getParent(company.get(u));//获取当前下标股票的祖宗节点
        return cnt.get(parent);//这个祖宗节点下有多少个子节点
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashMap<String,String[]> person = new HashMap<>();//记录每个人关注的股票
        UnionSet us = new UnionSet(); //初始化并查集对象，把每个股票当成一个节点
        int ops = sc.nextInt();//操作次数
        sc.nextLine();
        for (int i = 0; i < ops; i++) {//遍历每次操作
            String command = sc.nextLine();//本次输入的命令
            String commands[] = command.split(" ");//将命令按照空格分开
            String name = commands[1];//用户姓名
            if(commands[0].equals("1")){//如果是1，表示注册
                if(person.containsKey(name)){//如果当前用户已经存在，输出error
                    System.out.println("error");
                    continue;
                }
                String companyStr = sc.nextLine();//当前用户关注的股票
                String[] companies = companyStr.split(" ");//股票数组
                for (int j = 0; j < companies.length; j++) {//遍历每个股票
                    us.addCompany(companies[j]); //加入当前股票
                    if(j>0){ //合并股票
                        us.union(companies[j],companies[j-1]);//默认以第一支股票为父节点
                    }
                }
                person.put(name,companies);//key是用户，value是他订阅的股票
            }
            else{//如果是2，查询系统会给当前用户推荐几支股票
                if(person.containsKey(name)){//当前用户存在
                    int p = us.getParent(person.get(name)[0]);//当前用户的股票的父节点
                    int cnt  = us.getSetsByCompanies(p);//获取当前股票的祖宗节点下的股票数量
                    System.out.println(cnt-person.get(name).length);//总数量减去当前已经有的股票数量
                }
                else{//当前用户不存在，直接输出error
                    System.out.println("error");
                }
            }
        }
    }
}