18年春招今日头条笔试题

两个小时5道编程题，非常变态，而且题目还不好理解，AC2道，昨天得知AC两道笔试竟然没过，好吧，头条的算法门槛还是比较高的，最想去的公司了，看来我还需要好好总结方法了，而且下次头条笔试一定要一个人做，在一个安静的环境下…

1. 在n个元素的数组中，找到差值为k的数字对去重后的个数
2. 定义两个字符变量：s和m，再定义两种操作，
   第一种操作：
   m=s；
   s=s+s;
   第二种操作：
   s=s+m;
   假设初始化如下：
   s=”a”; m=s;
   求最小的操作步骤数，可以将s拼接到长度等于n；
3. 略(类似于点阵显示的问题，虽然简单，但是做起来很费劲)
4. 给定一个包含n个整数元素的集合a，一个包含m个整数元素的集合b
   定义magic操作为，从一个集合中取出一个元素，放到另一个集合中，且操作过后每个集合的平均值都大于操作前
   注意一下两点：
   1.不可以把一个集合的元素取空，这样就没有平均值了
   2.值为x的元素从集合b取出放到集合a，但集合a中已经有值为x的元素，则a的平均值不变（因为集合元素不会重复），b的平均值可能会改变（因为x被取出了）
   问最多可以进行多少次magic操作？
5. 小T最近迷上一款跳板小游戏
   已知空中有N个高度互不相同的跳板，小T刚开始在高度为0的地方，每次跳跃可以选择与自己当前高度绝对值差小于等于H的跳板，跳跃过后到达以跳板为轴的镜像位置，问小T在最多跳K次的情况下最高能跳多高？(高度不能为负)

数字对去重后的个数

这道题直接用两个for循环查找的话是会超时的，所以我一开始就没这么做，而是使用一个Map来，每次去重都删除后面的元素

public class TouTiao01 {

    /*
    使用map来存储数组中的值出现的个数
    比较当前元素加上k后的值是否在map中，如果在，就让改值对应的value减1
    k=0需要特殊考虑
     */
    public static int getTheNumber(int[]arr,int k){
        int res=0;
        if(k==0){
            for(int i=0;i<arr.length-1;i+=2){
                if(arr[i]==arr[i+1])res++;
            }
            return arr.length-res;
        }
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<arr.length;i++){
            if(map.containsKey(arr[i]))map.replace(arr[i],map.get(arr[i])+1);
            else map.put(arr[i],1);
        }
        for(int i=0;i<arr.length;i++){
            if(map.get(arr[i])>0&&map.containsKey(arr[i]+k)&&map.get(arr[i]+k)>0){
                map.replace(arr[i]+k,map.get(arr[i])-1);
            }
        }
        for(Integer key:map.keySet()){
            res+=map.get(key);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n,k;
        n=scanner.nextInt();
        k=scanner.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=scanner.nextInt();
        }
        scanner.close();
        Arrays.sort(arr);
        System.out.println(getTheNumber(arr,k));
    }
}

最小的操作步骤数

开始在找规律，发现出现很多问题，于是干脆用DFS来做，每一次操作都有两个选择，遍历这些选择，我以为会超时，结果通过了，实际上这是一道BFS的题，每次让所有路径都往前走一步，判断有没有到达终点的，没有继续，有则返回步数。
应该也可以使用DP来解决的，毕竟有重复的过程

public class TouTiao02 {
    static int minStep=Integer.MAX_VALUE;//记录需要变换的最小次数
    /*
    这里由于第一次变换比第二次变换使得字符串增长的更快，所以先走第一次变换，
    如果无法达到，则回退
    如果达到，就和最小的步数比较
     */
    public static void dfs(String s,String m,int step,int n){
        if(s.length()>=n){
            if(s.length()==n)minStep=step<minStep?step:minStep;
        }
        else {
                dfs(s+s,s,step+1,n);
                dfs(s+m,m,step+1,n);
        }
    }

    public static int getMinStep(int n){
        dfs("mm","m",1,n);
        return minStep;
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n;
        n=scanner.nextInt();
        scanner.close();
        System.out.println(getMinStep(n));
    }
}

magic操作

这道题其实挺简单的，就是没有时间看了
每次交换的时候只需要知道b中取的元素应该是小于b数组的均值，且大于a数组的均值，而且不能在a数组中包含该元素

public class TouTiao04 {
    /*
    dfs
    b中取的元素应该是小于b数组的均值，且大于a数组的均值，而且不能在a数组中包含该元素
     */
    static int maxMagic=0;
    public static void getMaxMagic(ArrayList<Integer>a,ArrayList<Integer>b,float avea,float aveb,int magicStep){
        if(magicStep>maxMagic)maxMagic=magicStep;
        Collections.sort(a);
        Collections.sort(b);
        int i=b.size()-1;
        while (i>=0&&(float)b.get(i)>aveb)i--;
        while (i>=0&&(float)b.get(i)>avea){
            if(a.contains(b.get(i))){
                i--;
                continue;
            }
            int num=b.get(i);
            a.add(num);
            b.remove(i);
            getMaxMagic(a,b,(avea*(a.size()-1)+num)/a.size(),(aveb*(b.size()+1)-num)/b.size(),magicStep+1);
            b.add(i,num);
            a.remove(new Integer(num));//这里是删除num值，而不是最后一个元素，因为a被打乱了
            i--;
        }

    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n,m;
        n=scanner.nextInt();
        m=scanner.nextInt();
        ArrayList<Integer> a=new ArrayList<>();
        ArrayList<Integer> b=new ArrayList<>();
        float avea=0,aveb=0;
        for(int i=0;i<n;i++){
            int num=scanner.nextInt();
            a.add(num);
            avea+=num;
        }
        for(int i=0;i<m;i++){
            int num=scanner.nextInt();
            b.add(num);
            aveb+=num;
        }
        scanner.close();
        getMaxMagic(a,b,avea/n,aveb/m,0);
        System.out.println(maxMagic);
    }
}

跳板小游戏

感觉这道题题目有点表述不清，按理说应该画一张图的
同样使用DFS，发现头条非常喜欢出DFS，BFS，DP的题
每一次跳跃都有若干的选择，但是你不知道哪一个选择是最优路径，那就遍历这所有的情况了，没啥好解释的了。

/*
这里的镜像的意思是以跳后的位置为轴，跳前到跳后的距离再翻转一次
*/
public class TouTiao05 {
    static int maxHeight=0;
    public static void getMaxHeight(int[]a,int curHeight,int k,int h){
        if(maxHeight<curHeight)maxHeight=curHeight;
        if(k==0)return;
        for(int i=0;i<a.length;i++){
            if(Math.abs(curHeight-a[i])<=h){
                int value=a[i]-curHeight;
                getMaxHeight(a,curHeight+2*value>0?curHeight+2*value:0,k-1,h);
            }
        }
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n,k,h;
        n=scanner.nextInt();
        k=scanner.nextInt();
        h=scanner.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=scanner.nextInt();
        }
        scanner.close();
        Arrays.sort(a);
        getMaxHeight(a,0,k,h);
        System.out.println(maxHeight);
    }
}