2020携程4.1后端笔试编程题 2.43

第一题求最小客服人数

时间限制：C/C++语言 1000MS；其他语言 3000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

携程呼叫中心7×24小时帮助旅客解决在途中的各种问题，为了尽可能提升服务质量，公司希望客服人数可以满足所有旅客的来电，不用排队等待人工客服。现在提供客服中心所有的通话记录时间，你能算出最少需要多少名客服吗？

输入
输入一个n表示要输入的通话记录个数，接下来输入n行，每行为逗号相隔的两个整数，两个数字分别代表呼入时间和挂断时间的时间戳。举例：10,30，表示[10,30)，代表第10秒呼入，第30秒已经挂断，即第30秒可以接入新的来电；每一行都是一条通话记录，通话记录已经按呼入时间由小到大排序；

输出
输出一个整数；代表最少需要多少客服，可以满足所有旅客来电不用等待。

样例输入

样例输出

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 岁。

问 x 年时，携程海洋馆有多少只小海豚？

输入
n（初始海豚数）
m（海豚寿命）
海豚生宝宝的年份数量(假设为p)
海豚生宝宝的年份1
...
海豚生宝宝的年份p
x（几年后）

输出
x年后，共有多少只小海豚

样例输入

样例输出

AC 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

题目描述：
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];
    }
}

#2020携程41后端笔试编程题##携程#