signed

QiShunwang

“诚信为本、客户至上”

2021春招美团算法笔试题

2021/3/21 0:20:38   来源:

2021春招美团算法笔试题整理,供大家参考!
(图片来源于网络,转载请联系博主)

一、流

小美最近在学操作系统。
流是操作系统中一个重要的概念。
小美自己也实现了一个类似于 /dev/random 的设备,但是它只能提供预先设定好但循环不断的某个小写字母排列。
在这里插入图片描述

package MT;

import java.util.Scanner;

public class MT1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String in1 = sc.next();
        String in2 = sc.next();
        char[] chars1 = in1.toCharArray();
        char[] chars2 = in2.toCharArray();
        int length1 = chars1.length;
        int length2 = chars2.length;
        int count = 0;
        int i = 0;
        while(true) {
            for (int j = 0; j < length1; j++) {
                if (chars1[j] != chars2[i]) {
                    count++;
                } else  {
                    if (i < length2-1) i++;
                    else break;
                }
            }
            if (i == length2-1) break;
        }
        System.out.println(count);
    }
}

二、多重集合

小团现在有两个等大的多重集合A和B,她现在想让A集合和B集合相等。
在这里插入图片描述

package MT;

import java.util.HashMap;
import java.util.Scanner;

public class MT2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];

        for (int i = 0; i < n; i++)
            a[i] = sc.nextInt();

        for (int i = 0; i < n; i++)
            b[i] = sc.nextInt();

        HashMap<Integer, Integer> mapA = new HashMap<>();
        HashMap<Integer, Integer> mapB = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (mapA.containsKey(a[i])) mapA.put(a[i], mapA.get(a[i]) + 1);
            else mapA.put(a[i], 1);
        }
        //System.out.println(mapA);
        for (int i = 0; i < n; i++) {
            if (mapB.containsKey(b[i])) mapB.put(b[i], mapB.get(b[i]) + 1);
            else mapB.put(b[i], 1);
        }
        //System.out.println(mapB);

        for (int i = 1; i < m; i++) {
            boolean match = true;
            for (Integer num : mapA.keySet()) {
                int numMod = (num + i) % m;
                if (mapB.containsKey(numMod) && mapA.get(num) == mapB.get(numMod))
                    continue;
                else {
                    match = false;
                    break;
                }
            }
            if (match) System.out.println(i);
        }
    }
}


//6 8
//1 1 4 5 1 4
//3 0 4 0 3 0

三、奶茶

学校正在举行喝奶茶比赛。这次比赛准备了n杯奶茶,序号为1到n。

package MT;

import java.util.Scanner;

public class MT3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int C = sc.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int dp[][] = new int[m][n];
        int total = 0;
        for (int i = 0; i < n; i++) {
            dp[0][i] = (int) Math.ceil(((total + arr[i]) * 1.0 / C));
            total += arr[i];
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = (int) Math.ceil(arr[0] * 1.0 / C);
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j];
                int tmp = 0;
                for (int k = j - 1; k >= 0; k--) {
                    tmp += arr[k + 1];
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][k], (int) Math.ceil(((tmp * 1.0 / C)))));
                }
            }
        }
        System.out.println(dp[m - 1][n - 1]);

    }
}

四、值日

小美和小团的班上有n个人,分别编号为1到n。其中小美的编号为1,小团的编号为2。
在这里插入图片描述

package MT;

import java.util.Scanner;

public class MT4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] duty = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                duty[i][j] = sc.nextInt();
            }
        }
        System.out.println(studentID(m, duty));
    }

    static int studentID(int m, int[][] dutyTable) {
        int id = 0;// 值日的人
        // 初值
        int a1 = 1, a2 = 2;
        // 第一天小美 “1”,第二天小团 “2”,从第三天开始,第三天dutyTable[a2-1][a1-1]
        int i = 0;
        while ( i < (m - 2)) {
            id = dutyTable[a2-1][a1-1];
            a1 = a2;
            a2 = id;
            i++;
        }
        return id;
    }
}




// 输入
//3 7
//0 3 2
//3 0 3
//2 1 0

五、溶液

小美在做化学实验,这个实验需要配置很多种溶液浓度,因此配溶液之前需要详细计算溶液浓度,避免误操作。
在这里插入图片描述

package MT;

import java.util.Scanner;

public class MT5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 初始溶液质量 m0 和 质量分数 w0
        int m0 = sc.nextInt();;
        double w0 = sc.nextInt() / 100.0;
        int n = sc.nextInt();  // 操作数

        // A操作之后的溶液质量和质量分数 mNew、wNew
        int mNew = m0; double wNew = w0;

        // 记录 A 操作加入溶液质量 m,加入溶液质量分数 w 的缓存值,方便B操作回退
        int mTmp = m0; double  wTmp = w0;

        String B = "B", A = "A";
        int i = 0;
        while (i < n) { // 操作 n 次,
            String input = sc.next();
            if (input == A) {
                int m = sc.nextInt();  // 加入溶液质量 m
                double w = sc.nextInt() / 100.0;  // 加入溶液质量分数 w
                // A操作之后的溶液质量和质量分数 mNew、wNew
                mNew = m0 + m;
                wNew = (m0 * w0 + m * w) / mNew;

                mTmp = m; wTmp = w;  // 记录 A 操作加入的量
            }

            if (input == B) {
                if (mNew == m0 && wNew == wTmp) continue;
                // 回退 上一步的 A,就是 根据公式反求一下
                mNew -= mTmp;
                wNew = (mNew * wNew - mTmp * wTmp) / (mNew - mTmp);// 反推公式中的变量

            }
            i++;
            System.out.println(mNew);
            System.out.println(String.format("%.5f",wNew));  // 保留5位小数
        }
    }
}