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

第一题

题目描述

小美在摆弄她的字符串。最近小团送了小美一个特殊字符 ‘*’，这个字符可以和其他所有字符匹配，除了这个字符外，其他字符只能自己和自己匹配。小美先前有一个字符串 S，长度为 n，现在她又新组合了一个可有特殊字符 ‘*’ 的字符串 s，长度为 m。小美想知道有多少个位置 i，使得 S[i+j] 与 s[j] 对于 1≤j≤m 均能匹配上？其中 X[y] 代表字符串 X 中第 y 位的字符。

测试样例

第一行两个空格隔开的正整数 n 和 m，分别表示字符串 S 和字符串 s 的长度；
接下来一行长度为 n 的仅包含小写英文字母的字符串 S；
接下来一行长度为 m 的包含小写英文字母以及特殊字符 ‘*’ 的字符串 s；
对于所有数据，1≤m≤n≤2000，输出一行一个整数，表示满足要求的位置数量

测试样例 1

输入
7 3
abcaacc
a*c
输出
3

样例 1 解释
可以对 i=0,3,4 这三个位置的子串 abc、aac、acc 匹配上 a*c，即
abcaacc
abcaacc
abcaacc

思路与代码

模拟即可。

 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 class Main {
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int n = in.nextInt(), m = in.nextInt();
      char[] S = in.next().trim().toCharArray();
      char[] s = in.next().trim().toCharArray();

      if (n == m) {
         System.out.println(Arrays.equals(S, s) ? 1 : 0);
         return;
      }

      int res = 0;
      for (int i = 0; i <= n - m; i++) {
         if (S[i] == s[0] || s[0] == '*') {
               int j = 0;
               for (; j < m; j++) {
                  if (s[j] == '*') continue;
                  if (S[i + j] != s[j]) break;
               }
               if (j == m) res++;
         }
      }
      System.out.println(res);
   }
}

第二题

题目描述

小美有一个精致的珠宝链子。初始这个链子上有 n 个宝石，从左到右分别编号为 1~n（宝石上的编号不会因为交换位置而改变编号）。接着，小美为了美观对这个项链进行微调，有 m 次操作，每次选择一个编号 x ,将编号 x 的宝石放到最左边（不改变其他宝石的相对位置）。小美想知道，所有操作完成后最终链子从左到右宝石编号是多少。

测试样例

第一行两个正整数 n 和 m，分别表示链子上的宝石数和操作次数。
接下来一行 m 个数 x1,x2,…,xm，依次表示每次操作选择的编号 x 值。
数字间两两有空格隔开
对于所有数据，1≤m,n≤50000, 1≤xi≤n，输出一行 n 个整数，表示答案。

测试样例 1

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

样例 1 解释
第一次微调完，链子为 2 1 3 4 5
第二次微调完，链子为 3 2 1 4 5
第三次微调完，链子为 4 3 2 1 5

思路与代码

语法题，使用双端队列模拟即可。将指定的宝石从链子中移除，并将其添加到链子头部。

 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
import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int n = in.nextInt(), m = in.nextInt();
      int[] ops = new int[m];
      for (int i = 0; i < m; i++) {
         ops[i] = in.nextInt();
      }

      ArrayDeque<Integer> deque = new ArrayDeque<>();
      for (int i = 0; i < n; i++) {
         deque.offerLast(i + 1);
      }

      for (int op : ops) {
         deque.remove(op);
         deque.offerFirst(op);
      }

      for (int i = 0; i < n; i++) {
         System.out.printf("%d ", deque.removeFirst());
      }
   }
}

第三题

题目描述

小团最近获得了美美团团国的裁缝资格证，成为了一个裁缝！现在小团有一个长度为 n 的大布料 S（在这个国家布料其实是一个仅包含小写英文字母的字符串），小团可以将布料在任意位置剪切，例如布料 abcd 可以被裁剪为 a 与 bcd 或 ab 与 cd 或 abc 与 d，不过，裁剪完之后是不能拼接起来的，因为小团还不是很擅长拼接布料。现在小团想知道能不能有一种裁剪方式能让他把布料恰好裁剪成客人要求的小布料。形式化地，有一个串 S，问是否能将其划分成 m 个不相交的连续子串，使得这些连续子串可以与要求的连续子串一一对应。两个串相对应是指这两个串完全相等。例如"aab"=“aab” 但 “aab”≠“baa”。

测试样例

第一行两个空格隔开的正整数 n 和 m，分别表示大布料 S 长度和客人要求的小布料数量。
接下来一行一个长度为 n 的仅包含小写英文字母的串 S，表示大布料的组成。
接下来一行 m 个空格隔开的数 x1,x2, …,xm，依次表示所要求的小布料长度。
接下来开始 m 行，每行一个长度为 xi 的仅包含小写英文字母的串 si，表示第 i 个小布料的组成。

如果存在这样的方案，输出方案总数。如果不存在任何方案，输出 0。
两个方案 A、B 不相同当且仅当方案 A 中存在一个相对于原始长布料的裁剪位置 i，而方案 B 中并未在该位置 i 裁剪。
例如 aaaaaa 裁剪方案 aaa|aaa 与方案 aaa|aaa 是相同的方案。而方案 aa|aaaa 与方案 aaaa|aa 是不同的方案，
虽然划分出的结果都是 aa 与 aaaa，但前者在第二个 a 处进行了裁剪，后者并没有在这里进行裁剪，所以视为不同的裁剪方案。

测试样例 1

输入
6 2
aaaaaa
4 2
aaaa
aa 输出
2

样例 1 解释
有两种方案，第一种是 aaaa|aa，第二种是 aa|aaaa，代表一次裁剪。

思路与代码

根据子集/排列思想，本题元素可重但不可复选。

 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
public class Main {
   static int res = 0;

   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int n = in.nextInt(), m = in.nextInt();
      in.nextLine();
      String S = in.nextLine().trim();
      in.nextLine();
      String[] fragments = new String[m];
      for (int i = 0; i < m; i++) {
         fragments[i] = in.next().trim();
      }

      // 如果长度相同，则按照字典序排序，否则按照长度排序
      Arrays.sort(fragments, ((o1, o2) -> {
         if (o1.length() == o2.length()) return o1.compareTo(o2);
         else return o1.length() - o2.length();
      }));

      backtrack(S, new StringBuilder(), fragments, new boolean[m]);
      System.out.println(res);
   }

   private static void backtrack(String S, StringBuilder sb, String[] fragments, boolean[] used) {
      if (S.equals(sb.toString())) {
         res++;
         return;
      }
      for (int i = 0; i < fragments.length; i++) {
         // 元素可重，但不可复选
         if (i > 0 && fragments[i].equals(fragments[i - 1]) && used[i - 1]) continue;
         if (used[i]) continue;

         sb.append(fragments[i]);
         used[i] = true;
         backtrack(S, sb, fragments, used);
         sb.replace(sb.length() - fragments[i].length(), sb.length(), "");
         used[i] = false;
      }
   }
}

第四题

题目描述

小团正忙着用机器人收衣服！因为快要下雨了，小团找来了不少机器人帮忙收衣服。他有 n 件衣服从左到右成一行排列，所在位置分别为 1~n，在每个位置上已经有一个就绪的机器人可以帮忙收衣服，但第 i 个位置上的机器人需要 pi 的电量来启动，然后这个机器人会用 ti 的时间收衣服，当它收完当前衣服后，会尝试去收紧邻的右边的一件衣服 (如果存在的话)，即 i+1 处的衣服，如果 i+1 处的衣服已经被其他机器人收了或者其他机器人正在收，这个机器人就会进入休眠状态，不再收衣服。不过如果机器人没有休眠，它会同样以 ti 时间来收这件 i+1 处的衣服（注意，不是 ti+1 的时间，收衣服的时间为每个机器人固有属性），然后它会做同样的检测来看能否继续收 i+2 处的衣服，一直直到它进入休眠状态或者右边没有衣服可以收了。形象地来说，机器人会一直尝试往右边收衣服，收 k 件的话就耗费 k*ti 的时间，但是当它遇见其他机器人工作的痕迹，就会认为后面的事情它不用管了，开始摸鱼，进入休眠状态。小团手里总共有电量 b，他准备在 0 时刻的时候将所有他想启动的机器人全部一起启动，过后不再启动新的机器人，并且启动的机器人的电量之和不大于 b。他想知道在最佳选择的情况下，最快多久能收完衣服。若无论如何怎样都收不完衣服，输出 -1。

测试样例

第一行两个正整数 n 和 b，分别表示衣服数量和小团持有电量。
接下来一行 n 个数 p1,p2, …,pn，含义如题所述，为机器人唤醒需求电量。
接下来一行 n 个数 t1,t2, …,tn，含义如题所述，为机器人收衣服所需时间。
数字间两两有空格隔开。
输出最短所需时间。

测试样例 1

输入
3 5
1 2 3
7 5 3
输出
10

样例 1 解释
可以同时启动第一个机器人和第二个机器人，耗电量为 1+2=3，这样花费时间为 max(7, 52)=10
也可以同时启动第一个机器人和第三个机器人，耗电量为 1+3=4，这样花费时间为 max(72, 3)=14
所以答案为 10

测试样例 2

输入
3 5
6 2 3
7 5 3
输出
-1

样例 2 解释因为必须要启动第一个机器人，耗电量至少为 6，但是持有电量只有 5，因此无法收完所有衣服，输出 -1

思路与代码

// TODO

1
// TODO  

第五题

题目描述

小美在回家路上碰见很多缠人的可爱猫猫！因为猫猫太可爱了以及小美十分有爱心，每遇到一只猫猫，小美忍不住停下来花费 T 的时间抚摸猫猫让猫猫不再缠着小美。而一路上小美能捡到很多亮闪闪的小玩具，这里我们给每个小玩具的种类都编了号，从 1~k，一共 k 种小玩具，对于每个所属种类 i 的小玩具，小美可以选择将它送给遇到的一只猫猫玩，这样的话可以只花费 ti 的时间就可以让这只猫猫心满意足的离开。小美想知道，在她以最佳的对小玩具的用法下，她最少耗费多少时间在打发猫猫（即只考虑摸猫时间以及用小玩具打发猫的时间）。注意，每个捡到的小玩具只能用一次。

测试样例

第一行三个正整数 n、k 和 T，分别表示小美回家遇见的事件数、小玩具种类总数以及摸猫时间！
接下来一行 k 个数 t1,t2, …,tk, 含义如题所述，为每种小玩具打发猫猫所用时间。
接下来一行 n 个数 e1,e2, …,en，表示 n 次事件，对第 i 次事件，如果 ei=0，则表示遇到了一只猫猫，小美可以选择花费 T 的时间去抚摸，或者用一个小玩具送给猫猫来打发它 (如果小美有的话)。
如果 ei>0，则表示小美在这里捡到了一个小玩具，种类为 ei。初始时候小美身上没有任何小玩具，她可以携带任意多个小玩具。
输出最少耗费多少时间在打发猫猫（即只考虑摸猫时间以及用小玩具打发猫的时间）。

测试样例 1

输入
6 2 100
1 50
0 1 2 0 1 0
输出
102

样例 1 解释
一开始没有小玩具，遇到一只猫猫只能抚摸，花费了 100 的时间。
接下来获得了小玩具 1 和 2，然后遇到一只猫猫，用了小玩具 1，只花费了 1 的时间。
接下来又获得一个小玩具 1 之后又遇见一只猫猫，因为又有小玩具 1 了，所以还是只用花费 1 的时间。
总共用时 102

思路与代码

贪心法。使用 PriorityQueue 将所有的玩具打发猫猫的时间存储起来，如果玩具打发猫猫的时间大于抚摸猫猫的时间，则该玩具不要也罢。

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

      int res = 0;
      PriorityQueue<Integer> timeOfToys = new PriorityQueue<>();

      for (int i = 0; i < n; i++) {
         if (e[i] == 0) {
               if (timeOfToys.isEmpty()) res += T;
               else res += timeOfToys.poll();
         } else {
               if (t[e[i] - 1] > T) continue;
               timeOfToys.add(t[e[i] - 1]);
         }
      }
      System.out.println(res);
   }
}