8月8日网易校招笔试题

前言

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

第一题

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
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 那这题就是把数字插到它应该在的位置不就好了么….没看出有什么陷阱:

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
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(3N),感觉显然不可能。后来仔细去看了一眼题目,N<=15….所以其实315=1500万,emmm 其实完全是可以的….

事后补写的一个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
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
72
73
74
75
76
77
78
79
80
81
82
83
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(3N)就直接放弃了…其实仔细看看题目中的N<=15,然后用笔算一算,就能得到正确结果的,稍微有点可惜了。