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]; } }