美团 3.19笔试 复盘
美团 3.19笔试，有点菜，感觉没有面试机会了:(，第一题AC，第二题应该是条件出错误，第三题思路出错，应该同区间列表，第四题读错题，导致走了弯路，这里试着重写解答：（不确定能否AC）
第一题：点外卖 AC
选购商品，判断是折扣价总和便宜还是满减便宜
用个循环做判断，求个满减和与折扣和做比较即可
第二题：文件加密解密
输入数据：
string n
字符串输入，n=1，加密，n=2，解密
测试用例： 6 2 hahaha 预期结果:hhhaaa 6 1 hhhaaa 预期结果:hahaha
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int t=sc.nextInt();
sc.nextLine();
String strings=sc.nextLine();
StringBuilder ans=new StringBuilder();
if(t==1){
//加密
boolean[] visited=new boolean[n];
for(int i=0;i<n;i++) {
int index=0;
int site=(n-i+1)/2;
while(site>0){
if(!visited[index]){
site--;
}
if(site==0){
break;
}
index++;
}
ans.append(strings.charAt(index));
visited[index]=true;
}
}else if(t==2){
//解密
char[] arr=new char[n];
boolean[] visited=new boolean[n];
for(int i=0;i<n;i++){
int index=0;
int site=(1+n-i)/2;
while(site>0){
if(!visited[index]){
site--;
}
if(site==0){
break;
}
index++;
}
arr[index]=strings.charAt(i);
visited[index]=true;
}
ans.append(String.valueOf(arr));
}
System.out.println(ans.toString());
}
} 第三题：做题时思路出错，没有想到二维数组直接保存区间
修改文件，两次修改范围，求冲突文件数（找交集）
输入演示：
n文件总数
m1第一次修改次数
m2第二次修改次数
n m1 m2
m1个起始点
m1个结束点
m2个起始点
m2个结束点
测试数据：
10 2 3
3 5
4 8
1 4 9
3 6 10
预期结果：4
import java.util.*;
public class Main {
public static void main(String[] args) {
//准备数据
Scanner sc = new Scanner(System.in);
//文件总数
int n = sc.nextInt();
//游戏本修改次数
int m1 = sc.nextInt();
//老爷机修改次数
int m2 = sc.nextInt();
int[][] first=new int[m1][2];
int[][] second=new int[m2][2];
for(int i=0;i<m1;i++){
first[i][0]=sc.nextInt();
}
for(int i=0;i<m1;i++){
first[i][1]=sc.nextInt();
}
for(int i=0;i<m2;i++){
second[i][0]=sc.nextInt();
}
for(int i=0;i<m2;i++){
second[i][1]=sc.nextInt();
}
//按照起始时间排序
Arrays.sort(first, (o1, o2) -> o1[0]-o2[0]);
Arrays.sort(second, (o1, o2) -> o1[0]-o2[0]);
first=merge(first);
second=merge(second);
compare(first,second);
}
//解决自身区间相交，合并区间
private static int[][] merge(int[][] arr){
int index=-1;
int[][] res=new int[arr.length][2];
for(int[] iterator:arr){
if(index==-1||res[index][1]<iterator[0]){
res[++index]=iterator;
}else{
res[index][1]=Math.max(iterator[1],res[index][1]);
}
}
return Arrays.copyOf(res,index+1);
}
//求解区间交集
private static void compare(int[][] first,int[][] second){
int ans=0;
int m=first.length;
int n=second.length;
int i=0,j=0;
while(i<m&&j<n){
int[] temp=new int[2];
int a=first[i][0];
int b=first[i][1];
int x=second[j][0];
int y=second[j][1];
temp[0]=Math.max(a,x);
temp[1]=Math.min(b,y);
if(temp[1]>=temp[0]){
ans+=temp[1]-temp[0]+1;
}
if(y>b){
i++;
}else{
j++;
}
}
System.out.println(ans);
}
} 第四题，
输入值：
n k1 k2
n个数
要求为求在这n个数中选出最大的能整除k1，不能整除k2的和，以及它的总数；结果要
%998244353测试用例：
5 3 4
6 8 -2 -5 2
预期结果：
9 2
public class Main {
static int arr[];
static int max=0;
static Map<Integer,Integer> map=new HashMap<>();
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k1=sc.nextInt();
int k2=sc.nextInt();
arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
trackBack(k1,k2,0,0);
System.out.println(max+" "+map.get(max));
}
private static void trackBack(int k1,int k2,int sum,int index){
sum=sum%998244353;
if(sum%k1==0&&sum%k2!=0){
if(sum>=max){
max=sum;
if(map.containsKey(max)){
map.put(max,(map.get(max)+1)%998244353);
}else{
map.put(max,1);
}
}
}
for(int i=index;i<arr.length;i++){
sum+=arr[i];
trackBack(k1,k2,sum,i+1);
sum-=arr[i];
}
}
}