【钛铂数据专场】力扣第 269 场周赛（2029 / 4292）

叁歲伎倆 2023-10-02 17:01 17阅读 0赞

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

![在这里插入图片描述][f30fb5d79279470f844fe0ef316d9b3a.png]

#### 文章目录 ####

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

## 一、5938. 找出数组排序后的目标下标 ##

### 1、题目简介 ###

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

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）  
![在这里插入图片描述][b60ff3afe336466daa6bb630459dbaac.png]

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

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16]

## 二、5939. 半径为 k 的子数组平均值 ##

### 1、题目简介 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 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;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_16_color_FFFFFF_t_70_g_se_x_16]

## 三、5940. 从数组中移除最大值和最小值 ##

### 1、题目简介 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 2]

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

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 3]

## 四、5941. 找出知晓秘密的所有专家 ##

### 1、题目简介 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 4]

### 2、题目解析 ###

*  看到这种传播性，直接就锁定并查集：[三分钟学会并查集][Link 1]
 *  简单来说，我们把相同时间的专家在一起进行处理，将他们进行合并
 *  当我们合并完之后，我们需要判断哪些是没有收到消息的，这里的判断题主一开始想差了，后来想到 并查集中的 `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;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_16_color_FFFFFF_t_70_g_se_x_16 1]

## 五、总结 ##

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

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

下次加油加油

[f30fb5d79279470f844fe0ef316d9b3a.png]: https://img-blog.csdnimg.cn/f30fb5d79279470f844fe0ef316d9b3a.png
[b60ff3afe336466daa6bb630459dbaac.png]: https://img-blog.csdnimg.cn/b60ff3afe336466daa6bb630459dbaac.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1c329b67c32643ac819298dbfae997b1.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/687305c05408428d864727810875f143.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_16_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4d7df2d3ec0d4e1cb99cbf93a15dea2f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_16,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/44ee7b50a77a451c93578e63611c833c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/1980aa8ae35b47c885ba726033a519e3.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/f50427d9fe4146bdbccf95ec14d3cb01.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[Link 1]: https://editor.csdn.net/md/?articleId=120401368
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_16_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/3d028635bd894a2ca6180ce975963600.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_16,color_FFFFFF,t_70,g_se,x_16