米哈游笔试

算法题1

米小游拿到了一个字符串，她想截取一个连续子串，使得该子串中包含至少K个连续的“mihoyo”。你可以帮米小游求出最短的子串长度，以及对应的子串位置吗？

输入：

22 2（字符串长度，至少有两个连续的）
mihoyoyomihoyomimihoyo

输出

8 21（左右下标），该题也可以为0 13

代码为：

package mihoyo;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        String s = scanner.next();
        String t = "mihoyo";
        //用于存储每一个出现mihoyo的位置
        List<Integer> l = new LinkedList<>();
        for (int i = 0;i<s.length()-5;i++){
            boolean flag = true;
            for (int j = 0;j<t.length();j++){
                if (s.charAt(i+j)!=t.charAt(j)){
                    flag = false;
                    break;
                }
            }
            //如果与mihoyo相等，则记录m的位置
            if (flag==true){
                l.add(i);
                i = i+5;
            }
        }
        //如果所有mihoyo出现的位置小于要所要求的k则直接输出-1
        if (l.size()<k) {
            System.out.println(-1);
        }else {
            //比较哪k个mihoyo的字符数最少
            int index = 0; //用于存储第一位位置
            int len = l.get(k-1)-l.get(0);//k个mihoyo的长度
            for (int i = k;i<l.size();i++){
                int tlen = l.get(i)-l.get(i-k+1);
                //选出最小的长度
                if (tlen<=len){
                    index = i-k+1;
                    len = tlen;
                }
            }
            System.out.println(l.get(index)+" "+(l.get(index+k-1)+5));
        }

    }
}

算法题2

一个人内心有个正整数 X，有 n 个人过来猜，这个人会对猜的结果进行统计，

有 a 个人的结果 >= X，有 b 个人的结果 < X

问这个数 X 有多少种可能的解决方法，如果无穷，输出 “infinity”

输入：

3（猜谜的人数）
1 5 3（每个人猜的数字）
2 1（a，b）

输出：

2

代码为：

package mihoyo;

import java.util.Arrays;
import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int arr[] = new int[n];
        for (int i = 0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        int a = scanner.nextInt();  //>=
        int b = scanner.nextInt();  //<
        //排序
        Arrays.sort(arr);
        if (b==0){ //只有等于的，所以方案数就是0-(arr[0]-1),也就是arr[0]个
            System.out.println(arr[0]);
            return;
        }
        if (a==0){  //全部都是小于该数，则该数的方案数是无穷多个
            System.out.println("infinity");
            return;
        }
        //除上述两个特殊情况之外，判断方案数
        //方案数等于：（大于该数的第一个数也就是小于该数的最后一个的后面一个）到（小于该数的最后一个数）
        //例如：2，6，10，12
        //如果小于和大于都是2 和 2 则该数的可能为6到10 种情况
        //如果小于个数为1，大于个数为3，则该数可能为2到6 种情况
        //如果小于个数为3，大于个数为1.则该数可能为10到12种情况
        int left = arr[b-1];
        int right = arr[b];
        if (left!=right) {
            System.out.println(right - left);
        }else {
            System.out.println(-1);
        }

    }
}

算法题3

有一棵树(没说是不是二叉树)有 N 个节点。如果相邻两个节点同奇数或同偶数，则认为是同一个连通分量，否则不同的连通分量。
根据此条件，可以获得每个子树的连通分量个数。打印所有子树连通分量个数的和。
3
/ \
4 1
/ \
2 5

例如，3-1-5是同一个连通分量，其余各自是一个连通分量。

1、2、3、4、5子树连通分量个数分别为 2、1、3、1、1，总和为 8

输入：

5 3（节点总数，根节点）
1 2（节点1和节点2有一条边相连）
1 3
3 4
5 1

输出：

8（所有子树连通块之和）

思路：

某节点为根的子树的贡献 = 所有子树贡献和 - 与该节点奇偶性相同的子节点数量。

代码为：

public class test {
    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;
    }

}