一、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
下次加油加油
