美团java后端实习 在线笔试 4.16
emmm，五个编程题，就做出四题，最后题盲猜是dp，不过没时间做了。
以下是前四个题的代码：
1、第一题要考虑两个情况：一个是每个人只能算一次，还有种是并列第一的情况
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int N = cin.nextInt();
int M = cin.nextInt();
int[][] score = new int[N][M];
int[] maxScore = new int[M];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
score[i][j] = cin.nextInt();
maxScore[j] = score[i][j]>maxScore[j]?score[i][j]:maxScore[j];
}
}
Set<Integer> set = new HashSet<>();
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(score[j][i]==maxScore[i])
set.add(j);
}
}
System.out.println(set.size());
}
}
2、就是把题目给的循环实现了下，遇到一个已经出现过的x就结束循环，对循环次数进行计数，然后把类型改成了long，防止爆int，然后就能过了
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int a,b,m,x;
a = cin.nextInt();
b = cin.nextInt();
m = cin.nextInt();
x = cin.nextInt();
boolean[] flag = new boolean[m];
int ans = 0;
while(true){
x = (int)(((long)a*(long)x+(long)b)%(long)m);
if(flag[x]==true)
break;
ans++;
flag[x]=true;
}
System.out.println(ans);
}
}
3、第三题看代码应该能看懂，我给测试样例吧，比如：
3 3
3 3 4
这个结果应该是(3,3)而不是(3,4)
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int N = cin.nextInt();
long K = cin.nextLong();
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<N;i++){
int tmp = cin.nextInt();
Integer temp = map.get(tmp);
if(temp == null){
map.put(tmp,1);
}else{
map.put(tmp,temp+1);
}
}
int[] num = new int[map.size()];
int numLength = 0;
for(int tmp:map.keySet()){
num[numLength++] = tmp;
}
Arrays.sort(num);
System.out.print("(");
long totalCnt = 0;
for(int i=0;i<numLength;i++){
long cnt = (long)map.get(num[i]);
if(totalCnt+cnt*N>=K){
System.out.print(num[i]+",");
for(int j=0;j<numLength;j++){
long _cnt = (long)map.get(num[j]);
if(totalCnt + _cnt*cnt >= K){
System.out.print(num[j]+")");
break;
}
totalCnt+=_cnt*cnt;
}
break;
}
totalCnt+=cnt*N;
}
}
}
4、第四题首先对数组排序，然后在数组中查找是否有K，若没有，先使用一次插入操作，把K插在该插的位置，然后因为数组中可能有多个K，则记录最左K的下标minI，和最右K下标maxI，然后就进行插入操作，从插入0次开始，分别计算插在最左边和插在最右边的时候，minI~maxI是否包含伪中位数的下标。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int N = cin.nextInt();
long K = cin.nextLong();
int[] num = new int[N];
for(int i=0;i<N;i++){
num[i] = cin.nextInt();
}
Arrays.sort(num);
int maxI,minI;
for(maxI=N-1;maxI>=0;maxI--){
if(num[maxI]==K)
break;
}
for(minI=0;minI<N;minI++){
if(num[minI]==K)
break;
}
int ans=0;
if(maxI<0){
int i;
for(i=0;i<N;i++){
if(num[i]>K)
break;
}
maxI=i;
minI=i;
ans++;
N++;
}
for(int j=0;;j++){
if(maxI+1+j >= (N+j+1)/2 && minI+1+j <= (N+j+1)/2 || maxI+1 >= (N+j+1)/2 && minI+1 <= (N+j+1)/2){
System.out.println(ans+j);
break;
}
}
}
}
