Java教程

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

本文主要是介绍【钛铂数据专场】力扣第 269 场周赛(2029 / 4292),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

在这里插入图片描述

文章目录

  • 一、第一题: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、题目解析

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

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

下次加油加油

这篇关于【钛铂数据专场】力扣第 269 场周赛(2029 / 4292)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!