2020春招-携程笔试-编程题3道

携程笔试编程题

Posted by weber on April 1, 2020

公司:携程

岗位:机器学习工程师(留用实习)

笔试:在线笔试(赛码网)

题型:20选择+3编程

编程题1 字符串子串数量

描述:

输入一个n,m, 接下来输入长度为n的字符串s,m个字符的集合,看s中最多可以匹配m集合以及其子集的字符串的个数(可重复)。

输入示例:

6 2

xyzxyz

x y

输出示例:

6

解释:

(x),(y),(xy),(x),(y),(xy)

思路:

遍历n,每次找到n中可以匹配m的最长子串c,然后根据c的长度计算个数,如果被截断(比如xyz遇到z)就重新统计c。

解答:

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int m = scan.nextInt();
    String str = scan.next();
    int[] map = new int[26];
    for (int i = 0; i < m; i++) {
        char c = scan.next().toCharArray()[0];
        map[c - 'a'] += 1;
    }
    scan.close();
    int[] baseMap = map.clone();
    int len = 0;
    int res = 0;
    for (int i = 0; i < n; i++) {
        int c = str.charAt(i) - 'a';
        if (map[c] > 0) {
            map[c] -= 1;
            len += 1;
        } else {
            map = baseMap;
            res += Math.pow(2.0, len) - 1;
            len = 0;
        }
    }
    System.out.println(res);
}

编程题2 电话客服的个数

题目类似 leetcode 253 会议室II

描述:

输入n,表示n个电话,每个电话是一个区间,比如 [10,30) 表示10秒接入,30秒挂断。输出最少需要几个接电话的客服,能应付这些电话。(已按照接入顺序排序)

输入示例:

3

0,10

5,20

15,30

输出示例:

2

思路:

贪心算法 + 堆排序(优先队列),可参考 253 会议室II

解答:

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int[][] call = new int[n][2];
    for (int i = 0; i < n; i++) {
        String[] str = scan.next().trim().split(",");
        call[i][0] = Integer.parseInt(str[0]);
        call[i][1] = Integer.parseInt(str[1]);
    }
    int res = calcMinStaff(call);
    System.out.println(res);
}

static int calcMinStaff(int[][] call) {
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
    queue.add(call[0][1]);
    for (int i = 1; i < call.length; i++) {
        int last = queue.peek(); // 最早结束的电话
        if (call[i][0] >= last) { //如果下一个电话比结束的电话晚,就给这个接线员
            queue.poll();
            queue.add(call[0][1]);
        } else {//最早结束的电话都赶不上这个电话,需要新的接线员
            queue.add(call[0][1]);
        }
    }
    return queue.size();
}

编程题3-海豚繁衍

繁衍类问题是一类题,考虑死亡/不考虑死亡,单次繁衍/多次繁衍

描述:

第0年有n只海豚,每只寿命为m,

输入k,表示数组birthYear的长度 (1<=birthYear[i]<=m),

输入k个birthYear的值,表示每只海豚在第birthYear[i]年生一只小海豚。

问第x年海豚的数量。

输入示例:

5

5

2

2

4

5

输出示例:

20

思路:

动态规划的题目,核心还是思考如何写出状态转移方程。相较于斐波那契的简单生殖方式,我们在做这种复杂的生殖条件时,可以建立一个记录新出生数量的数组,这样问题一下就迎刃而解。

解答:

static long countDolphin(int n, int m, int[] birthYear, int x) {

        int[] newBirth = new int[x + 1]; //用一个数组,记录新生海豚的数量
        for (int i = 0; i < birthYear.length; i++) {
            int step = birthYear[i];
            for (int j = step; j <= x; j += step) {
                newBirth[j] += 1;
            }
        }
        int[] dp = new int[x + 1];
        dp[0] = 1;
        for (int i = 1; i <= x; i++) {
            dp[i] = dp[i - 1] + newBirth[i]; //每个时刻的海豚数 = 上一时刻 + 该时刻新生 - 死亡
            if (i > m) dp[i] -= dp[i - m - 1];
        }
        return dp[x] * n;
    }

总结

这也是第一次线上笔试,一是有点紧张,二是最近做题少了,思路不够清晰,整体答的不是很好。

所以回过头来又认真做了一下,慢慢做其实都是自己会的。

三道题考察的知识点:

字符串,哈希表,贪心算法,堆排序(优先队列),动态规划。