8.10Zoom笔试

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

//没有全部通过 不知原因 希望大家指出
public class Test01 {
    static int res = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.nextLine());
        char[] ch = sc.nextLine().toCharArray();
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for (int i = 0; i < num - 1; i++) {
            int[] n = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            tree.computeIfAbsent(n[0], k -> new ArrayList<>()).add(n[1]);
            tree.computeIfAbsent(n[1], k -> new ArrayList<>()).add(n[0]);
        }
        int blue = 0;
        int red = 0;
        boolean[] visited = new boolean[num + 1];
        visited[0] = true;
        dfs(1, blue, red, visited, ch, tree);
        System.out.println(res);
    }

    public static void dfs(int cur, int blue, int red, boolean[] visited, char[] ch, Map<Integer, List<Integer>> tree) {
        if(visited[cur]) return;
        if (ch[cur - 1] == 'B') {
            res = res +Math.abs(red - blue-1);
        } else {
            res = res+ Math.abs(red+1  - blue);
        }
        visited[cur] = true;
        for (int i : tree.get(cur)) {
            if (ch[cur - 1] == 'B') {
                dfs(i, blue + 1, red, visited, ch, tree);
            } else {
                dfs(i,  blue, red + 1, visited, ch, tree);
            }
        }
    }
}

完成股票推荐系统设计，如果一个人关注了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

public class Test02 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        UF uf = new UF(500010);
        Map<String, Integer> map1 = new HashMap<>(); // 每个名字在树的映射
        Map<String, Integer> map2 = new HashMap<>(); // 股票和 index 映射
        Map<String, Integer> map3 = new HashMap<>();
        int index = 0;
        for (int i = 0; i < q; i++) {
            int op = sc.nextInt();
            if (op == 1) {
                String name = sc.next();
                int n = sc.nextInt();
                map3.put(name, n);
                String stock = sc.next();
                int currIndex = -1;
                if (map2.containsKey(stock)) {
                    currIndex = map2.get(stock);
                } else {
                    currIndex = index++;
                }
                map1.put(name, currIndex);
                map2.put(stock, currIndex);
                for (int j = 1; j < n; j++) {
                    int t = -1;
                    stock = sc.next();
                    if (map2.containsKey(stock)) {
                        t = map2.get(stock);
                    } else {
                        t = index++;
                    }
                    map2.put(stock, t);
                    uf.union(currIndex, t);
                    currIndex = t;
                }
            } else {
                String name = sc.next();
                if (!map3.containsKey(name)) {
                    System.out.println("error");
                    continue;
                }
                int root = uf.find(map1.get(name));
                int diff = uf.size[root] - map3.get(name);
                System.out.println(diff);
            }
        }
    }


    static class UF {
        int[] parent;
        int[] rank;
        int[] size;

        UF(int n) {
            parent = new int[n];
            rank = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        int find(int x) {
            while (parent[x] != x) {
                x = parent[x];
            }
            return x;
        }

        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] >= rank[rootY]) {
                    if (rank[rootX] == rank[rootY]) {
                        rank[rootX]++;
                    }
                    parent[rootY] = rootX;
                    size[rootX] += size[rootY];
                } else {
                    parent[rootX] = rootY;
                    size[rootY] += size[rootX];
                }
            }
        }

    }
}