# 美团 8.8 后台笔试

## 说明

0.91 1.00 0.64 1.00 1.00，这次相对来说比较简单，应该会有面试吧~

## 1. 数组中恰好有k个数严格小于它

### 题目描述

• 数组中恰好有k个数严格小于它。
• 1<=x<=n

### 解析

```import java.util.Arrays;
import java.util.Scanner;

public class Main1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while (t>0){
int n = scanner.nextInt();
int k = scanner.nextInt();
int[] a = new int[n];
for(int i=0;i<n;i++)
a[i] = scanner.nextInt();
Arrays.sort(a);
if(k==n){
if((a[n-1]+1)<=n&&(a[n-1]+1)>=1){
System.out.println("YES");
System.out.println(a[n-1]);
}else
System.out.println("NO");
}else if(k>n){
System.out.println("NO");
}else{
int c1 = a[k-1];
int c2 = a[k];
if(c1==c2)
System.out.println("NO");
else{
if(c1+1<=n&&c1+1>=1){
System.out.println("YES");
System.out.println(c1+1);
}else
System.out.println("NO");
}
}
t--;
}
}
}```

## 2. 键盘滞留

### 解析

```import java.util.Scanner;

public class Main2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
s = s.replace(" ","");
if(s.equals("")) {
System.out.println();
return;
}
char c = s.charAt(0);
String ss = c+"";
for(int i=1;i<s.length();i++){
if(s.charAt(i)!=c){
ss += s.charAt(i);
c = s.charAt(i);
}
}
System.out.println(ss);
}
}```

## 3. 求数组中序号和值都比它小的最大数

### 解析

```import java.util.*;

public class Main3 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
int[] pre = new int[n];

for(int i=0;i<n;i++)
a[i] = scanner.nextInt();
Queue<Integer> q = new PriorityQueue((o1, o2) -> (int)o2-(int)o1);
for(int i=1;i<n;i++){
List<Integer> list = new ArrayList<>();
while(q.size()>0){
int e = q.poll();
if(e<a[i]){
pre[i] = e;
break;
}
}
}
long res = 0;
for(int i=0;i<n;i++)
res += pre[i]*(i+1);
System.out.println(res);
}
}```

## 完美数组

### 解析

```import java.util.Scanner;

public class Main4 {
static int[] f = new int[10001];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for(int i=0;i<n;i++)
a[i] = scanner.nextInt();
int res = 0;
for(int i=0;i<f.length;i++)
f[i] = i;
for(int i=0;i<n/2;i++){
if(find(a[i])!=find(a[i+n/2])){
union(a[i],a[i+n/2]);
res++;
}
}
System.out.println(res);
}
public static int find(int x){
while(x!=f[x]){
x = f[x];
}
return x;
}
public static void union(int x,int y){
int a = find(x);
int b = find(y);
if(a==b)
return;
else
f[a] = b;
}
}```

## 5. 中序遍历一棵翻转过的二叉树

### 解析

```import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main5 {

static List<Integer> list;
static int[] lc;
static int[] rc;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
list = new ArrayList<>();
lc = new int[n+1];
rc = new int[n+1];
for(int i=1;i<=n;i++){
lc[i] = scanner.nextInt();
rc[i] = scanner.nextInt();
}
for(int i=0;i<m;i++){
int temp = scanner.nextInt();
int t = lc[temp];
lc[temp] = rc[temp];
rc[temp] = t;
}
dfs(k);
for(int i=0;i<list.size()-1;i++)
System.out.print(list.get(i)+" ");
System.out.println(list.get(list.size()-1));
}
public static void dfs(int i){
if(i==0)
return;
int l = lc[i];
int r = rc[i];
dfs(l);