米哈游 笔试 09.14 AC
一晚上做了三场笔试，时间大概
一个人内心有个正整数 X，有 n 个人过来猜，这个人会对猜的结果进行统计，
有 a 个人的结果 >= X，有 b 个人的结果 < X
问这个数 X 有多少种可能的解决方法，如果无穷，输出 "infinity"
补充，第二题的返回在于题目说 X 是正整数
有一棵树(没说是不是二叉树)有 N 个节点。如果相邻两个节点同奇数或同偶数，则认为是同一个连通分量，否则不同的连通分量。
根据此条件，可以获得每个子树的连通分量个数。打印所有子树连通分量个数的和。
3
/ \
4 1
/ \
2 5
例如，3-1-5是同一个连通分量，其余各自是一个连通分量。
1、2、3、4、5子树连通分量个数分别为 2、1、3、1、1，总和为 8
#米哈游##米哈游笔试##校招##23届秋招笔面经#
- 18：30 - 19：15 小米
- 19：15 - 19：45 茄子科技
- 19：45 - 20：30 米哈游。
要不是秋招没有 offer，谁会这样啊
第一题 包含 k 个 "mihoyo" 的字串的最短长度 (start end)
public static void main1(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
String s = sc.next();
String tmp = "mihoyo";
List<Integer> l = new ArrayList<>();
// 先尝试获取 mihoyo 的位置，这里用list存储m的索引
for(int i = 0; i < n - 5; i++){
boolean ok = true;
for(int j = 0; j < 6; j++){
if(s.charAt(i+j) != tmp.charAt(j)){
ok = false;
}
}
if(ok){
l.add(i);
i += 5;
}
}
// 不够 k 个
if(l.size() < k){
System.out.println(-1);
return;
}
// 判断比较
int retIdx = 0;
int len = l.get(k-1) - l.get(0);
for(int i = k; i < l.size(); i++){
int tmplen = l.get(i) - l.get(i-k+1);
if(tmplen <= len){
retIdx = i-k+1;
len = tmplen;
}
}
System.out.println(l.get(retIdx)+" "+(l.get(retIdx+k-1)+5));
}
第二题 如下
一个人内心有个正整数 X，有 n 个人过来猜，这个人会对猜的结果进行统计，
有 a 个人的结果 >= X，有 b 个人的结果 < X
问这个数 X 有多少种可能的解决方法，如果无穷，输出 "infinity"
补充，第二题的返回在于题目说 X 是正整数
public static void main2(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
int a = sc.nextInt(), b = sc.nextInt();
Arrays.sort(arr);
if(b == 0){ // 全部是小于等于的
System.out.println(arr[0]);
return;
}
if(a == 0) { // 全部是大于的
System.out.println("infinity");
return;
}
int left = arr[b-1], right = arr[b];
if(left == right){ // left < x <= right 不成立
System.out.println(-1);
return;
}else{
System.out.println(right-left);
}
} 第三题 树的题
有一棵树(没说是不是二叉树)有 N 个节点。如果相邻两个节点同奇数或同偶数，则认为是同一个连通分量，否则不同的连通分量。
根据此条件，可以获得每个子树的连通分量个数。打印所有子树连通分量个数的和。
3
/ \
4 1
/ \
2 5
例如，3-1-5是同一个连通分量，其余各自是一个连通分量。
1、2、3、4、5子树连通分量个数分别为 2、1、3、1、1，总和为 8
static Map<Integer, Integer> map;
static long ret;
static List<List<Integer>> l;
static boolean vis[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int root = sc.nextInt();
vis = new boolean[n+1];
map = new HashMap<>();
ret = 0;
l = new ArrayList<>();
for(int i = 0; i <= n; i++){
l.add(new ArrayList<>());
}
for(int i = 0; i < n-1; i++){
int a = sc.nextInt();
int b = sc.nextInt();
l.get(a).add(b);
l.get(b).add(a);
}
dfs(root);
System.out.println(ret);
}
public static int dfs(int pos) {
List<Integer> childs = l.get(pos);
vis[pos] = true;
// 当前节点是一个连通分量
int tmp = 1;
for(int child: childs){
if(!vis[child]){
// 获取 child 的连通分量
tmp += dfs(child);
// 如果同奇偶，则连通分量个数-1
if(child % 2 == pos%2) {
tmp -=1;
}
}
}
ret += tmp;
return tmp;
}
