美团Ai面试、笔试记录

Tian_xiaohua912 2024-09-19 10:35:03 阅读 75

美团Ai面试(每题有大约15s思考时间,答题时间限制5min)

选择使用语言java

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

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

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

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

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

8.10技术笔试

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

Question 1

小美准备登录美团,需要输入密码,小美忘记了密码,只记得密码可能是<code>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;

}

}



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。