美团 Java 岗算法笔试记录（2022/08/13）

第一题

题目描述

炸鸡店拥有一名会传送魔法的外卖派送员。该外卖派送员派送单子时，可以消耗时间 t 来正常派送单子（一次只能派送一个单子，不能多个同时派送），也可以使用魔法不耗费时间地隔空瞬间投送。现在炸鸡店在时刻 0 接收到了若干炸鸡订单，每个单子都有它的截止送达时间。外卖派送员需要保证送达时间小于等于这个截止时间。现在询问外卖员最少要使用几次魔法来保证没有外卖超时。

测试样例

测试样例 1

输入
6 5
5 6 7 8 9 10
输出
3

测试样例 2

输入
6 5
100 101 102 103 104 105
输出
0

思路与代码

贪心算法。先排序，然后看看每一次送达时间是否能在截止时间前。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public static void main(String[] args) throws IOException {
   Scanner in = new Scanner(System.in);
   int n = in.nextInt(), t = in.nextInt(), time = 0;
   int[] deadline = new int[n];

   for (int i = 0; i < n; i++)
      deadline[i] = in.nextInt();
   Arrays.sort(deadline);

   int res = n;
   for (int i = 0; i < n; i++) {
      if (deadline[i] >= time) {
            res--;
            time += t;
      }
   }
   System.out.println(res);
}

第二题

题目描述

你买了一个扫地机器人，你想要知道这个扫地机器人是否能够将房间打扫干净。为了简化问题，我们不妨假设房间被划分为 n*m 的方格。定义打扫干净为这 n*m 的方格全部被打扫过至少一次。你为扫地机器人下达了若干指令。每个指令为上下左右移动中的一种。机器人会将经过的路径上的方格打扫干净。初始时假设机器人处于第一行第一列的方格中。这个方格初始时会被机器人直接打扫干净。现在询问你机器人能否将房间打扫干净，能则输出 Yes，不能则输出 No。对于 Yes 的情况下，还要求你继续输出到哪个指令结束后，房间就打扫干净了。对于 No 的情况下，还要求你输出还有多少个地块没有打扫干净。保证机器人在打扫的过程中不会越过房间边界。换句话说机器人始终保持在 n*m 的方格图中。

测试样例

测试样例 1

输入
2 2 5
“SDWAS”
输出
“Yes”
3

测试样例 2

输入
2 2 5
“SWSWS”
输出
“No”
2

思路与代码

暴力解法即可。无须考虑边界问题，因为题目已经保证机器人不会越界。

 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
public static void main(String[] args) {
   Scanner in = new Scanner(System.in);

   int n = in.nextInt(), m = in.nextInt(), total = in.nextInt();
   char[] orders = in.next().toCharArray();
   boolean[][] cleaned = new boolean[n][m];

   cleaned[0][0] = true;
   int x = 0, y = 0, remain = n * m - 1;

   for (int i = 0; i < total; i++) {
      char order = orders[i];
      if (order == 'W') {
            x--;
      } else if (order == 'A') {
            y--;
      } else if (order == 'S') {
            x++;
      } else if (order == 'D') {
            y++;
      }
      if (!cleaned[x][y]) {
            remain--;
            cleaned[x][y] = true;
      }
      if (remain == 0) {
            System.out.println("Yes");
            System.out.println(i + 1);
            return;
      }
   }
   System.out.println("No");
   System.out.println(remain);
}

第三题

题目描述

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

测试样例

测试样例 1

输入
4
1 2 3 4
输出
4 2 1 3

样例 1 解释
初始牌堆为：4 2 1 3

Alice 和 Bob 分别操作后牌堆为：1 3 4 2，此时 1 被翻开，牌堆变为 3 4 2
Alice 和 Bob 分别操作后牌堆为：2 3 4，此时 2 被翻开，牌堆变为 3 4
Alice 和 Bob 分别操作后牌堆为：3 4，此时 3 被翻开，牌堆变为 4
Alice 和 Bob 分别操作后牌堆依旧为 4，此时 4 被翻开。

思路与代码

模拟倒推即可。

 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
public static void main(String[] args) {
   Scanner in = new Scanner(System.in);
   int n = in.nextInt();
   int[] poker = new int[n];
   for (int i = 0; i < n; i++) {
      poker[i] = in.nextInt();
   }

   LinkedList<Integer> list = new LinkedList<>();

   // 题干操作顺序
   // for (int i = 0; i < n; ++i) {
   //    list.addLast(list.removeFirst());
   //    list.addLast(list.removeFirst());
   //    poker[i] = list.removeFirst();
   //    System.out.print(poker[i] + " ");
   // }

   for (int i = n - 1; i >= 0; i--) {
      list.addFirst(poker[i]);
      list.addFirst(list.removeLast());
      list.addFirst(list.removeLast());
   }
   for (int i = 0; i < n; i++) {
      System.out.printf("%d ", list.get(i));
   }
}

第四题

题目描述

给一个长度为 n 的序列 a[1], a[2], …, a[n]，请问有多少个三元组 (i,j,k) 满足 i<j<k 且 a[i]-a[j]=2a[j]-a[k]？输出符合要求的三元组的数量。

测试样例

测试样例 1

输入
4
4 2 2 2
输出
3

思路与代码

直接暴力解即可，注意数据范围（使用 long 而不是 int）。

 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
public static void main(String[] args) {
   Scanner in = new Scanner(System.in);

   int n = in.nextInt();
   long[] nums = new long[n];
   HashMap<Long, List<Integer>> map = new HashMap<>();
   for (int i = 0; i < nums.length; i++) {
      nums[i] = in.nextInt();
      List<Integer> index = map.getOrDefault(nums[i], new ArrayList<>());
      index.add(i);
      map.put(nums[i], index);
   }

   int count = 0;
   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
            long target = -1 * (nums[i] - 3 * nums[j]);
            List<Integer> index = map.get(target);
            if (index != null) {
               for (Integer k : index) {
                  if (k > j) count++;
               }
            }
      }
   }
   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] 之间。

测试样例 1

输入
3
5 7 8
输出
13

样例解释 1
该样例中，二叉树上有三个节点，根节点为 1 号节点，其左儿子为 2 号节点，右儿子为 3 号节点，所能获取的最大金钱为 13，为从 1 号节点走到 3 号节点，共获得 5 + 8 = 13 的金钱。

测试样例 2

输入
5
863 163 396 428 90
输出
1454

思路与代码

与 leetcode 124 类似，采用递归的思路，针对根节点 root，分别求得其左右子树中的路径之和较大者，再加上当前根节点 root 节点值（形成一个单臂，即根节点 + 左子节点，或根节点 + 右子节点），最后返回到上一层递归即可。

 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
public static void main(String[] args) {
   Scanner in = new Scanner(System.in);
   int n = in.nextInt();
   int[] arr = new int[n + 1];

   for (int i = 1; i <= n; i++) {
      arr[i] = in.nextInt();
   }

   System.out.println(maxMoney(1, n, arr));
}

public static int maxMoney(int k, int n, int[] arr) {
   int left, right;

   // 获取左子树最大值，若没有左子树，则置为 0
   if (2 * k <= n) left = maxMoney(2 * k, n, arr);
   else left = 0;

   // 获取右子树最大值，若没有左子树，则置为 0
   if (2 * k + 1 <= n) right = maxMoney(2 * k + 1, n, arr);
   else right = 0;

   // 返回左右子树最大值与根节点之和
   return Math.max(left, right) + arr[k];
}

参考文献

1.美团 | 后端笔试第二场 | 8/13