2020携程4.1后端笔试编程题 2.43
第一题 求最小客服人数
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
携程呼叫中心7×24小时帮助旅客解决在途中的各种问题，为了尽可能提升服务质量，公司希望客服人数可以满足所有旅客的来电，不用排队等待人工客服。现在提供客服中心所有的通话记录时间，你能算出最少需要多少名客服吗？
输入一个n表示要输入的通话记录个数，接下来输入n行，每行为逗号相隔的两个整数，两个数字分别代表呼入时间和挂断时间的时间戳。 举例：10,30，表示[10,30)，代表第10秒呼入，第30秒已经挂断，即第30秒可以接入新的来电； 每一行都是一条通话记录，通话记录已经按呼入时间由小到大排序；
输出
输出一个整数；代表最少需要多少客服，可以满足所有旅客来电不用等待。
样例输入
6 0,30 0,50 10,20 15,30 20,50 20,65样例输出
5
AC 0.8：
public class Main1 {
int N;
PriorityQueue<Integer> pq = new PriorityQueue<>();
int count = 0;
public static void main(String[] args) {
Main1 m = new Main1();
m.solution();
}
private void solution() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
if (N == 0) {
System.out.println(0);
return;
}
sc.nextLine();
for (int i = 0; i < N; i++) {
String[] strs = sc.nextLine().split(",");
int start = Integer.valueOf(strs[0]);
int end = Integer.valueOf(strs[1]);
select(start, end);
}
System.out.println(count);
}
private void select(int start, int end) {
if (count == 0) {
count++;
pq.add(end);
} else {
int minEnd = pq.peek();
if (start < minEnd) {
count++;
pq.add(end);
} else {
pq.poll();
pq.add(end);
}
}
}
} 第二题 携程海洋馆的海豚小宝宝
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
携程海洋馆中有 n 只萌萌的小海豚，初始均为 0 岁，每只小海豚的寿命是 m 岁，且这些小海豚会在 birthYear[i] 这些年份生产出一位宝宝海豚（1 <= birthYear[i] <= m），每位宝宝海豚刚出生为 0 岁。
携程海洋馆中有 n 只萌萌的小海豚，初始均为 0 岁，每只小海豚的寿命是 m 岁，且这些小海豚会在 birthYear[i] 这些年份生产出一位宝宝海豚（1 <= birthYear[i] <= m），每位宝宝海豚刚出生为 0 岁。
问 x 年时，携程海洋馆有多少只小海豚？
输入
n（初始海豚数）
m（海豚寿命）
海豚生宝宝的年份数量(假设为p)
海豚生宝宝的年份1
...
海豚生宝宝的年份p
x（几年后）
输出
x年后，共有多少只小海豚
样例输入
输入
n（初始海豚数）
m（海豚寿命）
海豚生宝宝的年份数量(假设为p)
海豚生宝宝的年份1
...
海豚生宝宝的年份p
x（几年后）
输出
x年后，共有多少只小海豚
样例输入
5 5 2 2 4 5样例输出
20AC 0.75：
public class Main2 {
int N, M, P, X;
int[] birth;
List<Node> res = new ArrayList<>();
public static void main(String[] args) {
Main2 m = new Main2();
m.solution();
}
private void solution() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
P = sc.nextInt();
birth = new int[P];
for (int i = 0; i < P; i++) {
birth[i] = sc.nextInt();
}
Arrays.sort(birth);
X = sc.nextInt();
for (int i = 0; i < N; i++) {
res.add(new Node(0));
}
int count = N;
for (int i = 1; i <= X; i++) {
List<Node> temp = new ArrayList<>();
for (Node node : res) {
if (!node.dead) {
node.age++;
if (node.age > M) {
node.dead = true;
count--;
} else if (binSearch(node.age)) {
temp.add(new Node(0));
count++;
}
}
}
if (!temp.isEmpty()) {
res.addAll(temp);
}
}
System.out.println(count);
}
private boolean binSearch(int age) {
int low = 0, high = birth.length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (birth[mid] == age) {
return true;
} else if (birth[mid] < age){
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}
private static class Node {
int age;
boolean dead = false;
Node(int age) {
this.age = age;
}
}
} 第三题 模拟ElasticSearch中的FuzzyQuery中的单词纠正
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
ElasticSearch 是常用的开源搜索引擎，支持fuzzyQuery 给搜索带来很大便利。其简单原理如下，surprize有拼写错误，把z换成s后得到 surprise，即纠正一个字母，就可以匹配正确的单词。
同样，把surprize的z替换成s，然后在末尾加个d，可以得到surprised。
给定字典[ "surprise", "happy", "ctrip", "travel", "wellcome","student","system","program","editor"]为正确单词。
编程实现单词纠正，判断输入的单词能否在2(包含)次纠正操作内得到字典中的单词。
纠正操作是以下三种，
1：替换字符串中的一个字母;
2：删除字符串中的一个字母;
3：在字符串中增加一个字母。
输入
待纠正的单词1
...
待纠正的单词n
输出
如果可以匹配,请返回字典中的单词,
如果无法匹配,请返回字符串null
样例输入
ElasticSearch 是常用的开源搜索引擎，支持fuzzyQuery 给搜索带来很大便利。其简单原理如下，surprize有拼写错误，把z换成s后得到 surprise，即纠正一个字母，就可以匹配正确的单词。
同样，把surprize的z替换成s，然后在末尾加个d，可以得到surprised。
给定字典[ "surprise", "happy", "ctrip", "travel", "wellcome","student","system","program","editor"]为正确单词。
编程实现单词纠正，判断输入的单词能否在2(包含)次纠正操作内得到字典中的单词。
纠正操作是以下三种，
1：替换字符串中的一个字母;
2：删除字符串中的一个字母;
3：在字符串中增加一个字母。
输入
待纠正的单词1
...
待纠正的单词n
输出
如果可以匹配,请返回字典中的单词,
如果无法匹配,请返回字符串null
样例输入
hipp样例输出
happy题目有毒，没说清楚输入到底是一行还是N行（如果是N行，N也没给出），AC 0.88：
public class Main3 {
String[] dict = new String[]{"surprise", "happy", "ctrip", "travel", "wellcome","student","system","program","editor"};
List<char[]> dictList = new ArrayList<>(dict.length);
public static void main(String[] args) {
Main3 m = new Main3();
m.solution();
}
private void solution() {
for (String s : dict) {
dictList.add(s.toCharArray());
}
Scanner sc = new Scanner(System.in);
String word = sc.nextLine();
transfer(word);
}
private void transfer(String word) {
int maxLcsIndex = -1, maxLcsLen = 0;
char[] cs = word.toCharArray();
for (int i = 0, len = dictList.size(); i < len; i++) {
if (Math.abs(cs.length - dictList.get(i).length) <= 2) {
int lcsLen = LCS(dictList.get(i), cs);
if (lcsLen > maxLcsLen) {
maxLcsLen = lcsLen;
maxLcsIndex = i;
}
}
}
if (maxLcsIndex == -1) {
System.out.println("null");
return;
}
char[] target = dictList.get(maxLcsIndex);
int m = cs.length, n = target.length;
int diff = Math.abs(m - n);
if (diff == 2) {
if (maxLcsLen != Math.min(m, n)) {
System.out.println("null");
} else {
System.out.println(dict[maxLcsIndex]);
}
} else if (diff == 1) {
maxLcsLen++;
if (maxLcsLen >= Math.max(m, n) - 1) {
System.out.println(dict[maxLcsIndex]);
} else {
System.out.println("null");
}
} else if (diff == 0) {
if (maxLcsLen >= m - 2) {
System.out.println(dict[maxLcsIndex]);
} else {
System.out.println("null");
}
}
}
private int LCS(char[] s, char[] t) {
int m = s.length, n = t.length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
} 
联想公司福利 1460人发布