美团 8.8 后台笔试
说明
后台是4+1道题（听说同时的算法只有前4道），共2个小时，题目描述纯属回忆。
0.91 1.00 0.64 1.00 1.00，这次相对来说比较简单，应该会有面试吧~
1. 数组中恰好有k个数严格小于它
题目描述
输入一个数组，找一个最小的整数x，满足：
- 数组中恰好有k个数严格小于它。
- 1<=x<=n
如果能找到，先输出一行“YES”，再输出它；如果找不到，则输出“NO”。注：0<=k<=n<=10000
输入
第一行一个t，表示有t组数据。
接下来每组数据：输入n和k，n是数组的长度。
接下来是输入长度为n的数组。
输出
如果能找到，先输出一行“YES”，再输出它；如果找不到，则输出“NO”。
解析
对数组排序，如果k=n，则只需要比较数组末端元素是否满足在[1,n]之间，满足则直接输出a[n-1]+1，不满足输出NO。
如果k<n,那么a[0]~a[k-1]应该是有k个数，要严格大于a[k-1],即取a[k-1]+1，但要考虑a[k]是否等于a[k-1]，如果等于，则会有至少k+1个数严格小于它，最后再判断下元素是否满足在[1,n]之间。
以下代码过了91%，问题在于没考虑n和k都等于0的情况，这种情况直接取1。
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. 键盘滞留
题目描述
有一把问题键盘，不仅会任意时刻打出空格，还会重复重复某次键入，题目保证输入的原字符串没有连续两个字符相等的情况，求原字符串。
输入
有问题的字符串
输出
原字符串
解析
送分题，a了。
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. 求数组中序号和值都比它小的最大数
题目描述
输入一个数组a，求pre[i]，pre[i]的定义为max(a[j]),其中0<=j<i,数组中序号和值都比它小的最大数。
对于i取 0到n-1，求pre[i]*(i+1)的和。（原题描述是1~n，这里转化了下，所以是i+1，别见怪）
最后求
输入
第一行n，表示数组的长度
第二行，长度为n的数组
输出
对于i取0~n-1，求pre[i]*(i+1)的和。
解析
不会，只能暴力的用堆排，过了64%。请参考其他大佬。
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);
q.add(a[0]);
for(int i=1;i<n;i++){
List<Integer> list = new ArrayList<>();
while(q.size()>0){
int e = q.poll();
list.add(e);
if(e<a[i]){
pre[i] = e;
break;
}
}
list.add(a[i]);
q.addAll(list);
}
long res = 0;
for(int i=0;i<n;i++)
res += pre[i]*(i+1);
System.out.println(res);
}
}完美数组
题目描述
小美有一个数组，小团想把它转化为一个完美数组。求至少需要多少次操作？
完美数组指的是数组的前半段和后半段完全相同，如1，2，3，1，2，3。
一次操作指的是将数组中值为x的元素全部换为y。
输入
第一行一个n，表示数组的大小
第二行为长度为n的数组
输出
最少操作次数
解析
如果能看出来是并查集就很好做了，对于每次操作，相当于是把x和y并为了一类。
从i取0~n/2，若a[i]与a[i+n/2]属于一个集合,则不需要转换。若不相等，则需要转换，把a[i]和a[i+n/2]并为一个集合。最后输出转换的次数即可。a了。
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. 中序遍历一棵翻转过的二叉树
题目表述
一棵拥有n个节点的二叉树用数组表示，表示方法见输入。经过m次翻转操作，求翻转后的二叉树的中序遍历结果。其中k表示根节点的序号。
输入
第一行输入n/m/k
接下来n行，第i行都有两个数，分别表示i号节点的左子节点和右子节点下标。没有子节点用0表示。
接下来m行，第i行都有一个数，表示翻转i行的左右节点
输出
翻转后的二叉树的中序遍历。
解析
按照题目模拟一下就是了，用lc表示i号节点的左子节点下标，用rc表示i号节点的右子节点下标，翻转不过是交换lc与rc。最后dfs中序遍历即可。
可能难点在于大多数人习惯了TreeNode的二叉树表示方法，而这里是基于数组实现的。a了。
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);
list.add(i);
dfs(r);
}
}#美团笔试##美团##笔经#