2021届秋季校招笔试真题

目录

• 【简单】
• • meituan-001. 小美的用户名
  • meituan-003. 小美的跑腿代购
  • meituan-006. 小团的神秘暗号
• 【中等】
• • meituan-002. 小美的仓库整理
• 【困难】
• • meituan-004. 小团的复制粘贴
  • meituan-005. 小美的区域会议
• 心得

【简单】 meituan-001. 小美的用户名

小美是美团的前端工程师，为了防止系统被恶意攻击，小美必须要在用户输入用户名之前做一个合法性检查，一个合法的用户名必须满足以下几个要求：

用户名的首字符必须是大写或者小写字母。
用户名只能包含大小写字母，数字。
用户名需要包含至少一个字母和一个数字。
如果用户名合法，请输出 “Accept”，反之输出 “Wrong”。
格式：

输入：

• 输入第一行包含一个正整数 T，表示需要检验的用户名数量。
• 接下来有 T 行，每行一个字符串 s，表示输入的用户名。
  输出：
• 对于每一个输入的用户名 s，请输出一行，即按题目要求输出一个字符串。

示例：

输入：

5
Ooook
Hhhh666
ABCD
Meituan
6666

输出：

Wrong
Accept
Wrong
Wrong
Wrong

思路：
这题还是简单的，用ASCII值挨个挨个按照要求比较就行

代码实现：

import java.io.*;

public class Main {
    public static boolean isValidName(String name) {
        // 用户名需要包含至少一个字母和一个数字。 
        if (name == null || name.length() < 2) {
            return false;
        }
        // 用户名的首字符必须是大写或者小写字母。
        if (!Character.isLetter(name.charAt(0))) {
            return false;
        }
        // 用户名只能包含大小写字母，数字。
        boolean flagLetter = false, flagDigit = false;
        for (char ch : name.toCharArray()) {
            if (Character.isLetter(ch)) {
                flagLetter = true;
            } else if (Character.isDigit(ch)) {
                flagDigit = true;
            } else {
                return false;
            }
        }
        return flagLetter && flagDigit;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine());
        for (int i = 0; i < n; ++i) {
            if (isValidName(reader.readLine())) {
                writer.write("Accept\n");
            } else {
                writer.write("Wrong\n");
            }
        }
        writer.close();
        reader.close();
    }
}

meituan-003. 小美的跑腿代购

小美的一个兼职是美团的一名跑腿代购员，她有 n 个订单可以接，订单编号是 1~n ，但是因为订单的时效性，他只能选择其中 m 个订单接取，精明的小美当然希望自己总的获利是最大的，已知，一份订单会提供以下信息，跑腿价格 v ，商品重量 w kg，商品每重 1kg ，代购费用要加 2 元，而一份订单可以赚到的钱是跑腿价格和重量加价之和。小美可是开兰博基尼送货的人，所以自然不会在意自己会累这种事情。请问小美应该选择哪些订单，使得自己获得的钱最多。
请你按照选择的订单编号的从小到大顺序，如果存在多种方案，输出订单编号字典序较小的方案。

格式：

输入：

• 输入第一行包含两个正整数 n，m，表示订单的数量和小美可以接的订单数量。
• 接下来有 n 行，第 i 行表示 i-1 号订单的信息。每行有两个正整数 v 和 w ，表示一个订单的跑腿价格和商品重量。
  输出：
• 输出包含 m 个 1~n 之间的正整数，中间用空格隔开，表示选择的订单编号。
  示例：

输入：

5 2
5 10
8 9
1 4
7 9
6 10

输出：

2 5

思路：
就是把所有的跑腿的钱都算出来然后把最多的m个单子序号从前往后打印出来

代码实现：

import java.io.*;
import java.util.PriorityQueue;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] firstLine = reader.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int m = Integer.parseInt(firstLine[1]);
        // int[0]总价，int[1]订单索引
        PriorityQueue<int[]> queue = new PriorityQueue<>((e1, e2) -> {
            if (e1[0] == e2[0]) {
                return Integer.compare(e1[1], e2[1]); // 总价相同则按索引正序
            } else {
                return Integer.compare(e2[0], e1[0]); // 按总价倒序
            }
        });
        String[] orderLine;
        int value, weight;
        for (int i = 0; i < n; i++) {
            orderLine = reader.readLine().split(" ");
            value = Integer.parseInt(orderLine[0]);
            weight = Integer.parseInt(orderLine[1]);
            int[] e = new int[2];
            e[0] = value + weight * 2;
            e[1] = i;
            queue.offer(e);
        }
        boolean[] flag = new boolean[n];
        for (int i = 0; i < m; i++) {
            int[] e = queue.poll();
            assert e != null;
            flag[e[1]] = true;
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (flag[i]) {
                builder.append(i + 1).append(" ");
            }
        }
        writer.write(builder.toString());
        writer.flush();
        reader.close();
        writer.close();
    }
}

meituan-006. 小团的神秘暗号

小团深谙保密工作的重要性，因此在某些明文的传输中会使用一种加密策略，小团如果需要传输一个字符串 S ，则他会为这个字符串添加一个头部字符串和一个尾部字符串。头部字符串满足至少包含一个 “MT” 子序列，且以 T 结尾。尾部字符串需要满足至少包含一个 “MT” 子序列，且以 M 开头。例如 AAAMT 和 MAAAT 都是一个合法的头部字符串，而 MTAAA 就不是合法的头部字符串。很显然这样的头尾字符串并不一定是唯一的，因此我们还有一个约束，就是 S 是满足头尾字符串合法的情况下的最长的字符串。
很显然这样的加密策略是支持解码的，给出一个加密后的字符串，请你找出中间被加密的字符串 S 。

格式：

输入：

• 输入第一行是一个正整数 n ，表示加密后的字符串总长度。
• 输入第二行是一个长度为 n 的仅由大写字母组成的字符串 T 。
  输出：
• 输出仅包含一个字符串 S 。

示例：

输入：

10
MMATSATMMT

输出：

SATM

思路：

• 按照他的题意从前往后遍历，找到满足条件的最短头部字符串的尾部下标
• 按照他的题意从后往前便利，找到满足条件的最短尾部字符串的头部下标
• 返回中间子字符串

代码实现

import java.io.*;
public class Main {
    //头部字符串满足至少包含一个 “MT” 子序列，且以 T 结尾
    //尾部字符串需要满足至少包含一个 “MT” 子序列，且以 M 开头。
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        //输入
        int n = Integer.parseInt(reader.readLine());
        String T = reader.readLine();

        //TODO
        writer.write(recoveryString(n, T));

        //资源关闭
        writer.flush();
        writer.close();
        reader.close();
    }

    public static String recoveryString(int n, String T) {
        char[] chars = T.toCharArray();
        boolean headM = false;
        boolean tailT = false;
        int start = 0;
        int end = 0;
        for (int i = 0; i < n; i++) {
            if (chars[i] == 'M') {
                headM = true;
            }
            if (chars[i] == 'T' && headM == true) {
                start = i + 1;
                break;
            }
        }

        for (int i = n - 1; i > 0; i--) {
            if (chars[i] == 'T') {
                tailT = true;
            }
            if (chars[i] == 'M' && tailT == true) {
                end = i;
                break;
            }
        }
        return T.substring(start, end);
    }
}

【中等】 meituan-002. 小美的仓库整理

小美是美团仓库的管理员，她会根据单据的要求按顺序取出仓库中的货物，每取出一件货物后会把剩余货物重新堆放，使得自己方便查找。已知货物入库的时候是按顺序堆放在一起的。如果小美取出其中一件货物，则会把货物所在的一堆物品以取出的货物为界分成两堆，这样可以保证货物局部的顺序不变。
已知货物最初是按 1~n 的顺序堆放的，每件货物的重量为 w[i] ,小美会根据单据依次不放回的取出货物。请问根据上述 *** 作，小美每取出一件货物之后，重量和最大的一堆货物重量是多少？

格式：

输入：

• 输入第一行包含一个正整数 n ，表示货物的数量。
• 输入第二行包含 n 个正整数，表示 1~n 号货物的重量 w[i] 。
• 输入第三行有 n 个数，表示小美按顺序取出的货物的编号，也就是一个 1~n 的全排列。
  输出：
• 输出包含 n 行，每行一个整数，表示每取出一件货物以后，对于重量和最大的一堆货物，其重量和为多少。

示例：

输入：

5
3 2 4 4 5
4 3 5 2 1

输出：

9
5
5
3
0
解释：
原本的状态是 {{3,2,4,4,5}} ，取出 4 号货物后，得到 {{3,2,4},{5}} ，第一堆货物的和是 9 ，然后取出 3 号货物得到 {{3,2}{5}} ，此时第一堆和第二堆的和都是 5 ，以此类推。

思路：
暴力法自然就是从前往后遍历，将两堆的最大值输出。但是这个做法的时间复杂度位O(n²)。
但是我们还有更好的选择，顺序遍历是取出货物，那么我们可以选择从前往后遍历放入货物。
然后将结果反向输出不就是需要的答案了嘛

import java.io.*;

public class Main {
    private static int max = 0; // 当前最大重量和
    private static int[] parent; // parent[i]表示编号为i的货物的父节点索引，若parent[i]=i则表示此为一个根节点
    private static int[] heapWeight; // 若第i号货物是一个根节点，则heapWeight[i]表示此堆货物的重量和，否则值为0

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine()); // 货物数目
        String[] weight = reader.readLine().split(" ");
        String[] number = reader.readLine().split(" ");
        int[] w = new int[n]; // 货物重量
        int[] putSn = new int[n]; // 放入顺序，即倒序的取出顺序
        parent = new int[n];
        heapWeight = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = Integer.parseInt(weight[i]);
            putSn[i] = Integer.parseInt(number[i]);
            parent[i] = i; // 初始状态时，各编号货物独自成堆
        }
        boolean[] used = new boolean[n]; // 表示以第i号货物是否已被放入
        int[] result = new int[n + 1]; // 每次放入 *** 作后的最大重量和
        int putIndex;
        for (int i = n - 1; i > 0; i--) { // 开始放入（不需计算最后一次）
            putIndex = putSn[i] - 1; // 索引=序号-1
            used[putIndex] = true;
            // 先自成一个集合
            heapWeight[putIndex] = w[putIndex];
            max = Math.max(heapWeight[putIndex], max);
            // 若右边元素已被放入，则其必是一个根节点，并入当前元素（排除最后一号）
            if (putIndex + 1 < n && used[putIndex + 1]) {
                union(putIndex, putIndex + 1);
            }
            // 若左边元素已被放入，则将当前元素合并过去（排除第一号）
            if (putIndex > 0 && used[putIndex - 1]) {
                union(putIndex - 1, putIndex);
            }
            result[i] = max;
        }
        for (int i = 1; i <= n; i++) { // 多输出一个第n次取出，即第0次放入
            writer.write(result[i] + "\n");
        }
        writer.flush();
        reader.close();
        writer.close();
    }

    // 合并：r号货物所率领的堆 -> l号货物所在的堆，最终根节点为l号货物所属的根节点
    private static void union(int l, int r) {
        int lRoot = find(l);
        parent[r] = lRoot;
        heapWeight[lRoot] += heapWeight[r];
        heapWeight[r] = 0;
        max = Math.max(heapWeight[lRoot], max);
    }

    // 查询i号货物的根节点
    private static int find(int i) {
        while (parent[i] != i) {
            i = find(parent[i]);
        }
        return i;
    }

}

【困难】 meituan-004. 小团的复制粘贴

小团是一个莫得感情的 CtrlCV 大师，他有一个下标从 1 开始的序列 A 和一个初始全部为 -1 序列 B ，两个序列的长度都是 n 。他会进行若干次 *** 作，每一次 *** 作，他都会选择 A 序列中一段连续区间，将其粘贴到 B 序列中的某一个连续的位置，在这个过程中他也会查询 B 序列中某一个位置上的值。
我们用如下的方式表示他的粘贴 *** 作和查询 *** 作：
粘贴 *** 作：1 k x y，表示把 A 序列中从下标 x 位置开始的连续 k 个元素粘贴到 B 序列中从下标 y 开始的连续 k 个位置上。原始序列中的元素被覆盖。（注意：输入数据可能会出现粘贴后 k 个元素超出 B 序列原有长度的情况，超出部分可忽略）
查询 *** 作：2 x，表示询问B序列下标 x 处的值是多少。

格式：

输入：

• 输入第一行包含一个正整数 n ，表示序列 A 和序列 B 的长度。
• 输入第二行包含 n 个正整数，表示序列 A 中的 n 个元素，第 i 个数字表示下标为 i 的位置上的元素，每一个元素保证在 10^9 以内。
• 输入第三行是一个 *** 作数 m ，表示进行的 *** 作数量。
• 接下来 m 行，每行第一个数字为 1 或 2 ，具体 *** 作细节详见题面。
  输出：
• 对于每一个 *** 作 2 输出一行，每行仅包含一个正整数，表示针对某一个询问的答案。

示例 1：

输入：

5
1 2 3 4 5
5
2 1
2 5
1 2 3 4
2 3
2 5

输出：

-1
-1
-1
4

示例 2：

输入：

5
1 2 3 4 5
9
1 2 3 4
2 3
2 5
1 2 2 3
2 1
2 2
2 3
2 4
2 5

输出：

-1
4
-1
-1
2
3
4

思路：
这种不停覆盖的题目思路，都差不多——>线段树。这道题其实不难，难在优化。

代码实现：

import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int n = fs.nextInt();
        int[] a = fs.readArray(n);
        int m = fs.nextInt();
        SegTree tree = new SegTree(n + 1);
        for (int i = 0; i < m; i++) {
            int type = fs.nextInt();
            if (type == 1) {
                int k = fs.nextInt(), x = fs.nextInt(), y = fs.nextInt();
                k = Math.min(k, Math.min(n - y + 1, n - x + 1));
                tree.update(y, y + k - 1, 1, n, 1, x);
            } else {
                int x = fs.nextInt();
                // out.println(tree.search(x, x, 1, n, 1));
                out.println((tree.search(x, x, 1, n, 1) != -1 ? a[tree.search(x, x, 1, n, 1) - 1] : -1));
            }
        }
        

        out.flush();
        out.close();
    }
    public static class SegTree {// 线段树
        int n;
        int[] val;// 值
        int[] mark;// 懒标记
        public SegTree(int _n) {
            n = _n;
            val = new int[n << 2];
            mark = new int[n << 2];
            Arrays.fill(val, -1);
        }
        public void build(int lo, int hi, int p, int[] a) {
            if (lo == hi) {
                val[p] = a[lo];
                return;
            }
            int mid = (lo + hi) / 2;
            build(lo, mid, 2 * p, a);
            build(mid + 1, hi, 2 * p + 1, a);
            // pushup
            val[p] = val[2 * p] + val[2 * p + 1];
        }
        public void update(int lo, int hi, int left, int right, int p, int c) {
            if (left >= lo && right <= hi) {
                val[p] = c;
                mark[p] = c;// 打上懒标记，表示从c开始
                return;
            }
            int mid = (left + right) / 2;
            int num = mid + 1 - left;
            if (mark[p] != 0 && left != right) {
                pushDown(p, num);
            }
            if (lo <= mid) update(lo, hi, left, mid, 2 * p, c);
            if (hi > mid) {
                if (lo > mid) update(lo, hi, mid + 1, right, 2 * p + 1, c);
                else update(lo, hi, mid + 1, right, 2 * p + 1, c + Math.min(mid + 1 - lo, num));
            }
        }
        public void pushDown(int p, int num) {
            val[2 * p] = mark[p];
            val[2 * p + 1] = mark[p] + num;
            mark[2 * p] = mark[p];
            mark[2 * p + 1] = mark[p] + num;
            mark[p] = 0;
        }
        public int search(int lo, int hi, int left, int right, int p) {
            if (left >= lo && right <= hi) {
                return val[p];
            }
            int mid = (left + right) / 2;
            int num = mid + 1 - left;
            if (mark[p] != 0 && left != right) {
                pushDown(p, num);
            }
            int ans = 0;
            if (lo <= mid) ans += search(lo, hi, left, mid, 2 * p);
            if (hi > mid) ans += search(lo, hi, mid + 1, right, 2 * p + 1);
            return ans;
        }
    }
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    public static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }
        long[] readArrayL(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }
    }
}

meituan-005. 小美的区域会议

小美是美团总部的高管，她想要召集一些美团的区域负责人来开会，已知美团的业务区域划分可以用一棵树来表示，树上有 n 个节点，每个节点分别代表美团的一个业务区域，每一个区域有一个负责人，这个负责人的级别为 A[i]
已知小美召集人员开会必须满足以下几个条件：
1.小美召集的负责人所在的区域必须构成一个非空的连通的图，即选取树上的一个连通子图。
2.这些负责人中，级别最高的和级别最低的相差不超过 k 。
请问小美有多少种召集负责人的方式，当且仅当选取的集合不同时我们就认为两种方式不同。由于方案数可能非常大，所以请对 10^9+7 取模。

格式：

输入：

• 输入第一行包含两个整数 n 和 k ，表示区域的数量，和不能超过的级别。
• 接下来有 n-1 行，每行有两个正整数 a 和 b ，表示 a 号区域和 b 号区域有一条边。
• 最后一行有 n 个整数，第 i 个整数表示 i 号区域负责人的级别。
  输出：
• 输出仅包含一个整数，表示可以选择的方案数对 10^9+7 取模之后的结果。

示例：

输入：

5 1
1 2
2 3
3 4
4 5
2 2 2 2 2

输出：

15
解释：显然一个区域的方案有 {1}，{2}，{3}，{4}，{5}，两个区域的方案有 4 个，三个区域的方案有 3 个，四个区域的方案有 2 个，五个区域的方案有 1 个，共 15 个。

思路：
今儿有点累了，明儿再看吧。这美团题目太难了吧，我果然去不了大厂了嘛

心得

• 2022-05-05
  实际上，做这种大厂笔试题，我们发现，如果想要优化，在输入输出方面可以进行优化，如果是我之前自己做，就是用new Scanner。但是看了大佬的答案，我才知道还可以用IO流，更快更简洁↓

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));//输入
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(reader.readLine());//第一行
for (int i = 0; i < n; ++i) {
    if (isValidName(reader.readLine())) {
        writer.write("Accept\n");//输入的内容
    } else {
        writer.write("Wrong\n");
    }
}
writer.close();
reader.close();

• 2022-05-05
  可以自己做一些输入方面的封装，以及一些数据结构的封装，方便使用

1. 输入的封装

//输出
public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
//输入
public static class FastScanner {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer("");

    String next() {
        while (!st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    int[] readArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    long[] readArrayL(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
        }
        return a;
    }
}

2. 线段树的封装

public static class SegTree {// 线段树
    int n;
    int[] val;// 值
    int[] mark;// 懒标记

    public SegTree(int _n) {//构造器
        n = _n;
        val = new int[n << 2];
        mark = new int[n << 2];
        Arrays.fill(val, -1);
    }

    public void build(int lo, int hi, int p, int[] a) {
        if (lo == hi) {
            val[p] = a[lo];
            return;
        }
        int mid = (lo + hi) / 2;
        build(lo, mid, 2 * p, a);
        build(mid + 1, hi, 2 * p + 1, a);
        // pushup
        val[p] = val[2 * p] + val[2 * p + 1];
    }

    public void update(int lo, int hi, int left, int right, int p, int c) {
        if (left >= lo && right <= hi) {
            val[p] = c;
            mark[p] = c;// 打上懒标记，表示从c开始
            return;
        }
        int mid = (left + right) / 2;
        int num = mid + 1 - left;
        if (mark[p] != 0 && left != right) {
            pushDown(p, num);
        }
        if (lo <= mid) update(lo, hi, left, mid, 2 * p, c);
        if (hi > mid) {
            if (lo > mid) update(lo, hi, mid + 1, right, 2 * p + 1, c);
            else update(lo, hi, mid + 1, right, 2 * p + 1, c + Math.min(mid + 1 - lo, num));
        }
    }

    public void pushDown(int p, int num) {
        val[2 * p] = mark[p];
        val[2 * p + 1] = mark[p] + num;
        mark[2 * p] = mark[p];
        mark[2 * p + 1] = mark[p] + num;
        mark[p] = 0;
    }

    public int search(int lo, int hi, int left, int right, int p) {
        if (left >= lo && right <= hi) {
            return val[p];
        }
        int mid = (left + right) / 2;
        int num = mid + 1 - left;
        if (mark[p] != 0 && left != right) {
            pushDown(p, num);
        }
        int ans = 0;
        if (lo <= mid) ans += search(lo, hi, left, mid, 2 * p);
        if (hi > mid) ans += search(lo, hi, mid + 1, right, 2 * p + 1);
        return ans;
    }
}