9月6日腾讯笔试

前言

2020年9月6日晚上8点-10点的腾讯笔试。总体难度偏低

第一题

给定两个降序链表,求出其中的公共部分。本质上其实就是给定两个降序数组,然后找出公共部分,那用两个指针分别去做就可以了。

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
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int l = sc.nextInt();
int[] array = new int[l];
for (int i = 0; i < array.length; i++) {
array[i] = sc.nextInt();
}
int r = sc.nextInt();
int[] array2 = new int[r];
for (int i = 0; i < array2.length; i++) {
array2[i] = sc.nextInt();
}

List<Integer> res = new ArrayList<>();
int i = 0, j = 0;
while (i != l && j != r) {
if (array[i] == array2[j]) {
res.add(array[i]);
i++;
j++;
} else if (array[i] > array2[j]) {
i++;
} else {
j++;
}
}
for (Integer re : res) {
System.out.print(re + " ");
}
}
}

第二题

给定N个链表,每个链表中有数字,其中一个数字可能在多个链表中出现,也可能这个数字在任何链表中都不出现。一旦一个链表中的一个数字被标记了,那么整个链表都会被标记,根据这条规则开始扩散,求出最后能有多少个数字被扩散到。直接暴力就能过。

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
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
List<List<Integer>> lists = new LinkedList<>();
for (int i = 0; i < m; i++) {
int i1 = in.nextInt();
List<Integer> temp = new LinkedList<>();
for (int j = 0; j < i1; j++) {
temp.add(in.nextInt());
}
lists.add(temp);
}
Set<Integer> set = new HashSet<>();
set.add(0);
while (true) {
boolean flag = false;
List<Integer> needToBeRemoved = null;
for (List<Integer> l : lists) {
for (Integer integer : l) {
if (set.contains(integer)) {
set.addAll(l);
needToBeRemoved = l;
flag = true;
break;
}
}
}
lists.remove(needToBeRemoved);
if (!flag) {
break;
}
}
System.out.println(set.size());
}
}

第三题

给定N个字符串,求出出现次数最多的K个字符串以及出现次数最少的字符串。

直接调用API的题目,就不展示了。

第四题

给定一个数组(保证长度N是偶数),每次删掉其中的一位,求出剩余N-1的中位数。

思路也很简单,就是排个序,因为是偶数的数组,所以必然有两个中位数,然后判断每次删除的数字是在前面的还是在后面的,分别打印即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] array = new int[n];
List<Integer> list = new LinkedList<>();
for (int i = 0; i < array.length; i++) {
array[i] = sc.nextInt();
list.add(array[i]);
}


Collections.sort(list);
int small = list.get(n / 2 - 1);
int big = list.get(n / 2);
for (int i = 0; i < n; i++) {
if (array[i] <= small) {
System.out.println(big);
} else {
System.out.println(small);
}
}
}
}

第五题

我个人感觉是冒泡排序,有两种可能,先排红色的,再排黑色的;或者是先排黑色的,再排红色的,根据这个来做。但是由于比较复杂就放弃了。

总结

腾讯的笔试应该算是最简单的那类了…