0810zoom java笔试
#zoom
1，
求树的权值和，输入一个n，表示有n个节点，下一行输入n个字符组成的字符串，第i个字符为R/B，表示第i个节点的颜色为R/B，接下来的n-1行，输入u， v两个值，表示节点uv之间有一条连接的通路。节点的权值为根节点到该节点的R颜色节点个数与B颜色节点个数的差值
2，
股票推荐，大概题意是，A订阅了a，b两个股票，B订阅了a股票，查询B就向B推荐b股票。
操作
1，注册，需要输入名字，订阅股票数，订阅股票名字
2，查询，输出推荐的股票数量
输入一个数q表示有q个操作，
输入q个操作
eg:
5
1 Alice 2
zoom apple
2 Bob(输出error，Bob没有注册)
1 Bob 2
zoom Microsoft
2 Alice(输出1，推荐Microsoft)
2 Bob(输出1，推荐Apple)
今晚跪得很彻底，来个大佬说下好思路😭
思路看这个大佬写的帖子吧：
#笔经##做完zoom2023秋招笔试，人麻了#
1，
求树的权值和，输入一个n，表示有n个节点，下一行输入n个字符组成的字符串，第i个字符为R/B，表示第i个节点的颜色为R/B，接下来的n-1行，输入u， v两个值，表示节点uv之间有一条连接的通路。节点的权值为根节点到该节点的R颜色节点个数与B颜色节点个数的差值
2，
股票推荐，大概题意是，A订阅了a，b两个股票，B订阅了a股票，查询B就向B推荐b股票。
操作
1，注册，需要输入名字，订阅股票数，订阅股票名字
2，查询，输出推荐的股票数量
输入一个数q表示有q个操作，
输入q个操作
eg:
5
1 Alice 2
zoom apple
2 Bob(输出error，Bob没有注册)
1 Bob 2
zoom Microsoft
2 Alice(输出1，推荐Microsoft)
2 Bob(输出1，推荐Apple)
今晚跪得很彻底，来个大佬说下好思路😭
思路看这个大佬写的帖子吧：
0811复盘zoom：
第一题：用邻接表建立有向图，然后dfs遍历图一遍就能得到所有点的权值，用一个数组记录权值，最后计算即可
import java.util.*;
public class My1 {
public int getAns(List<List<Integer>> G, int[] color){
int ans = 0;
int n = color.length;
boolean[] visit = new boolean[n];
int[] weight = new int[n];
dfs(0, G, color, visit, weight, 0, 0);
for (int num : weight) ans += num;
return ans;
}
private void dfs(int root, List<List<Integer>> G, int[] color, boolean[] visit, int[] weight, int red, int blue){
if (visit[root]) return;
visit[root] = true;
if (color[root] == 1) red++;
else blue++;
weight[root] = Math.abs(red - blue);
for (int node : G.get(root)){
dfs(node, G, color, visit, weight, red, blue);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
sc.nextLine();
String str = sc.nextLine();
int[] color = new int[N];
List<List<Integer>> G = new ArrayList<>();
for (int i = 0; i < N; i++){
if (str.charAt(i) == 'R') color[i] = 1;
G.add(new ArrayList<>());
}
for (int i = 0; i < N - 1; i++){
int next = sc.nextInt() - 1;
int pre = sc.nextInt() - 1;
G.get(pre).add(next);
}
sc.close();
My1 main = new My1();
System.out.println(main.getAns(G, color));
}
}
第二题：并查集，去学习一下并查集就发现好像也挺简单的 import java.util.*;
class UnionFind{
List<Integer> rank;
List<Integer> parent;
List<String> company;
Map<String, Integer> map;
public UnionFind() {
rank = new ArrayList<>();
parent = new ArrayList<>();
company = new ArrayList<>();
map = new HashMap<>();
}
public int find(int n){
if (n != parent.get(n)) parent.set(n, find(parent.get(n)));//路径压缩
return parent.get(n);
}
public void union(int pre, int next){
int preParent = find(pre);
int nextParent = find(next);
if (rank.get(preParent) >= rank.get(nextParent)){
parent.set(nextParent, preParent);
rank.set(preParent, rank.get(preParent) + rank.get(nextParent));
}else {
parent.set(preParent, nextParent);
rank.set(nextParent, rank.get(preParent) + rank.get(nextParent));
}
}
public void addCompany(String comName){
if (map.containsKey(comName)){
return;
}
rank.add(1);
parent.add(rank.size() - 1);
company.add(comName);
map.put(comName, company.size() - 1);
}
public int getRecommend(int p){
int par = parent.get(p);
int ans = 0;
for (String c : company){
if (par == parent.get(map.get(c))) ans++;
}
return ans;
}
}
public class My2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
sc.nextLine();
UnionFind unionFind = new UnionFind();
Map<String, String[]> persons = new HashMap<>();
while (q-- > 0){
String command = sc.nextLine();
String[] commands = command.split(" ");
String ops = commands[0];
String name = commands[1];
if (ops.equals("1")){
if (persons.containsKey(name)){
System.out.println("error");
}else {
String companyStr = sc.nextLine();
String[] company = companyStr.split(" ");
for (int i = 0; i < company.length; i++){
unionFind.addCompany(company[i]);
if (i > 0){
unionFind.union(unionFind.map.get(company[i - 1]), unionFind.map.get(company[i]));
}
}
persons.put(name, company);
}
}else {
if (!persons.containsKey(name)){
System.out.println("error");
}else {
String[] cs = persons.get(name);
int p = unionFind.map.get(cs[0]);
System.out.println(unionFind.getRecommend(p) - cs.length);
}
}
}
}
}
思路和代码仅供参考，毕竟当时也没a出来，不知道有没有考虑不周得地方
