首页 > 9.6 腾讯后台开发笔试
头像
lulululud
编辑于 2020-09-06 22:07
+ 关注

9.6 腾讯后台开发笔试

第一题    数组公共子序列,,数组下标异步挪动就行
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len1 = sc.nextInt();
        int[] nums1 = new int[len1];
        for(int i = 0; i < len1; ++i) {
            nums1[i] = sc.nextInt();
        }
        int len2 = sc.nextInt();
        int[] nums2 = new int[len2];
        for(int i = 0; i < len2; ++i) {
            nums2[i] = sc.nextInt();
        }
        sc.close();
        int[] ans = solution(nums1, nums2);
        if(ans.length >= 1) {
            for(int i = 0; i < ans.length - 1; ++i) {
                System.out.print(ans[i] + " ");
            }
            System.out.print(ans[ans.length - 1]);
        }
    }

    static int[] solution(int[] arr1, int[] arr2) {
        if(arr1.length == 0 || arr2.length == 0) {
            return new int[0];
        }
        int index1 = 0, index2 = 0, len1 = arr1.length, len2 = arr2.length;
        ArrayList<Integer> temp = new ArrayList<>();
        while(index1 < len1 && index2 < len2) {
            if(arr1[index1] == arr2[index2]) {
                temp.add(arr1[index1]);
                ++index1;
                ++index2;
            }
            else if(arr1[index1] > arr2[index2]) {
                ++index1;
            }
            else {
                ++index2;
            }
        }
        int[] ans = new int[temp.size()];
        for(int i = 0; i < temp.size(); ++i) {
            ans[i] = temp.get(i);
        }
        return ans;
    }
}
第二题  字符串次数前k个,后k个,哈希表排序
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        HashMap<String, Integer> map = new HashMap<>();
        String temp;
        for(int i = 0; i < N; ++i) {
            temp = sc.next();
            map.put(temp, map.getOrDefault(temp, 0) + 1);
        }
        ArrayList<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort((o1, o2) -> !o1.getValue().equals(o2.getValue()) ? o2.getValue() - o1.getValue() :
                o1.getKey().compareTo(o2.getKey()));

        for(int i = 0; i < K; ++i) {
            System.out.println(list.get(i).getKey() + " " + list.get(i).getValue());
        }
        list = new ArrayList<>(map.entrySet());
        list.sort((o1, o2) -> !o1.getValue().equals(o2.getValue()) ? o1.getValue() - o2.getValue() :
                o1.getKey().compareTo(o2.getKey()));
        for(int i = 0; i < K; ++i) {
            System.out.println(list.get(i).getKey() + " " + list.get(i).getValue());
        }
    }
}
第三题。第四题顺序记不住了,
寻找中位数,还是哈希表排序,记住中位数以及中位数前一个数的下标就行
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] nums = new int[N];
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < N; ++i) {
            nums[i] = sc.nextInt();
            map.put(i, nums[i]);
        }
        sc.close();

        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(Comparator.comparingInt(Map.Entry::getValue));
        int mid = list.get(N / 2).getKey();
        int subMid = list.get(N / 2 - 1).getKey();
        if(nums[mid] == nums[subMid]) {
            for(int i = 0; i < N; ++i) {
                System.out.println(nums[mid]);
            }
        }
        else {
            for(int i = 0; i < N; ++i) {
                if(nums[i] >= nums[mid]) {
                    System.out.println(nums[subMid]);
                }
                else {
                    System.out.println(nums[mid]);
                }
            }
        }
    }
}
通知人数,典型的图的遍历,我采用的是BFS,将第一个包含0的团队加进双端队列queue,设置visited集合标记以通知过的编号,对应queue中的每一个元素循环遍历其他团队中的编号,
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        ArrayList<HashSet<Integer>> list = new ArrayList<>();
        HashSet<Integer> temp;
        int flag = -1, num, len;
        for(int i = 0; i < M; ++i) {
            len = sc.nextInt();
            temp = new HashSet<>();
            for(int j = 0; j < len; ++j) {
                num = sc.nextInt();
                if(num == 0 && flag == -1) {
                    flag = i;
                }
                temp.add(num);
            }
            list.add(temp);
        }
        sc.close();
        if(flag == -1) {
            System.out.println(0);
        }
        else {
            LinkedList<Integer> queue = new LinkedList<>();
            HashSet<Integer> visited = new HashSet<>();
            temp = list.remove(flag);
            for(Integer integer : temp) {
                queue.addLast(integer);
                visited.add(integer);
            }
            int size;

            while(!queue.isEmpty()) {
                size = queue.size();
                for(int i = 0; i < size; ++i) {
                    num = queue.removeFirst();
                    for(HashSet<Integer> set : list) {
                        if(set.contains(num)) {
                            for(Integer integer : set) {
                                if(!visited.contains(integer)) {
                                    queue.addLast(integer);
                                    visited.add(integer);
                                }
                            }
                        }
                    }
                }
            }
            System.out.println(visited.size());
        }
    }
}


全部评论

(7) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐