笔试

美团后端 20200813

1. 魔法外卖

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

package meituan.bishi.one;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int t = sc.nextInt();
        int[] ans = new int[n];
        for (int i = 0;i < n;i++){
            ans[i] = sc.nextInt();
        }
        Arrays.sort(ans);
        int sum = 0;
        int time = 0;
        for (int i = 0;i < n;i++){
            if(time + t > ans[i]){
                sum++;
            }else{
                time += t;
            }
        }
        System.out.println(sum);
    }
}
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

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 的情况，第二行输出一个正整数，表示还剩几个地块没有打扫。

package meituan.bishi.two;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] res = new int[n][m];
        int len = sc.nextInt();
        String sb = sc.next();
        int num = 0;
        for (int i = 0;i < n;i++){
            for (int j = 0;j < m;j++){
                res[i][j] = 1;
            }
        }
        int row = 0;
        int col = 0;
        res[0][0] = 0;
        num++;
        int cnt = 0;
        for (char c : sb.toCharArray()){
            if(c=='W'){
                row--;
                cnt++;
                if(res[row][col]==1){
                    res[row][col]=0;
                    num++;
                    if (num==n*m){
                        System.out.println("Yes");
                        System.out.println(cnt);
                    }
                }
            }
            if(c=='A'){
                col--;
                cnt++;
                if(res[row][col]==1){
                    res[row][col]=0;
                    num++;
                    if (num==n*m){
                        System.out.println("Yes");
                        System.out.println(cnt);
                    }
                }
            }
            if(c=='S'){
                row++;
                cnt++;
                if(res[row][col]==1){
                    res[row][col]=0;
                    num++;
                    if (num==n*m){
                        System.out.println("Yes");
                        System.out.println(cnt);
                    }
                }
            }
            if(c=='D'){
                col++;
                cnt++;
                if(res[row][col]==1){
                    res[row][col]=0;
                    num++;
                    if (num==n*m){
                        System.out.println("Yes");
                        System.out.println(cnt);
                    }
                }
            }
        }
        if (num<n*m){
            System.out.println("No");
            System.out.println(n*m-num);
        }
    }
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

3. 扑克

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

package meituan.bishi.three;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dianshu = new int[n];
        for(int i = 0;i < n;i++){
            dianshu[i] = sc.nextInt();
        }
        Deque<Integer> deque = new LinkedList<>();
        for (int i = n - 1;i >= 0;i--){
            if(deque.isEmpty() || deque.size()==1){
                deque.addFirst(dianshu[i]);
            }else{
                deque.addFirst(dianshu[i]);
                for (int j = 0;j < 2;j++){
                    int temp = deque.removeLast();
                    deque.addFirst(temp);
                }
            }
        }
        for (Integer integer : deque){
            System.out.print(integer + " ");
        }
    }
}
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

4. 合法元组数

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

package meituan.bishi.four;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] res = new int[n];
        for(int i = 0;i < n;i++){
            res[i] = sc.nextInt();
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0;i < n;i++){
            if (map.containsKey(res[i])){
                map.get(res[i]).add(i);
            }else{
                map.put(res[i],new ArrayList<>());
                map.get(res[i]).add(i);
            }
        }
        int sum = 0;
        for (int i = 0;i < n;i++){
            for (int j = i + 1;j < n;j++){
                if (map.containsKey(3*res[j]-res[i])){
                    for (Integer integer : map.get(3*res[j]-res[i])){
                        if (integer > j){
                            sum++;
                        }
                    }
                }
            }
        }
        System.out.println(sum);
    }
}
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

5. 生活在树上

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

package meituan.bishi.five;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] tree = new int[n+1];
        for (int i = 1;i < n+1;i++){
            tree[i] = sc.nextInt();
        }
        Main main = new Main();
        long ans = main.dfs(1,n,tree);
        System.out.println(ans);
    }

    long dfs(int root,int n,int[] tree){
        if (root > n){
            return 0;
        }
        return tree[root] + Math.max(dfs(2*root,n,tree),dfs(2*root+1,n,tree));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24