网易笔试(内推)- 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,是我惹不起的…