腾讯笔试 9.6（附代码）

一开始不知道啥情况，进不去笔试，少考十分钟。只 a 了 4.05，哭了。

题目记不得了，等其他大佬补充，我把代码附上。

ac
思路：有序的，直接遍历比较就可以了

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Node head1 = new Node();
        Node head2 = new Node();
        int n = sc.nextInt();
        Node cur = head1;
        for(int i = 0; i < n; i++) {cur.next = new Node(sc.nextInt()); cur = cur.next;}
        int m = sc.nextInt();
        cur = head2;
        for(int i = 0; i < m; i++) {cur.next = new Node(sc.nextInt()); cur = cur.next;}
        Solution s = new Solution();
        s.solve(head1.next, head2.next);
    }
}


class Solution{
    void solve(Node head1, Node head2) {
        StringBuilder ans = new StringBuilder();
        while(head1 != null && head2 != null) {
            if(head1.val > head2.val) head1 = head1.next;
            else if(head2.val > head1.val) head2 = head2.next;
            else {
                ans.append(head1.val + " ");
                head1 = head1.next;
                head2 = head2.next;
            }
        }
        System.out.println(ans.toString().substring(0,ans.length() - 1));
    }
}

class Node{
    int val;
    Node next;
    public Node() {}
    public Node(int val) {
        this.val = val;
    }
}

ac
思路：
把团队看成节点，人在哪些团队里，这些团队直接就连条边。
从 0 所在的团队出发，遍历到的团队，就是能通知到的团队。里面的人数就是答案

import java.util.*;
//2.小团队
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Map<Integer, List<Integer>> map1 = new HashMap();//存放每个组里有哪些人
        Map<Integer, List<Integer>> map2 = new HashMap();//存放一个人在哪些组里
        for(int i = 0; i < m; i++) {
            List<Integer> list = new ArrayList();
            int pn = sc.nextInt();
            for(int j = 0; j < pn; j++) {
                int p = sc.nextInt();
                list.add(p);
                List<Integer> zuList = map2.getOrDefault(p, new ArrayList());
                zuList.add(i);
                map2.put(p, zuList);
            }
            map1.put(i, list);
        }
        Solution s = new Solution();
        s.solve(n, m, map1, map2);
    }
}


class Solution{
    void solve(int n,int m, Map<Integer, List<Integer>> map1, Map<Integer, List<Integer>> map2) {
        Set<Integer>[] nextZu = new Set[m];
        for(int i = 0; i < m; i++) nextZu[i] = new HashSet();
        boolean[] vis = new boolean[n];
        for(Integer p: map2.keySet()) {
            for(Integer zu: map2.get(p)) {
                for(Integer zu2: map2.get(p)) {
                    nextZu[zu].add(zu2);
                    nextZu[zu2].add(zu);
                }
            }
        }
        Set<Integer> visZu = new HashSet();
        for(Integer zu: map2.get(0)) {
            dfs(visZu, zu, nextZu);
        }
        Set<Integer> visP = new HashSet();
        for(Integer zu: visZu) {
            for(Integer p: map1.get(zu)) visP.add(p);
        }
         System.out.println(visP.size());
    }

    void dfs(Set<Integer> visZu, int zu, Set<Integer>[] nextZu) {
        if(visZu.contains(zu)) return;
        visZu.add(zu);
        for(Integer zu2: nextZu[zu]) {
            if(visZu.contains(zu2)) continue;
            dfs(visZu, zu2, nextZu);
        }
    }
}

3.ac
思路：top k问题，用堆就可以了

import java.util.*;
字符串比较
public class Main{
    public static void main(String[] args) {
        Solution s = new Solution();
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        Map<String, Node> map = new HashMap();//存放字符串对应的结点
        sc.nextLine();
        for(int i = 0; i < N; i++) {
            String str = sc.nextLine();
            Node node = map.getOrDefault(str, new Node(str));
            node.nums++;
            map.put(str, node);
        }
        s.solve(K, map);
    }
}


class Solution{
    void solve(int K, Map<String, Node> map) {
        PriorityQueue<Node> minheap = new PriorityQueue<Node>((a, b) ->
        a.nums != b.nums ? a.nums - b.nums : compare(a.val, b.val));
        PriorityQueue<Node> maxheap = new PriorityQueue<Node>((a, b) ->
        a.nums != b.nums ? b.nums - a.nums : compare(a.val, b.val));
        for(String key: map.keySet()) {
            Node node = map.get(key);
            minheap.add(node);
            maxheap.add(node);
        }
        for(int i = 0; i < K; i++) {
            Node node = maxheap.poll();
            System.out.println(node.val + " " + node.nums);
        }
        for(int i = 0; i < K; i++) {
            Node node = minheap.poll();
            System.out.println(node.val + " " + node.nums);
        }
    }

    int compare(String a, String b) {
        int len = Math.min(a.length(), b.length());
        for(int i = 0; i < len; i++) {
            if(a.charAt(i) == b.charAt(i)) continue;
            return a.charAt(i) - b.charAt(i);
        }
        return a.length() - b.length();
    }
}

class Node{
    String val;
    int nums;
    public Node(String val) {
        this.val = val;
        nums = 0;
    }
}

ac
思路：找规律，原中位数有俩 mid 和 mid2。
删除的数字 <= mid，则中位数为 mid2。
否则，为mid

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Solution s = new Solution();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        int[] sort = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
            sort[i] = nums[i];
        }
        Arrays.sort(sort);
        s.solve(nums, sort[n / 2 - 1], sort[n/2]);
    }
}


class Solution{
    void solve(int[] nums, int mid, int mid2) {
        for(int num: nums) {
            if(num <= mid) System.out.println(mid2);
            else System.out.println(mid);
        }
    }
}