美团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.字符串遍历间隔数**
题目描述：
给你一个小写字母的全排列，然后按照排列顺序组成一个长度不限的字符序列，给你一个目标字符串，让你按照对应顺序取出，然后想问你最少需要浪费多少字符。目标字符串的长度为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.值日表
没明白啥意思。
#美团##笔试题目#
