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

第一题

题目描述

小团想要自己来烤串！不过在烤串之前，需要串好烤串。小团有 n 个荤菜和 n 个素菜，他想按顺序分别一个荤菜一个素菜串起来，想请你帮他串好！给出两个长度分别为 n 的仅包含小写英文字母的串 A 和 B，分别代表荤菜和素菜的种类（用字母来表示菜的种类）。请你以从左到右的顺序依次串好他们！例如对于荤菜串 A1A2…An 和素菜串 B1B2…Bn，串好应该是 A1B1A2B2…AnBn。

测试样例

第一行一个正整数 n，表示烤串长度；第二行为一个长度为 n 的字符串 A，表示荤菜按次序都是哪些菜；第三行为一个长度为 n 的字符串 B，表示素菜按次序都是哪些菜；对于 80% 的数据，n≤1000，对于 20% 的数据，n≤50000。于所有数据，A 和 B 为仅包含小写英文字母的字符串；输出一行，包含 2n 个字符串表示串好的烤串。

测试样例 1

输入
4
abcd
efgh
输出
aebfcgdh

思路与代码

语法题，直接交替插入两个字符串的字符即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Main {
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int n = in.nextInt();
      in.nextLine();
      String A = in.nextLine();
      String B = in.nextLine();

      StringBuilder builder = new StringBuilder();
      for (int i = 0; i < n; i++) {
         builder.append(A.charAt(i));
         builder.append(B.charAt(i));
      }
      System.out.println(builder);
   }
}

第二题

题目描述

小团在地图上放了三个定位装置，想依赖他们来进行定位！小团的地图是一个 n×n 的一个棋盘，他在 (x1,y1),(x2,y2),(x3,y3) xi,yi ∈ Z ∩ [1,n] 这三个位置分别放置了一个定位装置（两两不重叠）。然后小团在一个特定的位置 (a,b)a,b ∈ Z ∩[1,n] 放置了一个信标。每个信标会告诉小团它自身到那个信标的曼哈顿距离，即对 i=1,2,3 小团知道 (|xi-a|+|yi-b|)，现在小团想让你帮他找出信标的位置！注意，题目保证最少有一个正确的信标位置。因为小团不能定位装置确定出来的信标位置是否唯一，如果有多个，输出字典序最小的那个。(a,b) 的字典序比 (c,d) 小，当且仅当 a<c 或者 a==c∧b<d。

测试样例

第一行一个正整数 n，表示棋盘大小；
第二行两个整数，分别表示 x1 与 y1，即第一个定位器的位置；
第三行两个整数，分别表示 x2 与 y2，即第二个定位器的位置；
第四行两个整数，分别表示 x3 与 y3，即第三个定位器的位置；
第五行三个整数，分别表示第一、二、三个定位器到信标的曼哈顿距离。第 i 个定位器到信标的曼哈顿距离即 (|xi-a|+|yi-b|)；
数字间两两有空格隔开，对于所有数据，n≤50000, 1≤xi,yi≤n，输出一行两个整数，表示字典序最小的可能的信标位置。

测试样例 1

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

样例 1 解释
与 (2, 1) 的哈曼顿距离为 2 的位置有三个，分别是 (1, 2), (2, 3), (3, 2)
与 (2, 2) 的哈曼顿距离为 1 的位置有四个，分别是 (1, 2), (2, 1), (2, 3), (3, 2)
与 (2, 3) 的哈曼顿距离为 2 的位置有三个，分别是 (1, 2), (2, 1), (3, 2)
所以只有 (1, 2), (3, 2) 这两个位置有可能是信标，而 (1, 2) 的字典序最小，所以输出 (1, 2)

思路与代码

曼哈顿距离即水平和竖直方向上的距离之和。使用 directions 表示方向，对距离 $d$ 进行遍历，若水平方向取距离 $d_x$，则竖直方向距离 $d_y = d - d_x$，枚举出所有点后判断点是否在边界内，若在则有效。

 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
public class Main {
   static int[][] directions = {{1, -1}, {1, 1}, {-1, 1}, {-1, -1}};

   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int n = in.nextInt();
      int x1 = in.nextInt(), y1 = in.nextInt();
      int x2 = in.nextInt(), y2 = in.nextInt();
      int x3 = in.nextInt(), y3 = in.nextInt();
      int d1 = in.nextInt(), d2 = in.nextInt(), d3 = in.nextInt();

      Set<String> set1 = getAdjoin(n, x1, y1, d1);
      Set<String> set2 = getAdjoin(n, x2, y2, d2);
      Set<String> set3 = getAdjoin(n, x3, y3, d3);

      PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
         if (a[0] == b[0]) return a[1] - b[1];
         else return a[0] - b[0];
      });

      for (String s : set1) {
         if (set2.contains(s) && set3.contains(s)) {
               String[] pair = s.split("-");
               queue.offer(new int[]{Integer.parseInt(pair[0]), Integer.parseInt(pair[1])});
         }
      }

      int[] pair = queue.poll();
      System.out.println(pair[0] + " " + pair[1]);
   }

   static Set<String> getAdjoin(int n, int x, int y, int d) {
      Set<String> set = new HashSet<>();
      for (int i = d; i >= 0; i--) {
         for (int[] dir : directions) {
               int newX = x + i * dir[0], newY = y + (d - i) * dir[1];
               if (newX >= 1 && newX <= n && newY >= 1 && newY <= n)
                  set.add(newX + "-" + newY);
         }
      }
      return set;
   }
}

第三题

题目描述

小美即将进行期末考试！小美现在盘算了一下，一共有 n 道试题，对于第 i 道试题，小美有着 pi 的概率做对，获得 ai 的分值，另外 (1-pi) 的概率做错，获得 0 分。小美的总分即是每道题获得的分数之和。小美不甘于此！她决定突击复习，因为时间有限，她最多复习 m 道试题，使得复习后的试题正确率提升到 100%。小美想知道，如果她以最佳方式进行复习，能获得的期望总分最大是多少。

测试样例

第一行两个正整数 n 和 m，表示总试题数和最多复习试题数。
接下来一行 n 个整数，分别为 p1 p2…pn，表示小美有 pi%的概率，即 pi=pi/100 的概率做对第 i 个题。（注意，这里为了简单起见，将概率 pi 扩张 100 倍成为整数 pi 方便输入）
接下来一行 n 个整数，分别表示 a1 a2…an，分别表示第 i 个题做对的分值。
数字间两两有空格隔开，对于所有数据，1≤m≤n≤50000,0≤pi≤100,1≤ai≤1000
输出一行一个恰好两位的小数，表示能获得的最大期望总分。（如果答案为 10 应输出 10.00，2.5 应输出 2.50）

测试样例 1

输入
2 1
89 38
445 754
输出
1150.05

样例 1 解释
如果都不复习，小美总分的期望为 89% * 445 + 38% * 754 = 682.57
如果复习第一道题，小美总分的期望为 100% * 445 + 38% * 754 = 731.52
如果复习第二道题，小美总分的期望为 89% * 445 + 100% * 754 = 1150.05
所以选择复习第二道题，这样能获得最大期望总分 1150.05
根据每题复习后的收益进行排序即可

思路与代码

自定义数据结构 Pair，使用 PriorityQueue 对 Pair 按照收益倒序排列，即收益最大的课排在前。再通过贪心法，选取前 $m$ 门收益最大的课进行复习，剩余 $n-m$ 门课则不复习。

 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
class Main {
   static class Pair {
      int a;  // 满分
      double diff;  // 满分与不复习得分的差值（收益）

      public Pair(int a, double diff) {
         this.a = a;
         this.diff = diff;
      }
   }

   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int n = in.nextInt(), m = in.nextInt();
      int[] p = new int[n], a = new int[n];
      PriorityQueue<Pair> queue = new PriorityQueue<>((o1, o2) -> {
         return o2.diff - o1.diff;
      });

      for (int i = 0; i < n; i++) {
         p[i] = in.nextInt();
      }
      for (int i = 0; i < n; i++) {
         a[i] = in.nextInt();
      }
      for (int i = 0; i < n; i++) {
         queue.offer(new Pair(a[i], a[i] * (1 - p[i] / 100.0)));
      }

      double res = 0;
      for (int i = 0; i < n; i++) {
         Pair pair = queue.poll();
         if (i < m) {
               res += pair.a;
         } else {
               res += pair.a - pair.diff;
         }
      }
      System.out.println(res);
   }
}

第四题

题目描述

小团生日收到妈妈送的两个一模一样的数列作为礼物！他很开心的把玩，不过不小心没拿稳将数列摔坏了！现在他手上的两个数列分别为 A 和 B，长度分别为 n 和 m。小团很想再次让这两个数列变得一样。他现在能做两种操作，操作一是将一个选定数列中的某一个数 a 改成数 b，这会花费|b-a|的时间，操作二是选择一个数列中某个数 a，将它从数列中丢掉，花费|a|的时间。小团想知道，他最少能以多少时间将这两个数列变得再次相同！

测试样例

第一行两个空格隔开的正整数 n 和 m，分别表示数列 A 和 B 的长度。
接下来一行 n 个整数，分别为 A1 A2…An
接下来一行 m 个整数，分别为 B1 B2…Bm
对于所有数据，1≤n,m≤2000， |Ai|,|Bi|≤10。输出一行一个整数，表示最少花费时间，来使得两个数列相同。

测试样例 1

输入
1 1
-9821
7742
输出
17563

样例 1 解释
可以选择两次第二种操作，消除数列 A 的第一个数和数列 B 的第一个数，需要花费 9821+7742=17563 的时间
也可以选择一次第一种操作，将数列 A 的第一个数改成数列 B 的第一个数，也是需要花费 9821+7742=17563 的时间
所以答案为 17563

思路与代码

动态规划，与 leetcode 72.编辑距离类似，但要注意设置本题的边界条件。

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

      int[][] dp = new int[n + 1][m + 1];
      // 丢掉 A[i]
      for (int i = 1; i <= n; i++) {
         dp[i][0] = dp[i - 1][0] + Math.abs(A[i - 1]);
      }
      // 丢掉 B[i]
      for (int i = 1; i <= m; i++) {
         dp[0][i] = dp[0][i - 1] + Math.abs(B[i - 1]);
      }
      for (int i = 1; i <= n; i++) {
         int a = A[i - 1];
         for (int j = 1; j <= m; j++) {
               int b = B[j - 1];
               if (a == b) {
                  dp[i][j] = dp[i - 1][j - 1];
               } else {
                  dp[i][j] = Math.min(dp[i - 1][j - 1] + Math.abs(b - a),
                           Math.min(dp[i - 1][j] + Math.abs(a), dp[i][j - 1] + Math.abs(b)));
               }
         }
      }
      System.out.println(dp[n][m]);
   }
}

第五题

题目描述

小团的玩具火箭有点磨损了，上面有很多地方翘起来了，小团想要用强力胶进行修补，但在强力胶凝结之前，需要找点东西压住。幸好小团有很多这样的东西。小团有 m 种配重材料，第 i 种材料重 ai 单位重量（因为小团有太多了，可以认为每种都有任意多个）。火箭上有 n 个地方翘起来了，需要至少 bi 单位重量的东西来压住，而且只能用一个配重材料来压，(多了的话不好压，多个配重材料容易散开，所以小团不想用多个来折腾)。小团想一次就把所有翘起来的地方全都修补好，请问他需要使用的配重材料重量之和最少是多少？

测试样例

第一行两个正整数 n 和 m，分别代表需要修补的地方个数以及材料种类数。
接下来一行 n 个数 b1,b2,…,bn，含义如题。
接下来一行 m 个数 a1,a2,…,am，含义如题。
对于 40% 的数据，n,m≤100，对于另外 30% 的数据，n,m≤2000，对于所有数据，1≤n,m≤50000，1≤ai,bi≤104，输出小团最少需要使用的配重材料重量之和。如果没有任何办法满足，输出-1。

测试样例 1

输入
1 1
5
4
输出
-1

样例 1 解释
需要 5 单位重量，只有 4 单位重量的材料，压不住，输出-1。

测试样例 2

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

样例 2 解释
第一个地方需要重量为 4 的，第二个地方可以用重量为 1 的，第三个地方只能选择重量为 4 的才能压住。所以总重量需求为 9。可以证明没有更优方案。

思路与代码

利用 TreeSet 的特性，遍历每个需要的重量 $b_i$，通过 ceiling(bi) 方法得到大于等于 $b_i$ 的最小值，若不存在这样的值则说明压不住，返回-1。或者对材料重量与所需重量排序后，基于上述思路二重遍历即可。

 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
class Main {
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int n = in.nextInt(), m = in.nextInt();
      int[] b = new int[n];
      TreeSet<Integer> ts = new TreeSet<>();

      for (int i = 0; i < n; i++) {
         b[i] = in.nextInt();
      }
      for (int i = 0; i < m; i++) {
         ts.add(in.nextInt());
      }

      long res = 0;
      for (int bi : b) {
         Integer ceiling = ts.ceiling(bi);
         if (ceiling == null) {
            System.out.println(-1);
            return;
         } else {
            res += ceiling;
         }
      }
      System.out.println(res);
   }
}

参考文献

1.08/20 美团后端笔试
2.20220820 美团笔试题解