美团Ai面试、笔试记录

Java资料网推荐美团Ai面试、笔试记录这篇文章给大家，欢迎收藏Java资料网享受知识的乐趣

美团Ai面试（每题有大约15s思考时间，答题时间限制5min）

选择使用语言java

1、如何查看和修改系统时间？

2、什么是函数式接口？这java8中新增了哪些函数式接口？

3、Java中默认方法default是什么？解决了什么问题？

4、在线教育平台设计作业提交系统如何处理截止日期和查重？

5、最近学习的某个新语言或新技术通过什么渠道学习的？遇到的难题？如何解决？

8.10技术笔试

题目源自链接，代码仅进行了自测输入，有任何问题评论区讨论。

Question 1

小美准备登录美团，需要输入密码，小美忘记了密码，只记得密码可能是n个字符串中的一个。小美会按照密码的长度从小到大依次尝试每个字符串，对于相同长度的字符串，小美随机尝试，并且相同的密码只会尝试一次。小美想知道，她最少需要尝试多少次才能登录成功，最多需要尝试多少次才能登录成功。

小美不会重新尝试已经尝试过的字符串。成功登录后会立即停止尝试。

第一行输入一个整数n (1 <n < 1000) 代表密码字符串的个数。
第二行输入一个只由小写字母组成的字符串s(1 <|s|< 1000) 代表正确的密码。接下来n行，每行输入一个长度不超过 1000 的字符串，代表小美记得的密码。

输出描述

在一行上输出两个整数，表示最少和最多尝试次数。

示例

输入：

4
ab
abc
ab
ac
ac

输出：

1 2

解答：

import java.util.*;

public class Q1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String correctPassword = sc.next();
        List<String> passwords = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            passwords.add(sc.next());
        }
        sc.close();
        long[] ans = getTryNum(n, correctPassword, passwords);
        System.out.println(ans[0] + " " + ans[1]);
    }

    public static long[] getTryNum(int n, String correctPassword, List<String> passwords) {
        long[] ans = new long[2];

        // 使用set去重
        Set<String> set = new HashSet<>();
        for (int i = 0; i < passwords.size(); i++) {
            set.add(passwords.get(i));
        }
        List<String> uniPsw = new ArrayList<>(set);

        // 建立长度map
        Map<Integer, Integer> lenMap = new HashMap<>();
        for (int i = 0; i < uniPsw.size(); i++) {
            lenMap.merge(uniPsw.get(i).length(), 1, Integer::sum);
        }

        long minAttempts = 1;
        int len = correctPassword.length();
        for (int i = 1; i < len; i++) {
            if (lenMap.containsKey(i)) {
                minAttempts += lenMap.get(i);
            }
        }

        long maxAttempts = 0;
        if (lenMap.containsKey(len)) {
            maxAttempts += minAttempts + lenMap.get(len) - 1;
        }
        ans[0] = minAttempts;
        ans[1] = maxAttempts;
        return ans;
    }
}

Question 2

小美有一个长度为 n 的数组 a1,a2,…,an ，他可以对数组进行如下操作:

• 删除第一个元素 a1，同时数组的长度减一，花费为x。
• 删除整个数组，花费为 k x MEX(a)(其中 MEX(a)表示a中未出现过的最小非负整数。例如[0,1,2,4]的 MEX为3)

小美想知道将a数组全部清空的最小代价是多少，请你帮帮他吧

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1 ≤ T < 1000)代表数据组数，每组测试数据描述如下:
第一行输入三个正整数n,k,x(1≤n≤2x10e5,1 ≤k,x ≤ 10e9)代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。
第二行输入n个整数 a1,a2,·..,an(0 ≤ a¡< n)，表示数组元素。
除此之外，保证所有的n 之和不超过 2x10e5。

输出描述

对于每一组测试数据，在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。

示例
输入:

1
6 3 3
4 5 2 3 1 0

输出：

15

说明：

若不执行操作一就全部删除，MEX{4,5,2,3,1,0} = 6，花费18;
若执行一次操作一后全部删除，MEX{5,2,3,1,0}= 4，花费3+12;
若执行两次操作一后全部删除，MEX{2,3,1,0}= 4,花费6+12;
若执行三次操作一后全部删除，MEX{3,1,0}= 2，花费9+6;
若执行四次操作一后全部删除，MEX{1,0}=2，花12+6;
若执行五次操作一后全部删除，MEX{0}=1，花费15+3;
若执行六次操作一，MEX{}=0，花费 18;

解答：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Q2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        long[] allAns = new long[num];

        for (int i = 0; i < num; i++) {
            int n = sc.nextInt();
            long k = sc.nextInt();
            long x = sc.nextInt();
            List<Integer> array = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                array.add(sc.nextInt());
            }
            if (i == num - 1) {
                sc.close();
            }
            long ans = minCost(n, k, x, array);
            allAns[i] = ans;
        }
        sc.close();
        for (int i = 0; i < num; i++) {
            System.out.println(allAns[i]);
        }
    }
    public static long minCost(int n, long k, long x, List<Integer> array) {
        // 求最小值
        long ans = Long.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            int noDigital = MEX(array);
            long tmp = noDigital * k + i * x;
            ans = Math.min(ans, tmp);
            if (array.size() != 0) {
                array.remove(0);
            }
        }
        return ans;
    }

    public static int MEX(List<Integer> array) {
        int n = array.size() + 1;
        if (n == 1) {
            return 0;
        }
        int[] cnt = new int[n];
        for (int i = 0; i < array.size(); i++) {
            cnt[array.get(i)]++;
        }
        int noDigital = -1;
        for (int i = 0; i < n; i++) {
            if (cnt[i] == 0) {
                noDigital = i;
            }
        }
        return noDigital;
    }
}

Question 3

小美的彩带是由一条长度为n 的彩带一直无限循环得到的，彩带的每一个位置都有一个颜色，用ai表示。因此当i>n时，ai = a(i-n)。
小美每次会从左往后或从右往左剪一段长度为x的彩带，她想知道她每次剪下来的彩带有多少种颜色。

输入描述

第一行输入两个整数 n,q(1< n,q≤ 2 x 10e5)代表彩带长度、剪彩带次数。

第二行输入n个整数 a1,a2,...,an(1≤ai≤ 10e9)代表彩带每一个位置的颇色。

此后q 行，每行输入一个字符c 和一个整数x(1 ≤ x ≤ 10e9; c属于'L','R')代表裁剪方向和裁剪长度，其中'L'说明从左往右剪，"'说明从右往左剪。

输出描述

对于每一次裁彩带，在一行上输出一个整数代表颜色数量，

示例

输入：

6 3
1 1 4 5 1 4
L 2
L 3
R 12

输出：

1
3
3

说明：

第一次剪彩带，剪下来的是[1,1]，有{1}这1种颜色；
第二次剪彩带，剪下来的是 [4,5,1]，有 {1,4,5}这3种颜色;
第三次剪彩带，剪下来的是[1,1,4,5,1,4,1,1,4,5,1,4]，有{1,4,5}这3种颜色。

解答：

import java.util.*;

public class Q3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] array = new int[n];

        // 读取彩带的颜色
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        int orgin = -1;
        int[] ans = new int[q];
        // 处理每个裁剪请求
        for (int i = 0; i < q; i++) {
            String lOrR = sc.next();
            char direction = lOrR.charAt(0);
            int x = sc.nextInt();
            int[] cnt = colorNum(n, array, direction, x, orgin);
            orgin = cnt[1];
            ans[i] = cnt[0];
        }
        sc.close();

        for (int i = 0; i < q; i++) {
            System.out.println(ans[i]);
        }
    }

    public static int[] colorNum(int n, int[] array, char direction, int x, int currentPosition) {
        int[] ans = new int[2];
        Map<Integer, Integer> map = new HashMap<>();

        if (direction == 'L') {
            // 从当前位置开始裁剪
            for (int j = 0; j < x; j++) {
                map.merge(array[(currentPosition + j + 1) % n], 1, Integer::sum);
            }
            // 更新当前位置
            currentPosition = (currentPosition + x) % n;
        } else if (direction == 'R') {
            // 从当前位置开始裁剪
            for (int j = 0; j < x; j++) {
                map.merge(array[(currentPosition + 1 - j + n) % n], 1, Integer::sum);
            }
            // 更新当前位置
            currentPosition = (currentPosition - x + n + 1) % n;
        }
        ans[0] = map.size();
        ans[1] = currentPosition;
        return ans;
    }
}

文章来源:https://blog.csdn.net/TIANLEeeee/article/details/141102394
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！