0913微众Java笔试ak

前两题直接看代码。

第三题我自己试过一些用例，如果是没考虑可以直接连通，会是70%。然后如果考虑了直接连通，可能是因为没有先进行并查集的“扫描”，只用了题目给的条件判断是否连通，会是50%。

————————————

更新：2023.12.19约面，无语辣。没提前沟通时间，联系hr要求改时间，hr说要和面试官讲下。然后又没后续了，随便吧，也没打算继续。

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n + 1];
        // 记录该数字上一次出现的下标
        Map<Integer, Integer> lastMap = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            int num = sc.nextInt();
            if (lastMap.containsKey(num)) {
                arr[lastMap.get(num)] = 0;
            }
            lastMap.put(num, i);
            arr[i] = num;
        }
        for(int i =1;i<=n;i++){
            if(arr[i]!=0){
                System.out.print(arr[i]+" ");
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        LinkedList<Integer> list = new LinkedList();
        // 第一首直接放
        System.out.print(sc.nextInt() + " ");
        while (--n > 0) {
            list.add(sc.nextInt());
        }
        while (!list.isEmpty()) {
            list.add(list.removeFirst());
            System.out.print(list.removeFirst() + " ");
        }
    }
}

public class Main {
    private static Map<Integer, Set<Integer>> lineMap = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), s = sc.nextInt(), t = sc.nextInt();
        lineMap.clear();
        while (m-- > 0) {
            int x = sc.nextInt(), y = sc.nextInt();
            if (!lineMap.containsKey(x)) {
                lineMap.put(x, new HashSet<>());
            }
            if (!lineMap.containsKey(y)) {
                lineMap.put(y, new HashSet<>());
            }
            Set<Integer> xReach = lineMap.get(x);
            Set<Integer> yReach = lineMap.get(y);
            xReach.add(y);
            yReach.add(x);
        }
        Set<Integer> sCanReachSet = new HashSet<>();
        Set<Integer> tCanReachSet = new HashSet<>();
        int sGroupCount = reachCount(s, sCanReachSet);
        int tGroupCount = reachCount(t, tCanReachSet);
        // 可以直接到达的情况
        if (sCanReachSet.contains(t)) {
            // 排列组合的 C n 2
            System.out.println((n - 1) * (n) / 2);
        } else {
            System.out.println(sGroupCount * tGroupCount);
        }
    }

    // 获取从指定岛屿能到达的岛屿的个数（包含此岛屿）
    public static int reachCount(int n, Set<Integer> counted) {
        if (!lineMap.containsKey(n)) {
            return 1;
        }
        counted.add(n);
        Set<Integer> canReachSet = lineMap.get(n);
        for (Integer canReach : canReachSet) {
            if (counted.add(canReach)) {
                reachCount(canReach, counted);
            }
        }
        return counted.size();
    }
}