网易笔试（内推）- 20200808 - Java后端开发

发表于 | 分类于 |

笔试一共四道编程题，共100min:imp:。

鄙人全军覆没~:innocent:

下面是大佬的题解~

1. 素数的个数

给出一个包含n个正整数的数组a，把a[i]拆分为若干个和为a[i]的素数，求拆分后最多能有多少个素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
第一行数据为n，表示数组长度，第二行为n个元素。
输入:
3
1 1 1
输出:
0
不可拆分
 
输入:
4
1 3 5 7
输出：
6
1为0个，3为1个，5为（2,3），7为（2,2,3）

根据规律可得：nums[i]/2就是该元素可以分出的素数个数。发现自己真的想多了，原来是在找规律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Scanner;
class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int[] nums = new int[len];
        long result = 0;
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextInt();
 
            //规律：nums[i]/2就是nums[i]可以分出的素数个数
            result += nums[i] / 2;
        }
 
        System.out.println(result);
    }
}

2. 字典序最小的排列

没做，题目让我看蒙了:disappointed:。

给出一个长度为m的序列T，求一个长度为n且字典序最小的排列S，要求不改变原序列中元素的相对位置。

1
2
3
4
5
6
第一行输入两个正整数n和m
第二行输入m个数，表示序列
5 3
2 1 5
输出
2 1 3 4 5

合并数组 + 双指针。先通过HashSet取出缺失的元素，组成nums2数组。需要result数组的注意第一个元素，nums1和nums2的第一个元素，谁小，先存谁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.HashSet;
import java.util.Scanner;
public class Solution{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int len = sc.nextInt();
        int len1 = sc.nextInt();
        int[] nums1 = new int[len1];
 
        HashSet<Integer> set = new HashSet<>();
        for(int i=0;i<nums1.length;i++){
            nums1[i] = sc.nextInt();
            set.add(nums1[i]);
        }
 
        //nums2，长度为len-len1，存放互补的元素
        int[] nums2 = new int[len-len1];
        int index = 0;
        for(int i=1;i<=len;i++){
            if(!set.contains(i)){
                nums2[index++] = i;
            }
        }
 
        /*双指针判断
        i指针用于控制nums1移动
        j指针用于控制nums2移动
        */
 
        int i = 0;
        int j = 0;
 
        int[] result = new int[len];
        int Resultindex = 0;
 
        //谁的第一个小谁就先存
        if(nums1[0] < nums2[0]){
            result[Resultindex++] = nums1[0];
            i=1;
        }else{
            result[Resultindex++] = nums2[0];
            j=1;
        }
 
        while(i < nums1.length && j < nums2.length){
 
            //谁小存谁
            if(nums1[i] < nums2[j]){
                result[Resultindex++] = nums1[i++];
            }else{
                result[Resultindex++] = nums2[j++];
            }
        }
 
        //补充存入最后一个数
        while(i == nums1.length && j < nums2.length){
            //如果nums1完但nums2未完，存入nums2
            result[Resultindex++] = nums2[j++];
        }
        while(i < nums1.length && j == nums2.length){
            //如果nums2完但nums1未完，存入nums1
            result[Resultindex++] = nums1[i++];
        }
 
        for(int k=0;k<result.length-1;k++){
            System.out.print(result[k] + " ");
        }
        System.out.print(result[result.length-1]);
    }
}

3. 丢弃最少物品

好题好题！

给出n个物品，每个物品都有自己的价值，每个物品只有一件，这些物品需要分给两个人，要求分配完之后，两个人的物品价值相同。分配完成之后，会丢弃剩下的物品，求最少要丢弃多少物品。

1
2
3
4
5
6
7
输入
输入第一行为总的测试数据个数，第二行为物品个数n，第三行为n个物品的价值。
1
5
30 60 5 15 30
输出
20 丢弃5和15，把60分配给第一个人，2个30分配给第二个人。

根据大佬的思路：dfs回溯 + 分与不分，实在是没想到dfs还有这种用法，之前只会用dfs计算组合，这次算是学到了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Scanner;
public class Solution{
    public static int result = Integer.MAX_VALUE;
    public static int sum = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int group = sc.nextInt();
        //以后多组读入可以采用这种方式,学到了
        while(group-- > 0){
 
            int len = sc.nextInt();
            int[] nums = new int[len];
            for(int i=0;i<nums.length;i++){
                nums[i] = sc.nextInt();
                sum += nums[i];
            }
 
            //index从0开始，第一个人拥有的为result1，第二个人用于的为result2。都初始为0
            dfs(nums,0,0,0);
 
            System.out.println(result);
        }
    }
 
    private static void dfs(int[] nums, int index, int result1, int result2) {
        //递归出口
        if(index == nums.length){
            //当result1 == result2时
            if(result1 == result2){
                result = Math.min(result,sum - 2*result1);
            }
            return;
        }
 
        //分为3中情况，
        /*
        1. 谁都不给
        2. 给第一个：result1 + nums[index]
        3. 给第二个：result2 + nums[index]
         */
        dfs(nums,index+1,result1,result2);
        dfs(nums,index+1,result1+nums[index],result2);
        dfs(nums,index+1,result1,result2+nums[index]);
    }
}

4. 运送货物

第四题看了一眼，emmm，是我惹不起的…