美团笔试 美团笔试题 后端 0810
笔试时间:2024年08月10日 后端笔试
历史笔试传送门:2023秋招笔试合集
第一题
题目:小美的密码
小美准备登录美团,需要输入密码,小美忘记了密码,只记得密码可能是 n个字符串中的一个。小美会按照密码的长度从小到大依次尝试每个字符串,对于相同长度的字符串,小美随机尝试,并且相同的密码只会尝试一次。小美想知道,她最少需要尝试多少次才能登录成功,最多需要尝试多少次才能登录成功。小美不会重新尝试已经尝试过的字符串。成功登录后会立即停止尝试。
输入描述
第一行输入一个整数 n(1<=n<=1000)代表密码字符串的个数。
第二行输入一个只由小写字母组成的字符串 s(1<=|s|<=1000)代表正确的密码。
接下来 n 行,每行输入一个长度不超过 1000的字符串,代表小美记得的密码。
输出描述
在一行上输出两个整数,表示最少和最多尝试次数。
样例输入
4
ab
abc
ab
ac
ac
样例输出
1 2
说明
小美可能按照 ["ab", "ac", "abc"] 的顺序尝试,第一次尝试成功,也可能按照 ["ac", "ab", "abc"] 的顺序尝试,第二次尝试成功。
小美在尝试 "ac" 发现不正确后不会继续尝试 "ac"。
参考题解
哈希表
C++:[此代码未进行大量数据的测试,仅供参考]
#include <iostream> #include <vector> #include <unordered_map> #include <set> #include <algorithm> using namespace std; int main() { int n; cin >> n; string ans; cin >> ans; unordered_map<int, set<string>> pos; for (int i = 0; i < n; ++i) { string p; cin >> p; pos[p.size()].insert(p); } vector<pair<int, set<string>>> sorted_pos(pos.begin(), pos.end()); sort(sorted_pos.begin(), sorted_pos.end()); int step = 0; int MIN = -1, MAX = -1; for (const auto& [k, v] : sorted_pos) { if (v.find(ans) != v.end()) { MIN = step + 1; MAX = step + v.size(); } else { step += v.size(); } } cout << MIN << " " << MAX << endl; return 0; }
Java:[此代码未进行大量数据的测试,仅供参考]
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); String ans = scanner.next(); Map<Integer, Set<String>> pos = new HashMap<>(); for (int i = 0; i < n; i++) { String p = scanner.next(); pos.computeIfAbsent(p.length(), k -> new HashSet<>()).add(p); } List<Map.Entry<Integer, Set<String>>> sortedPos = new ArrayList<>(pos.entrySet()); sortedPos.sort(Map.Entry.comparingByKey()); int step = 0; int MIN = -1, MAX = -1; for (Map.Entry<Integer, Set<String>> entry : sortedPos) { Set<String> v = entry.getValue(); if (v.contains(ans)) { MIN = step + 1; MAX = step + v.size(); } else { step += v.size(); } } System.out.println(MIN + " " + MAX); scanner.close(); } }
Python:[此代码未进行大量数据的测试,仅供参考]
from collections import defaultdict n = int(input()) ans = input() pos = defaultdict(set) for _ in range(n): p = input() pos[len(p)].add(p) pos = dict(sorted(pos.items())) step = 0 MIN,MAX = -1,-1 for k,v in pos.items(): if ans in v: MIN =step + 1 MAX = step + len(v) else: step += len(v) print(MIN, MAX)
第二题
题目:小美的数组删除
小美有一个长度为 n 的数组 a1,a2,....,an ,他可以对数组进行如下操作:
- 删除第一个元素 a1,同时数组的长度减一,花费为 x。
- 删除整个数组,花费为 k*MEX(a) (其中 MEX(a) 表示 a 中未出现过的最小非负整数。例如 [0,1,2,4] 的 MEX 为 3 )。
小美想知道将 a 数组全部清空的最小代价是多少,请你帮帮他吧。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1<=T<=1000) 代表数据组数,每组测试数据描述如下:
第一行输入三个正整数 n,k,x(1<=n<=2*10^5, 1<=k,x<=10^9) 代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。
第二行输入 n 个整数 a1,a2,....,an(0<=ai<=n),表示数组元素。
除此之外,保证所有的 n 之和不超过 2*10^5。
输出描述
对于每一组测试数据,在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。
样例输入
1
6 3 3
4 5 2 3 1 0
样例输出
15
说明:
若不执行操作一就全部删除,MEX{4,5,2,3,1,0} = 6,花费 18 ;
若执行一次操作一后全部删除,MEX{5,2,3,1,0} = 4,花费 3+12;
若执行两次操作一后全部删除,MEX{2,3,1,0} = 4,花费 6+12 ;
若执行三次操作一后全部删除,MEX{3,1,0} = 2,花费 9+6 ;
若执行四次操作一后全部删除,MEX{1,0} = 2,花费 12+6 ;
若执行五次操作一后全部删除,MEX{0} = 1,花费 15+3;
若执行六次操作一,MEX{} = 0,花费 18;
参考题解
动态规划+维护动态最小未出现的整数。f[i]表示从i往后考虑的最小花费,选择就是选择第一个元素或者直接删除后续所有的元素。对于删除后续所有的元素的选项,我们必须要直到MEX是多少,我们可以用在更新dp的过程中,用一个suffix不断地更新当前的最小未出现的整数。虽然这里出现了两层循环的嵌套,但是并不会重置参数,因此复杂度是O(n).
C++:[此代码未进行大量数据的测试,仅供参考]
#include <iostream> #include <vector> #include <set> #include <algorithm> #include <climits> using namespace std; int main() { int T; cin >> T; while (T--) { long long n, k, x; cin >> n >> k >> x; vector<long long> A(n); for (int i = 0; i < n; ++i) { cin >> A[i]; } vector<long long> dp(n + 1, LLONG_MAX); dp[n] = 0; set<int> vst; int suffix_MEX = 0; for (int i = n - 1; i >= 0; --i) { vst.insert(A[i]); while (vst.count(suffix_MEX)) { suffix_MEX++; } dp[i] = min(dp[i + 1] + x, k * suffix_MEX); } cout << dp[0] << endl; } return 0; }
Java:[此代码未进行大量数据的测试,仅供参考]
import java.util.*; public class Main { public static void main(Strin
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。