9月6日腾讯笔试

前言

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

第一题

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

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

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的中位数。

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

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);
            }
        }
    }
}

第五题

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

总结

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