8月8日网易校招笔试题

前言

一共四道编程题，没有那么多花里胡哨的东西，做就完事儿了。

第一题

给定一个数组，求出这个数组中每个数字能够拆分出的最多的素数，返回和即可。

[3,5,7] ，因为3能分成3，5能分成2和3，7能分成2，2和3，所以答案是6

emmm 一开始我居然想的是判断一个数是不是素数，然后进行拆分…所以花了点时间去走远路。

其实题目非常简单，由于2和3都是素数，所以只要用2和3去组成这个素数就可以了….

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long result = 0;
        for (int i = 0; i < n; i++) {
            result += sc.nextInt()/2;
        }
        sc.close();
        System.out.println(result);
    }
}

唯一需要注意的点就是：最后的结果可能会溢出int的范围，请使用long来保存。如果用int是通过30%，如果是long通过100%，其它就没什么难度了。

第二题

给定一个数组，求出一个最小的字典排序。

n=5 array = [2,1,5] 答案是[2,1,3,4,5]

emm 那这题就是把数字插到它应该在的位置不就好了么….没看出有什么陷阱：

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        List<Integer> remain = new ArrayList<>();
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = i + 1;
        }

        for (int i = 0; i < m; i++) {
            int num = sc.nextInt();
            list.add(num);
            array[num - 1] = -1;
        }
        sc.close();
        
        for (int i = 0; i < n; i++) {
            if (array[i] != -1) {
                remain.add(array[i]);
            }
        }

        int index = 0;
        while (remain.size() > 0) {
            boolean last = false;
            int tmp = remain.remove(0);
            while (list.get(index) < tmp ) {
                index++;
                if(index >= list.size()){
                    list.add(tmp);
                    last = true;
                    break;
                }
            }
            if(!last) {
                list.add(index, tmp);
            }
        }

        // 输出结果
        for (int i = 0; i < list.size() - 1; i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.print(list.get(list.size() - 1));
    }
}

核心思路是用一个list保存给定的数字，而另外一个remain list保存剩余的那些数字。那么我们只需要把remain中的数字放到题目给定的顺序中即可。

仔细想想只需要O(N)就够了，因为只需要遍历一遍。估计很多人都卡在这里因为他们又从头开始判断了，其实是不需要的。

第三题

我这里直接把题目抽象了一下，给定一个数组，找出两个子数组，让子数组的和相等；让剩下的那些元素的和越小越好。

emm 其实这道题我一开始想到的就是暴力，我们不妨设两个子数组为A和B，那么每个元素只有三种状态：在A中、在B中、不在AB中，所以如果暴力（DFS）的话，时间效率是O(3^N)，感觉显然不可能。后来仔细去看了一眼题目，N<=15….所以其实3¹⁵=1500万，emmm 其实完全是可以的….

事后补写的一个DFS的暴力解法：

public class Main {

    private static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            Item[] array = new Item[n];
            for (int j = 0; j < n; j++) {
                array[j] = new Item(sc.nextInt(), -1);
            }
            dfs(array, 0);
            System.out.println(min);
        }
    }


    public static void dfs(Item[] array, int index) {
        /**
         * -1 = 初始状态 1 = 在数组A中   2 = 在数组B中  3 = 都不在  4 = 已经遍历过了
         */

        // 跳出条件
        if (index == array.length) {
            getValue(array);
            return;
        }

        array[index].setStatus(1);
        dfs(array, index + 1);

        array[index].setStatus(2);
        dfs(array, index + 1);

        array[index].setStatus(3);
        dfs(array, index + 1);

    }

    private static void getValue(Item[] array) {
        int valueOfA = 0;
        int valueOfB = 0;
        int otherValue = 0;
        for (Item item : array) {
            if (1 == item.getStatus()) {
                valueOfA += item.getValue();
            } else if (2 == item.getStatus()) {
                valueOfB += item.getValue();
            } else if (3 == item.getStatus()) {
                otherValue += item.getValue();
            }
        }

        if (valueOfA == valueOfB) {
            min = Math.min(otherValue, min);
        }

    }
}

class Item {
    private int value;
    private int status;

    public Item(int value, int status) {
        this.value = value;
        this.status = status;
    }

    public int getValue() {
        return value;
    }
    
    public int getStatus() {
        return status;
    }

    public void setStatus(int status) {
        this.status = status;
    }
}

第四题

一道关于图的题目，连看都看不懂。算了。

总结

只做出了前两道，还是比较菜。第三题其实自己有想过暴力的解法，但是因为自己推算了时间复杂度是O(3^N)就直接放弃了…其实仔细看看题目中的N<=15，然后用笔算一算，就能得到正确结果的，稍微有点可惜了。