说明

后台是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);
    }
}