好久没有打周赛了，本周试了一下，战绩一言难尽，最后一题并查集差一点就做出来了

文章目录

• 一、第一题：5938. 找出数组排序后的目标下标
• • 1、题目简介
  • 2、题目解析
  • 3、题目代码
• 二、第二题：5939. 半径为 k 的子数组平均值
• • 1、题目简介
  • 2、题目解析
  • 3、题目代码
• 三、第三题：5940. 从数组中移除最大值和最小值
• • 1、题目简介
  • 2、题目解析
  • 3、题目代码
• 四、第四题：5941. 找出知晓秘密的所有专家
• • 1、题目简介
  • 2、题目解析
  • 3、题目代码
• 五、总结

一、第一题：5938. 找出数组排序后的目标下标

1、题目简介

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）

2、题目解析

• 签到题，直接排序原数组，遍历一遍等于 target 的即可

3、题目代码

class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == target){
                list.add(i);
            }
        }
        return list;
    }
}

二、第二题：5939. 半径为 k 的子数组平均值

1、题目简介

2、题目解析

• 给你一个数组，让你求 [i - k, i + k] / (2 * k + 1)
• 题目有两种做法
  • 第一种是前缀和，我们求出整体的前缀和，通过 arr[i + k] - arr[i - k - 1] / (2 * k + 1) 即可求出所有的 avg
  • 第二种是滑动窗口，当我们窗口在滑动时，我们的 sum = sum + arr[i + k] - arr[i - k - 1] 即可求出所有的 avg
• 题目比较坑的点在于给的取值范围为 10^5 * 10^5 超过了 Int 的范围，需要使用 long 类型来进行接收

3、题目代码

class Solution {
     public int[] getAverages(int[] nums, int k) {
        long sum = 2 * k + 1;
        int n = nums.length;
        long[] arr = new long[n];
        arr[0] = nums[0];
        int[] target = new int[n];
        int num = 0;
        for (int i = 1; i < n; i++) {
            arr[i] = arr[i - 1] + nums[i];
        }
        for (int i = 0; i < n; i++) {
            if (i - k >= 0 && i + k < n) {
                if (i - k == 0) {
                    target[num++] = (int)(arr[i + k] / sum);
                } else {
                    target[num++] = (int) ((arr[i + k] - arr[i - k - 1]) / sum);
                }
            } else {
                target[num++] = -1;
            }
        }
        return target;
    }
}

三、第三题：5940. 从数组中移除最大值和最小值

1、题目简介

2、题目解析

• 这个题目刚上来本来想用暴力递归转动态去做，但后来想了想，好像可以贪心做
• 我们先进行遍历，求出 最小值 和 最大值 的下标，然后计算其与 0 和 length 的距离，求这四个距离的最小值
• 去掉距离的最小值后，这个时候我们已经去除了一个元素，然后计算另一个元素和 0 和 length 距离即可

3、题目代码

class Solution {
    public int minimumDeletions(int[] nums) {
        int sum = 0;
        int n = nums.length;
        if(n <= 1){
            return 1;
        }
        
        int min = nums[0];
        int indexMin = 0;
        int max = nums[0];
        int indexMax = 0;
        for(int i = 1; i < n; i++){
            if(min > nums[i]){
                min = nums[i];
                indexMin = i;
            }
            if(max < nums[i]){
                max = nums[i];
                indexMax = i;
            }
        }
        
        int num1 = n - 1 - indexMin;
        int num2 = n - 1 - indexMax;
        
        // 先排除一个最小的
        int numMin = Math.min(Math.min(indexMin, indexMax), Math.min(num1, num2));
        
        //System.out.println(numMin);
        
        if(numMin == indexMin){
            sum = sum + indexMin + 1;
            sum = sum + Math.min(num2, indexMax - indexMin - 1) + 1;
        }else if(numMin == indexMax){
            sum = sum + indexMax + 1;
            sum = sum + Math.min(num1, indexMin - indexMax - 1) + 1;
        }else if(numMin == num1){
            sum = sum + num1 + 1;
            sum = sum + Math.min(indexMax, num2 - num1 - 1) + 1;
        }else{
            sum = sum + num2 + 1;
            sum = sum + Math.min(indexMin, num1 - num2 - 1) + 1;
        }
        
        return sum;
        
    }
}

四、第四题：5941. 找出知晓秘密的所有专家

1、题目简介

2、题目解析

• 看到这种传播性，直接就锁定并查集：三分钟学会并查集
• 简单来说，我们把相同时间的专家在一起进行处理，将他们进行合并
• 当我们合并完之后，我们需要判断哪些是没有收到消息的，这里的判断题主一开始想差了，后来想到 并查集中的 isSame 可以判断，我们只需要判断当前的点和 0号专家 在不在一个集合即可，如果不在一个集合，我们需要进行还原处理
  • 还原处理的话，可以直接使用 parent[a] = a;，当然也可以使用初始化并查集（不过，好像会超时）
• 最后，遍历一下哪些点与 0好专家 在一个集合，输出即可

3、题目代码

class Solution {
    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        Set<Integer> time = new HashSet<>();
        HashMap<Integer, List<int[]>> setHashMap = new HashMap<>();
        for (int i = 0; i < meetings.length; i++) {
            if (setHashMap.containsKey(meetings[i][2])) {
                List<int[]> list = setHashMap.get(meetings[i][2]);
                list.add(meetings[i]);
            } else {
                List<int[]> list = new ArrayList<>();
                list.add(meetings[i]);
                setHashMap.put(meetings[i][2], list);
            }
            time.add(meetings[i][2]);
        }
        // 次数出现最多的输出，大顶堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (Integer key : time) {
            priorityQueue.add(key);
        }
        UnionAndFind unionAndFind = new UnionAndFind(n);
        unionAndFind.union(0, firstPerson);
        while (!priorityQueue.isEmpty()) {
            Integer integer = priorityQueue.poll();
            List<int[]> list = setHashMap.get(integer);
            for (int i = 0; i < list.size(); i++) {
                int[] arr = list.get(i);
                unionAndFind.union(arr[0], arr[1]);
            }
            for (int i = 0; i < list.size(); i++) {
                if (!unionAndFind.isSameSet(0, list.get(i)[0])) {
                    unionAndFind.guli(list.get(i)[0]);
                    unionAndFind.guli(list.get(i)[1]);
                }
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (unionAndFind.isSameSet(0, i)) {
                list.add(i);
            }
        }
        return list;
    }
}

class UnionAndFind {
    // 当前自己的大哥是谁
    private int[] parent;
    // 当前自己的队伍有多少人(只有大哥有)
    private int[] size;
    // 辅助数组
    private int[] help;
    // 江湖还有几个派系
    int sets;

    // 初始化
    // 每个人的大哥都是自己
    public UnionAndFind(int N) {
        parent = new int[N];
        size = new int[N];
        help = new int[N];
        sets = N;
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int i) {
        int h = 0;
        while (i != parent[i]) {
            help[h++] = i;
            i = parent[i];
        }
        for (h--; h >= 0; h--) {
            parent[help[h]] = i;
        }
        return i;
    }

    public boolean isSameSet(int a, int b) {
        return find(a) == find(b);
    }

    public void union(int a, int b) {
        int A = find(a);
        int B = find(b);
        if (A != B) {
            if (size[A] >= size[B]) {
                size[A] += size[B];
                parent[B] = A;
            } else {
                size[B] += size[A];
                parent[A] = B;
            }
            sets--;
        }
    }

    public void guli(int a) {
        parent[a] = a;
    }
}

五、总结

这次由于题目简单，导致三题已经是吊车尾的水平了

比较可惜的是，并查集前天刚刚复习，没想到还原并查集的操作，错失了人生中的第一次AK

下次加油加油