美团2023届秋招笔试记录

笔试之后总结记录的一些题解，并不能保证全部AC

编程题1-小美的礼盒包装AC?

题目描述

小美开的西点屋子举办一周年活动，她准备制作一批礼盒作为对消费者的回馈，每个礼盒中都有三枚西点屋的招牌点心。为了让消费者能品尝到两种点心，因此每个礼盒中都要包含至少一枚A点心和一枚B点心，现在小美的西点屋内共有x枚A点心和y枚B点心，请问小美最多可以制作多少礼盒

输入描述

输入第一行包含一个正整数 T, 表示数据组数 (1 <= T <= 10000)
然后有T行，每行包括两个整数 x 和 y, 空格隔开，表示有 x 枚 A 点心和 y 枚 B 点心 （1 <= x, y <= 10^9)
1
2

输出描述

输出包含T行，每行一个整数，表示最多可以制作的礼盒数量
1

样例输入

2
44 85
9 49
1
2
3

样例输出

43
9
1
2

多的种类和少的种类比较，如果大于少的种类的两倍，直接返回少的，否则返回两者和的三分之一

大家对这一题还是有点疑惑，可能是我的代码写的有点问题，主要也是之前笔试的时候确实没怎么休息好，这些题都没AC出来，下来后复盘了一下

对于这一道题，对于任意一个盒子，只能有两种放点心的方式：

• A点心放一个，B点心放两个
• A点心放两个，B点心放一个

对于以上两种情况分别定义为 $\alpha ,\beta$，则可以得到以下公式
$$\begin{gathered} 2\alpha +\beta \le x \\ \alpha +2\beta \le y \end{gathered}$$
将上面两个式子相加，得到
$$3(\alpha +\beta )\le x+y\to \alpha +\beta \le \frac{x+y}{3}$$

这是一个限制条件，另外如果是A点心太少，只能尽可能的每个盒子只选一枚点心来装盒，即 $\alpha =0$，那么根据不等式方程组就有
$$\beta \le x$$
反之，也有B点心太少，$\beta =0$，也有
$$\alpha \le y$$

所以综合得到判断公式是
$$\min (x,y,\frac{x+y}{3})$$

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            int A = scanner.nextInt(), B = scanner.nextInt();
            System.out.println(calcgift(A, B));
        }
    }

    public static int calcgift(int A, int B) {
        return Math.min(A, B, (A+B)/3);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

提交前代码没有完全AC，不保证修改后的代码完全AC

编程题2AC?

题目描述

小美在做一个实验，这个实验会在纸带上打印出若干个数字，已知该实验所呈现出的正确结果应该是存在某一个分割出k，在k之前打印出的数字都是小于0的，而在k之后的数字应该都是大于0的，那么在k之前如果某一个数据大于等于0，那么我们认为这个数组是异常的，同理，在k之后如果某一个数据小于等于0，那么我们也认为这个数据是异常的。

现在给出小美打印的纸带，且k是未知的，那么请问在最乐观的情况下至少有多少个实验数据是异常的（显然如果出现0，无论k为哪个时刻，这个0数据都是异常的)

输入描述

输入第一行包含一个正整数n，表示小美在纸带上打印的数字数量，(1<=n<=100000)
输入第二行包含n个整数，即小美在纸带上打印的数字，中间用空格隔开，数字仅会-1， 0， 1中的一个
1
2

样例输入

5
0 -1 1 1 -1
1
2

提示

在最乐观的情况下，k应该在第二个和第三个数字之间，此时第一个和最后一个数据是异常的

动态规划分别设置两个数组，记录的是当前 i 前异常的数和 i 后异常的数，比较最小的异常数，返回对应索引

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        int[] prev = new int[n+1];
        int[] next = new int[n+1];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
            if (nums[i] >= 0)
                prev[i+1] = prev[i] + 1;
            else
                prev[i+1] = prev[i];
        }

        int min_err = Integer.MAX_VALUE, idex = 0;
        for (int i = n-1; i >=0; i--) {
            if (nums[i] <= 0)
                next[i] = next[i+1] + 1;
            else
                next[i] = next[i+1];

            if (min_err > next[i] + prev[i+1]) {
                min_err = next[i] + prev[i+1];
                idex = i;
            }
        }

        System.out.println(idex);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

提交前的代码没有完全AC，不保证修改后的代码能够AC

编程题3AC

题目描述

小美有n块魔法石，每块魔法石都有正反两面，每一面都刻有一个魔法阵，初始状态下，n块魔法石都是正面向上。这n块魔法石的能量刚好可以构建一个大型魔法阵，但是需要至少一般的魔法石向上的一面铭刻的阵法相同才能触发大型魔法阵的效果。

小美希望反转最少数量的魔法石，使得这个大型魔法阵被触发，请问她最少需要翻转多少块魔法石。

输入描述

输入第一行包含一个正整数n，表示魔法石的数量
（1<=n<=100000)
输入第二行包含n个正整数，表示n块魔法石正面铭刻的魔法阵种类，由于魔法书上记载的魔法阵数量太多，所以魔法阵编号可能是从1到10^9的任何一个正整数
输入第三行包含n个正整数，表示n块魔法石反而正面铭刻的魔法阵种类，魔法阵编号同样在1到10^9之间
数字间两两有空格隔开
1
2
3
4
5

输出描述

输出仅包含一个整数，如果有解则输出最少翻转的魔法石数量，如果无解则输出-1
1

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

public class Q3 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int up[] = new int[n];
        int down[] = new int[n];
        for (int i = 0; i < n; i++) {
            up[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            down[i] = sc.nextInt();
        }
        System.out.println(minOps(n,up,down));
    }

    public static int minOps(int n, int[] up, int[] down){
        HashMap<Integer,Integer> allMap = new HashMap<>();
        HashMap<Integer,Integer> upMap = new HashMap<>();
        //先统计个数
        for (int i = 0; i < n; i++) {
            //两面相同统计一次
            allMap.put(up[i],allMap.getOrDefault(up[i],0)+1);
            if(up[i]!=down[i]){
                allMap.put(down[i],allMap.getOrDefault(down[i],0)+1);
            }
            upMap.put(up[i],upMap.getOrDefault(up[i],0)+1);
        }

        int target = n%2==0?n/2:n/2+1;
        int ans = n+1;
        for (Integer key : allMap.keySet()) {
            if(allMap.get(key)>=target){
                ans = Math.min(ans,upMap.getOrDefault(key,0)>=target?0:target-upMap.getOrDefault(key,0));
            }
        }
        return ans==n+1?-1:ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

不保证完全AC

编程题4AC

按顺序给你一堆训练集（只有类别编号），就是给了一个数组，然后每个类别中，前（类别数据个数）/2向上取整为训练集，后面的是测试集，让我们按顺序拆分

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[] nums = new int[n];
        int[] samples = new int[m];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
            samples[nums[i]-1]++;
        }
        int[] trains = new int[m];
        int[] tests = new int[m];
        for (int i = 0; i < m; i++) {
            trains[i] = samples[i]/2;
            tests[i] = samples[i]/2;
            if (samples[i] % 2 !=0) {
                trains[i]++;
            }
        }

        int[] cnt = new int[m];
        for (int i = 0; i < n; i++) {
            if (cnt[nums[i]-1]++ < trains[nums[i]-1])
                System.out.print(i+1 + " ");
        }

        cnt = new int[m];
        System.out.println();
        for (int i = 0; i < n; i++) {
            if (cnt[nums[i]-1] < trains[nums[i]-1]) {
                cnt[nums[i] - 1]++;
                continue;
            }
            else if (cnt[nums[i]-1] - trains[nums[i]-1] < tests[nums[i] - 1]){
                System.out.print(i+1 + " ");
                cnt[nums[i]-1]++;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

专项编程题AC

初始字符串为MetTuan，每次对字符串做 str = str + str.reverse() + "wow"的操作，无限循环。后面给你一个k，问你位置k的字符为什么。

对于这一题来说就是找规律，假设字符串为s，字符串的逆序为s’，那么字符串无限循环的过程是

初始字符串为MetTuan，每次对字符串做 str = str + str.reverse() + "wow"的操作，无限循环。后面给你一个k，问你位置k的字符为什么。

这一道题就是找规律：

第一次循环后字符串为：s+s’+“wow”

第二次循环后字符串为：s+s’+“wow”+“wow”+s+s’+“wow”

第三次循环后字符串为：s+s’+“wow”+“wow”+s+s’+“wow”+“wow”+s+s’+“wow”+“wow”+s+s’+“wow”

后续的无限循环字符串基本上都是s+s’+“wow”+“wow”重复出现，所以直接输入数字对这个字符串长度取余，然后取出对应字符输出即可

import java.util.Scanner;

public class Q5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        String str = "MeiTuan";
        str = str + (new StringBuilder(str).reverse().toString())+"wowwow";
        for (int i = 0; i < T; i++) {
            long pos = sc.nextLong()-1;
            pos = pos % str.length();
            System.out.println(str.charAt((int)pos));
       }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16