首页 > 美团20210321部分题目及解析
头像
保持热忱天天向上
编辑于 2021-03-22 20:32
+ 关注

美团20210321部分题目及解析

由于本人没有参加笔试,只是看了下题目再加上本人水平太菜,所以所用到的方法也未必能ac,可能会有什么边界条件没考虑到,欢迎各位批评指正。
**1.字符串遍历间隔数**
题目描述:
给你一个小写字母的全排列,然后按照排列顺序组成一个长度不限的字符序列,给你一个目标字符串,让你按照对应顺序取出,然后想问你最少需要浪费多少字符。目标字符串的长度为10^5以内

> 直接把字符串转为字符串数组,然后用模式串去匹配原字符串,暴力求解。

```java
package newCoder.meituan;

import java.util.Scanner;

public class alpha_traverse {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();//匹配串
String str2 = sc.next();//模式串
char[]str1ToChar1 = str1.toCharArray();
char[]str2ToChar2 = str2.toCharArray();
int len1 = str1ToChar1.length;
int len2 = str2ToChar2.length;
int res = 0,i = 0;
while(true){
for(int j = 0;j < len1;j++){
if(str1ToChar1[j]!=str2ToChar2[i]){//没有匹配到
res++;
}else{//匹配到
if(i < len2 - 1){
i++;
}else{
break;
}
}
}
if(i == len2 - 1){
break;
}
}
System.out.println(res);

}
}

```

**2.集合**
题目描述:
给你两个集合A和B,你可以选择让集合A中的所有元素均加x,然后对m取余,使得A集合和B集合相等,问你最少的x是多少

> 没想到什么好的数学解法,直接暴力求解。这其实是个映射问题,可以考虑用ArrayList存储A的每一个元素,然后用HashSet存储B的每一个元素。用HashSet的contains方法来判断A中的每一个元素+x然后取模是否在B中即可。

```java
package newCoder.meituan;

import java.util.*;
public class muti_set {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();
int M1 = M;
int M2 = M;
List<Integer> list  = new ArrayList<>();
Set<Integer> set = new HashSet<>();
while(M-- > 0){
list.add(sc.nextInt());
}
while(M1-- > 0){
set.add(sc.nextInt());
}
int res = 1;
for(int data:list){
int nums = 1;
while(set.contains((data + res)% M2 )&& nums < N){
nums++;
if(nums == N){
break;
}
}
res++;
}
System.out.println(res);
}
}

```

**3.奶茶**
题目描述:
有n杯奶茶,m个人,每一个每分钟可以和c单位,现在每一个人只能选择一段连续编号的奶茶,问你所有奶茶喝完所需要的的最短时间是多少,喝完奶茶时间为这m个人中,喝完每个人的奶茶最短最长时间,注意:一杯奶茶时间可以为小数,最终答案向上取整。

> 解析:根据常识,m个人都参与喝奶茶,这样才会喝奶茶用时最短,除非n<m。可以把题目抽象成m段连续的子数组和最小问题。求解连续子数组和最小问题,可以考虑动态规划的方法来做,但是状态转移方程不太好想。可以考虑二分查找+贪心的方法来解决。步骤如下:
> 1.连续的子数组和一定大于数组中的最大值,小于数组中所有元素相加。
> 2.从前往后遍历,用sum来表示当前分割子数组的和,cnt表示已经分割出的子数组的数量(包括当前子数组)。对于选定的值x,每当sum + arr[i]大于x,就把当前值作为新的一段分割的子数组,cnt++。
> 3.求解出连续子数组和的最小值,求出所需时间。

```java
package newCoder.meituan;

import java.util.Scanner;

public class naicha {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int []arr = new int[0];
int M = 0;
int C = 0;
int N = sc.nextInt();//n杯奶茶
M = sc.nextInt();//m个人
C = sc.nextInt();//喝奶茶的速度:ml/s
arr = new int[N];//存储输入的n杯奶茶的容量
for(int i = 0;i < N;i++){
arr[i] = sc.nextInt();
}
int min = subArraySumMin(arr,M);
if(min / C == 0){
System.out.println(min / C);
}else{
System.out.println(min / C + 1);
}
}
public static int subArraySumMin(int[]arr,int M){
int l = 0,r = 0;
for(int i = 0;i < arr.length;i++){
r += arr[i];
if(l < arr[i])
l = arr[i];
}
while(l < r){
int mid = l + (r - l) / 2;
if(check(arr,mid,M)){
r = mid;
}else{
l = mid + 1;
}

}
return l;
}
public static boolean check(int[]arr,int x,int m){
int sum = 0,cnt = 1;
for(int i = 0; i < arr.length;i++){
if(sum + arr[i] > x){
cnt++;
sum = arr[i];
}else{
sum += arr[i];
}
}
return cnt <= m;
}
}

```

4.值日表
没明白啥意思。

全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐