美团后端笔试2022.08.13

柔光的暖阳◎ 2023-10-11 18:10 14阅读 0赞

#### 文章目录 ####

*  1.魔法外卖
 *  2.打扫房间
 *  3.扑克牌游戏
 *  4.三元组变形问题
 *  附加题：树的分支最大值

昨天刚刚笔试结束，然后今天抽空给大家整理一下，然后简单说一下思路。

整场笔试下来，整体难度一般，只不过在第三题扑克牌游戏的时候进行的不是很顺利，附加题难度一般，不知道有没有小伙伴和我一样时间耗费在第三题上面的。

## 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

这道题目思路很简单，我们只需要保证自己送完前一个的时间+t（送下一个外卖消耗的时间）小于等于下一个外卖的截止时间即可。  
代码如下：（Java版）

import java.util.Arrays;
    import java.util.Scanner;
    
    public class 魔法外卖 {
        
        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的方格全部被打扫过至少一次。
> 
> 你为扫地机器人下达了若干指令。每个指令为上下左右移动中的一种。机器人会将经过的路径上的方格打扫干净。
> 
> 初始时假设机器人处于第一行第一列的方格中。这个方格初始时会被机器人直接打扫干净。
> 
> 现在询问你机器人能否将房间打扫干净，能则输出Yes，不能则输出No。
> 
> 对于Yes的情况下，还要求你继续输出到哪个指令结束后，房间就打扫干净了。
> 
> 对于No的情况下，还要求你输出还有多少个地块没有打扫干净。  
> 保证机器人在打扫的过程中不会越过房间边界。换句话说机器人始终保持在n\*m的方格图中。

输入描述

> 第一行三个正整数n, m, k，以空格分开，表示房间大小n\*m，接下来会有长度为k的指令。
> 
> 第二行长度为k的一个字符串。字符串中仅有下面四种字符（注意：均为大写）
> 
>  *  W：表示下一步机器人将向上移动
>  *  A：表示下一步机器人将向左移动
>  *  S：表示下一步机器人将向下移动
>  *  D：表示下一步机器人将向右移动
> 
> 保证2 <= n, m <= 100, 指令长度 <= 100000

输出描述

> 第一行一个字符串Yes或No表示能否打扫干净
> 
> 对于Yes的情况，第二行输出一个正整数，表示在第几个指令之后已经打扫干净了。
> 
> 注意指令编号从1开始而不是0。
> 
> 对于No的情况，第二行输出一个正整数，表示还剩几个地块没有打扫。

样例输入

> 2 2 5  
> SDWAS
> 
> 样例输出  
> Yes  
> 3

这道题题目很长，我给大家简单翻译一下，就是说机器人从\[0,0\]这个位置出发，默认\[0,0\]这个位置是初始时就被打扫干净的，然后按照我们输入的WASD的指令，上下左右移动，然后判断在有限的指令步数里能不能打扫干净

*  如果能打扫干净，我们需要输出Yes，同时输出对应执行到哪个指令 ，从1开始计数
 *  如果不能打扫干净，我们需要输出No,同时输出还剩几块没有打扫的

这道题目有几点需要我们注意：

*  1.如果指令的长度<地板的数量-1（因为\[0,0\]这个位置初始时是干净的，需要打扫的数量是n\*m-1）,那么一定不能打扫干净
 *  2.如果指令的长度>=地板数量-1，那么也不一定能打扫完，因为有些指令到达的位置很可能是已经打扫过的，所以我们还需记录一下已经被打扫过的位置。

代码如下：(Java版)

import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    public class 打扫房间 {
        
        public static boolean containsVal(List<int[]> list, int i, int j) {
        
            for (int k = 0; k < list.size(); k++) {
        
                int[] t = list.get(k);
                if (t[0] == i && t[1] == j) {
        
                    return true;
                }
    
            }
            return false;
        }
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            String operation = sc.next();
            char[] opt = new char[k];
            for (int i = 0; i < k; i++) {
        
                opt[i] = operation.charAt(i);
            }
            if (k + 1 < n * m) {
        //一定打扫不完
                System.out.println("No");
                System.out.println(n * m - k - 1);
            } else {
        
                int count = 1;//已经被打扫干净的数量
                Integer lastOp = 0;//最后一次执行的指令
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{
        0, 0});//初始位置已经被打扫
                int i = 0, j = 0;//初始值
    
                for (char op : opt) {
        
                    switch (String.valueOf(op)) {
        
                        case "W"://向上
                            if (i - 1 >= 0) {
        
                                i -= 1;
                                int[] t = new int[]{
        i, j};
                                if (!containsVal(list, i, j)) {
        
                                    count++;
                                    list.add(t);
                                }
                            }
    
                            break;
                        case "A"://向左
                            if (j - 1 >= 0) {
        
                                j -= 1;
                                int[] t = new int[]{
        i, j};
                                if (!containsVal(list, i, j)) {
        
                                    count++;
                                    list.add(t);
                                }
                            }
    
                            break;
                        case "S"://向下
                            if (i + 1 < n) {
        
                                i += 1;
                                int[] t = new int[]{
        i, j};
                                if (!containsVal(list, i, j)) {
        
                                    count++;
                                    list.add(t);
                                }
                            }
    
                            break;
                        case "D"://向右
                            if (j + 1 < m) {
        
                                j += 1;
                                int[] t = new int[]{
        i, j};
                                if (!containsVal(list, i, j)) {
        
                                    count++;
                                    list.add(t);
                                }
                            }
    
                            break;
                    }
                    lastOp++;
                    if (count >= m * n) {
        
                        break;
                    }
                }
                if (count >= m * n) {
        
                    System.out.println("Yes");
                    System.out.println(lastOp);
                } else {
        
                    System.out.println("No");
                    System.out.println(n * m - list.size());
                }
    
    
            }
    
    
        }
    
    
    }

## 3.扑克牌游戏 ##

题目描述：

> Alice和Bob在玩一个游戏。有n张卡牌，点数分别为1到n。进行洗牌后，n张牌从上到下叠放形成一个牌堆。
> 
> 每次Alice先将当前牌堆顶的一张牌放到牌堆底，然后Bob再将当前牌堆顶的一张牌放到牌堆底。（特别地，当牌堆中只有一张牌时，相当于不进行任何操作）接着，他们会翻开当前牌堆顶的牌，并记下它的点数。
> 
> 当所有牌都被翻开后，他们也记下了n个点数。现在他们想根据记下的这个序列来还原一开始的牌（从牌堆顶到牌堆底每一张牌的点数）。

输入描述:

> 第一行是一个正整数n，表示有n张牌。
> 
> 接下来一行n个用空格隔开的正整数，第i个数a\_i表示第i张被翻开的牌的点数。  
> 1<=n<=100000

输出描述：

> 一行n个用空格隔开的正整数，第i个数表示初始牌堆中从牌堆顶到牌堆底的第i张牌的点数。

样例输入:

> 4  
> 1 2 3 4

样例输出：

> 4 2 1 3

这道题目做了很久，因为一直想着通过递归剪枝的方法去尝试还原初始牌的点数，后来仔细分析了一下，是我想多了，也想错了，题目本身就已经 暗示着我们使用队列来进行处理，所以我们就按照出题人的思路，通过**双端队列+反向模拟**就可以很轻松的解决

为了防止大家看不懂里面的部分指令，给大家先复习一下：  
![在这里插入图片描述][93955711d7274e42ba4c742973ab1451.png_pic_center]

其中Queue就是我们的普通队列，和双端队列Deque不同的是，它不支持从队头添加元素以及从队尾删除元素。

对于这道题目，题目给出的顺序是从a\[\]数组的0号位置开始，按顺序将两张牌依次放在a\[\]数组的最后面，然后在抽出一张牌，记录点数，我们只需翻过来，从a\[length-1\]开始的位置，进行同样的操作，即从队尾依次抽出两张放在队头，然后再抽出一张牌，那么这张牌对应的便是真实的位置。

代码如下：

import java.util.*;
    
    public class 扑克牌游戏 {
        
        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 : origin) {
        
                System.out.print(i + " ");
            }
    
        }
    
    }

## 4.三元组变形问题 ##

题目描述：

> 给一个长度为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

我第一次拿到这个题目，直接使用三个for循环，主要是看看通过率多少，如果比较通过率较高的话就直接直接下一题了，结果发现才70%，然后又简单优化了一下，优化的方式也很简单，我们知道了i,j，就可以计算a\[k\]的值，这样的话时间复杂度就由原来的o(n^3) 变为o(n^2)，但是通过率仍然不是百分之百，但是也提高到了95%，有更好的办法的小伙伴直接评论区给大家长长见识。

package com.exercise.leetecode.problem.美团;
    
    import java.util.*;
    
    public class 三元组变形问题 {
        
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
        
                a[i] = sc.nextInt();
            }
            int count = 0;
            Map<Integer, Integer> map = new HashMap<>();
            for (int k = 0; k < n; k++) {
        
                map.put(a[k], map.getOrDefault(a[k], 0) + 1);
            }
    
            for (int i = 0; i < n - 2; i++) {
        
                map.put(a[i], map.getOrDefault(a[i], 0) - 1);
                Map<Integer, Integer> cpMap = new HashMap<>(map);
                for (int j = i + 1; j < n - 1; j++) {
        
                    cpMap.put(a[j], cpMap.getOrDefault(a[j], 0) - 1);
                    int restNum = 2 * a[j] - a[i] + a[j];
                    count += cpMap.getOrDefault(restNum, 0);
                }
    
            }
            System.out.println(count);
        }
    
    
    }

## 附加题：树的分支最大值 ##

题目描述：

> 给一棵有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

这道附加题的难度都不如第三道题的难度，如果有因为在前面浪费时间太多而导致没有做这道题的小伙伴真的是可惜了呀。

这道题我们也无需构造树状结构，因为左右子树的特征很明显，只需层次遍历即可。

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class 树的分支最大值 {
        
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();//结点个数
            int[] moneys = new int[n + 1];
            for (int i = 1; i <= n; i++) {
        
                moneys[i] = sc.nextInt();
            }
            int[] dp = new int[n + 1];
            Queue<Integer> queue = new LinkedList<>();
            queue.add(1);
            int count = 0;
            while (!queue.isEmpty()) {
        
                int index = queue.poll();
                count++;
                if (index == 1) {
        //说明是根节点
                    dp[index] = moneys[index];
                } else if (index % 2 == 0) {
        //说明是左子树
                    dp[index] = dp[index / 2] + moneys[count];
                } else {
        //说明是右子树
                    dp[index] = dp[(index - 1) / 2] + moneys[count];
                }
                if (index * 2 <= n) {
        
                    queue.add(index * 2);
                }
                if (index * 2 + 1 <= n) {
        
                    queue.add(index * 2+1);
                }
            }
            //找最大值
            int ans = dp[1];
            for (int i : dp) {
        
                ans = Math.max(i, ans);
            }
            System.out.println(ans);
        }
    }

[93955711d7274e42ba4c742973ab1451.png_pic_center]: https://img-blog.csdnimg.cn/93955711d7274e42ba4c742973ab1451.png#pic_center