携程笔试 携程笔试题 0415
笔试时间：2025年04月15日
历史笔试传送门：
第一题
题目
首先将每个字符串中把每个字母去重(多次出现只保留最先出现的那个字母)，若两个字符串一致，我们则认为两个字符串相似。游游会提出多此询问，请你帮助她判断两个字符串是否相似。
输入描述
每个测试文件均包含多组测试数。
第一行输入一个整数 T(1 <= T <=1000),代表数据组数,每组测试数据描述如下:
对于每一组测试数据:2 行，每行一个字符串。
分别代表81和82,输入保证仅有小写字母组成且长度不超过 10^5。
数据保证单个测试文件的所有字符串长度之和不超过10^5
输出描述
对于每一组数据，若两个字符串相似，输出"YES",否则输出"NO"。
样例输入
2
aba
abba
ac
ca
样例输出
Yes
NO
参考题解
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
string dedup(const string &s) {
string result;
unordered_set<char> seen;
for (char c : s) {
if (!seen.count(c)) {
seen.insert(c);
result += c;
}
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
string s1, s2;
while (t--) {
cin >> s1 >> s2;
string d1 = dedup(s1);
string d2 = dedup(s2);
cout << (d1 == d2 ? "YES\n" : "NO\n");
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashSet;
import java.util.Set;
public class Main {
static String dedup(String s) {
StringBuilder sb = new StringBuilder();
Set<Character> seen = new HashSet<>();
for (char c : s.toCharArray()) {
if (seen.add(c)) {
sb.append(c);
}
}
return sb.toString();
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
String s1 = br.readLine();
String s2 = br.readLine();
String d1 = dedup(s1);
String d2 = dedup(s2);
System.out.println(d1.equals(d2) ? "YES" : "NO");
}
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def dedup(s):
result = ""
seen = set()
for char in s:
if char notin seen:
seen.add(char)
result += char
return result
t = int(input())
while t > 0:
t -= 1
s1 = input()
s2 = input()
dedup_s1 = dedup(s1)
dedup_s2 = dedup(s2)
if dedup_s1 == dedup_s2:
print("YES")
else:
print("NO")
第二题
题目：最大收益
游游现在有一个公司，这个公司里有n个任务，每一个任务都有一个能力值和收益值，现在有m个工人，每一个工人都有一个能力值，对于每一个任务来说，只有这个人的能力值不低于该任务需要的能力值，才可以完成这个任务。假设多个工人可以完成,同一个任务，收益为这个任务的收益值乘以这个任务完成的次数，现在想知道每一个工人最多只能安排一个任务的前提下，最大的收益值是多少？
输入描述
每一个文件输入第一行输入一个整数T（1<=T<=100)，代表有T组测试数据。
接下来T组，每一组第一行输入两个整数n,m(1≤n,m≤10^4)第二行输入n个整数，其中ai代表第i个任务所需要的的能力值
第三行输入n个整数，其中p[i](1 ≤ p[i]≤10^5)代表第i个任务的收益第四行输入m个整数，其中b[i](1 ≤ b[i]≤10^5)代表第i个工人的能力数据保证同一个文件内n的总和不超过10^5，m的总和不超过10^5数据保证同一个文件内n的总和不超过10^5，m的总和不超过10^5
输出描述
对于每一组测试数据，输出一个答案代表最大的收益。
样例输入
1
5 4
2 4 6 8 10
10 20 30 40 50
4 5 6 7
样例输出
100
说明：对于样例:我们选择前两个工人做第二个任务，第三个工人和第四个工人做第三个任务，此时收益最大
参考题解
贪心
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
struct Task {
int ability;
int profit;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<int> abilities(n), profits(n), workers(m);
for (int i = 0; i < n; ++i) cin >> abilities[i];
for (int i = 0; i < n; ++i) cin >> profits[i];
for (int i = 0; i < m; ++i) cin >> workers[i];
vector<Task> tasks(n);
for (int i = 0; i < n; ++i) {
tasks[i] = {abilities[i], profits[i]};
}
sort(tasks.begin(), tasks.end(),
[](const Task &a, const Task &b){ return a.ability < b.ability; });
sort(workers.begin(), workers.end());
long long total = 0;
int idx = 0;
// max-heap of available profits
priority_queue<int> pq;
for (int w : workers) {
while (idx < n && tasks[idx].ability <= w) {
pq.push(tasks[idx].profit);
++idx;
}
if (!pq.empty()) {
total += pq.top();
}
}
cout << total << "\n";
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Main {
static class Task {
int ability, profit;
Task(int a, int p) { ability = a; profit = p; }
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine().trim());
while (T-- > 0) {
String[] line = br.readLine().split("\\s+");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
int[] abilities = new int[n];
int[] profits = new int[n];
int[] workers = new int[m];
line = br.readLine().split("\\s+");
for (int i = 0; i < n; i++) abilities[i] = Integer.parseInt(line[i]);
line = br.readLine().split("\\s+");
for (int i = 0; i < n; i++) profits[i] = Integer.parseInt(line[i]);
line = br.readLine().split("\\s+");
for (int i = 0; i < m; i++) workers[i] = Integer.parseInt(line[i]);
List<Task> tasks = new ArrayList<>();
for (int i = 0; i < n; i++) {
tasks.add(new Task(abilities[i], profits[i]));
}
tasks.sort(Comparator.comparingInt(t -> t.ability));
Arrays.sort(workers);
long total = 0;
int idx = 0;
// max-heap for available profits
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int w : workers) {
while (idx < n && tasks.g
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
