2022 8.13美团后端笔试

事先说明本文对牛客大佬文章进行二次创作：美团8.13 后端方向笔试题 全AC_笔经面经_牛客网

1:  魔法外卖（模拟）

 * 炸鸡店拥有一名会传送魔法的外卖派送员。
 *
 * 该外卖派送员派送单子时，可以消耗时间t来正常派送单子（一次只能派送一个单子，不能多个同时派送），也可以使用魔法不耗费时间地隔空瞬间投送。
 *
 * 现在炸鸡店在时刻0接收到了若干炸鸡订单，每个单子都有它的截止送达时间。外卖派送员需要保证送达时间小于等于这个截止时间。
 *
 * 现在询问外卖员最少要使用几次魔法来保证没有外卖超时。
 *
 *
 *
 * 输入描述
 * 第一行两个正整数n, t 以空格分开，表示当前接到了n个订单，外卖员在不使用魔法的情况下正常派送所需要消耗的时间t。
 *
 * 第二行n个正整数，每个正整数表示一个订单的截止送达时间。
 *
 * 1 <= n <= 1e5, 1 <= t <= 100, 订单的送达时间介于[1, 1e7]之间
 *
 * 输出描述
 * 一行一个非负整数，表示外卖员最少需要使用的魔法次数。
 * 样例输入
 * 6 5
 * 5 6 7 8 9 10
 * 样例输出
 * 4

public class Main1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int t=scanner.nextInt();
        int[] times = new int[n];
        for (int i=0; i<times.length; i++){
            times[i] = scanner.nextInt();
        }
        Arrays.sort(times);
        int num=0;
        int time=0;
        for (int i=0; i<times.length; i++){
            //送完前一个的时间+t小于等于下一个的截止时间，就不用魔法
            if(time+t<=times[i]){
                time+=t;
            }else{
                num++;
            }
        }
        System.out.print(num);
    }
}

---

2：打扫房间（模拟）

你买了一个扫地机器人，你想要知道这个扫地机器人是否能够将房间打扫干净。

* 为了简化问题，我们不妨假设房间被划分为n*m的方格。定义打扫干净为这n*m的方格全部被打扫过至少一次。
* <p>
* 你为扫地机器人下达了若干指令。每个指令为上下左右移动中的一种。机器人会将经过的路径上的方格打扫干净。
* <p>
* 初始时假设机器人处于第一行第一列的方格中。这个方格初始时会被机器人直接打扫干净。

* 现在询问你机器人能否将房间打扫干净，能则输出Yes，不能则输出No。
* <p>
* 对于Yes的情况下，还要求你继续输出到哪个指令结束后，房间就打扫干净了。
* <p>
* 对于No的情况下，还要求你输出还有多少个地块没有打扫干净。
* <p>
* 保证机器人在打扫的过程中不会越过房间边界。换句话说机器人始终保持在n*m的方格图中。

* 输入描述
* 第一行三个正整数n, m, k，以空格分开，表示房间大小n*m，接下来会有长度为k的指令。
* <p>
* 第二行长度为k的一个字符串。字符串中仅有下面四种字符（注意：均为大写）
* <p>
* W：表示下一步机器人将向上移动
* <p>
* A：表示下一步机器人将向左移动
* <p>
* S：表示下一步机器人将向下移动
* <p>
* D：表示下一步机器人将向右移动
* <p>
* 保证2 <= n, m <= 100, 指令长度 <= 100000
* <p>
* 输出描述
* 第一行一个字符串Yes或No表示能否打扫干净
* <p>
* 对于Yes的情况，第二行输出一个正整数，表示在第几个指令之后已经打扫干净了。
* <p>
* 注意指令编号从1开始而不是0。
* <p>
* 对于No的情况，第二行输出一个正整数，表示还剩几个地块没有打扫。

* 样例输入
* 2 2 5
* SDWAS
* 样例输出
* Yes
* 3

public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
 
        String orders = scanner.next();
        if (orders.length() != 5) {
            return;
        }
        int[][] room = new int[n][m];
        room[0][0] = 1;
        int count = 1, x = 0, y = 0;
        for (int i = 0; i < orders.length(); i++) {
            char ch = orders.charAt(i);
            if (ch == 'W') {
                y--;
            } else if (ch == 'S') {
                y++;
            } else if (ch == 'A') {
                x--;
            } else if (ch == 'D') {
                x++;
            }
            //存在这个点
            if (room[y][x] == 0) {
                room[y][x] = 1;
                count++;
            }
            if (count == n * m) {
                System.out.println("Yes");
                System.out.print(i + 1);
                return;
            }
 
        }
        System.out.println("No");
        System.out.print(n * m - count);
    }
}

---

3：扑克牌游戏（双向队列，反向模拟）

* Alice和Bob在玩一个游戏。有n张卡牌，点数分别为1到n。进行洗牌后，n张牌从上到下叠放形成一个牌堆。每次Alice先将当前牌堆顶的一张牌放到牌堆底，然后Bob再将当前牌堆顶的一张牌放到牌堆底。（特别地，当牌堆中只有一张牌时，相当于不进行任何操作）接着，他们会翻开当前牌堆顶的牌，并记下它的点数。当所有牌都被翻开后，他们也记下了n个点数。现在他们想根据记下的这个序列来还原一开始的牌（从牌堆顶到牌堆底每一张牌的点数）。
* <p>
* <p>
* <p>
* 输入描述
* 第一行是一个正整数n，表示有n张牌。
* <p>
* 接下来一行n个用空格隔开的正整数，第i个数a_i表示第i张被翻开的牌的点数。
* <p>
* 1<=n<=100000
* <p>
* 输出描述
* 一行n个用空格隔开的正整数，第i个数表示初始牌堆中从牌堆顶到牌堆底的第i张牌的点数。
* <p>
* <p>
* 样例输入
* 4
* 1 2 3 4
* 样例输出
* 4 2 1 3

public class Main3 {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int[] cards = new int[n];
        for(int i=0; i<n; i++)  {
            cards[i] = scanner.nextInt();
        }
        int[] origin=new int[n];
        Deque<Integer> deque = new LinkedList<Integer>();
        for(int i=0; i<n; i++) {
            deque.offerLast(n-i-1);
        }
        for(int i=0; i<n; i++) {
            deque.offerFirst(deque.pollLast());
            deque.offerFirst(deque.pollLast());
            //反向操作，现在索引是正向的
            origin[deque.pollLast()]=cards[i];
        }
        for(int i=0; i<n; i++) {
            System.out.print(origin[i]);
            System.out.print(" ");
        }
 
    }
}

---

4：三元组变形问题（HashMap）

给一个长度为n的序列a[1], a[2], …, a[n]，请问有多少个三元组(i,j,k)满足i<j<k且a[i]-a[j]=2a[j]-a[k]？输出符合要求的三元组的数量。
*
*
*
* 输入描述
* 第一行是一个整数n，表示序列长度为n。
*
* 接下来一行n个用空格隔开的整数，a[i]表示序列的第i个数。
*
* 1<=n<=4000, 0<=a[i]<=1000000
*
* 输出描述
* 一行一个整数，表示符合要求的三元组数量。
*
*
* 样例输入
* 4
* 4 2 2 2
* 样例输出
* 3

public class Main4 {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int[] nums = new int[n];
        for(int i=0; i<n; i++) {
            nums[i] = scanner.nextInt();
        }
        long count=0;
 
        Map<Integer, Integer> mp = new HashMap<>();
        mp.put(nums[n - 1], 1);
        for (int i = n - 2; i >= 1; i--) {
            for (int j = i - 1; j >= 0; j--) {
                count += mp.getOrDefault(3 * nums[i] - nums[j], 0);
            }
            mp.put(nums[i], mp.getOrDefault(nums[i], 0) + 1);
        }
 
        /*超时了，82%
        int num=0;
        for(int i=0;i<arr.length;i++) {
            for(int j=i+1; j<arr.length; j++) {
                for(int k=j+1; k<arr.length; k++) {
                    if(arr[i]==3*arr[j]-arr[k]) {
                        num++;
                    }
                }
            }
        }
        System.out.print(num);*/
        System.out.print(count);
    }
}

---

5：树的分支最大值（层序遍历）

给一棵有n个节点的二叉树，节点的编号从1到n。
*
* 其中，节点k的左儿子为节点2*k（当2*k大于n时，不存在左儿子）
*
* 节点k的右儿子为节点2*k+1（当2*k+1大于n时，不存在右儿子）
*
* 该二叉树的根节点为节点1。
*
*
*
* 对于每个节点，节点上有一些金钱。
*
* 现在你可以从根节点1开始，每次选择左儿子或者右儿子向下走，直到走到叶子节点停止，并获得你走过的这些节点上的金钱。
*
*
*
* 你的任务是求出你可以获得的最大的金钱总量。
*
*
*
* 输入描述
* 第一行是一个正整数n，表示二叉树上总共有n个节点。
*
* 第二行有n个正整数，第i个正整数表示节点i上有多少数量的金钱。
*
* 1 <= n <= 100000
*
* 对所有数据保证：单个节点上的金钱数量在 [1, 1000] 之间
*
* 输出描述
* 一行一个正整数，表示你所能获得的最大的金钱总量
*
*
* 样例输入
* 3
* 5 7 8
* 样例输出
* 13

public class Main5 {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int[] array = new int[n+1];
        for (int i=1; i<=n; i++) {
            array[i] = scanner.nextInt();
        }
        int res=0;
        Queue<Integer> deque = new ArrayDeque<Integer>();
        deque.offer(1);
        while(!deque.isEmpty()) {
            int tmp=deque.poll();
            res=Math.max(res,array[tmp]);
            if(2*tmp<=n){
                array[tmp*2]+=array[tmp];
                deque.offer(2*tmp);
            }
            if(2*tmp+1<=n){
                array[tmp*2+1]+=array[tmp];
                deque.offer(2*tmp+1);
            }
        }
        System.out.print(res);
    }
}