网易笔试参考答案研发岗

1 素数拆分

一个正整数数组A，可以把其中的某个元素A[i]拆分成若干个和为A[i]的数(也可以不拆分)，问这个数组里最多能有多少个素数。

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        long n = input.nextLong();
        long[] nums = new long[(int) n];
        long res = 0;

        for (long i = 0; i < nums.length; i++)
            nums[(int) i] = input.nextInt();

        // 2 是最小的素数，全部拆成最小的素数，把个数累加。
        for (long num : nums)
            res += num / 2;

        System.out.println(res);
    }
}

2. 排列

大概意思：保持第二行输入的顺序不变，假设为数组 A，把数组 B[1..n] 与 A 的差集按递增序插入。
事后诸葛亮。
示例数据

INPUT:
5 2
4 2

OUTPUT: 1 3 4 2 5

// 归并
public class Main {

    public static void main(String[] args) {
        // 0. Some kind of bullshit.
        Scanner input = new Scanner(System.in);
        List<Integer> res = new ArrayList<>();
        int n = input.nextInt();
        int m = input.nextInt();

        int[] A = new int[m]; // 用于存储已出现的数字
        int[] B = new int[n - m]; // 用于存储未出现的数字
        boolean[] C = new boolean[n + 1]; // 用于检验 A 是否出现

        // 1. 获取已有的数字 [2, 1, 5]
        for (int i = 0; i < m; i++) {
            A[i] = input.nextInt();
            C[A[i]] = true;
        }

        // 2. 获取剔除掉 1 中获取数字之后的数组
        int k = 0;
        for (int i = 1; i <= n; ++i)
            if (!C[i])
                B[k++] = i;

        // 3. 归并排序
        int idxA = 0, idxB = 0;
        while (idxA < m && idxB < k) {
            if (A[idxA] < B[idxB])
                res.add(A[idxA++]);
            else
                res.add(B[idxB++]);
        }

        // 4. 合并剩余部分
        while (idxA < m)
            res.add(A[idxA++]);

        while (idxB < k)
            res.add(B[idxB++]);

        for (int i = 0; i < res.size() - 1; i++)
            System.out.print(res.get(i) + " ");
        System.out.print(res.get(res.size() - 1));
    }
}

3. 平分礼物

// 回溯
public class Main {

    private static int res;

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        while (T-- > 0) {
            int n = input.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = input.nextInt();
                res += a[i];
            }

            dfs(a, 0, 0, 0, 0);
            System.out.println(res);
        }
    }

    /**
     * 递归更新最小抛弃价值
     * @param a 价值数组
     * @param i 价值下标
     * @param first 第一个人
     * @param second 第二个人
     * @param delta 要抛弃的价值
     */
    private static void dfs(int[] a, int i, int first, int second, int delta) {
        if (i == a.length) { // 分完一轮之后进行判断
            if (first == second) // 如果正好能够分的平均，更新最小值。
                res = Math.min(delta, res);
            return;
        }

        dfs(a, i + 1, first + a[i], second, delta); // 把 a[i] 分给第一个人
        dfs(a, i + 1, first, second + a[i], delta); // 把 a[i] 分给第二个人
        dfs(a, i + 1, first, second, delta + a[i]); // 把 a[i] 扔掉
    }
}

4. 送货xx