I haven't played the weekly game for a long time. I tried it this week. My record is endless. The last question was almost done by checking the collection
1, Question 1: 5938. Find the target subscript after array sorting
1. Topic introduction
Given two strings S and p, find the substrings of all ectopic words of p in s, and return the starting indexes of these substrings. Do not consider the order in which answers are output
Ectopic words refer to strings formed by rearrangement of the same letters (including the same string)
2. Topic analysis
- Check in question, sort the original array directly, and traverse the array equal to target
3. Title code
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;
}
}
2, Question 2: 5939. Average value of subarray with radius k
1. Topic introduction
2. Topic analysis
- Give you an array, let you find [i - k, i + k] / (2 * k + 1)
- There are two approaches to the topic
- The first is prefix sum. We find the prefix sum of the whole, and all AVGs can be found through arr[i + k] - arr[i - k - 1] / (2 * k + 1)
- The second is sliding window. When our window is sliding, our sum = sum + arr[i + k] - arr[i - k - 1] can calculate all AVGs
- The problem is that the given value range is 10 ^ 5 * 10 ^ 5, which exceeds the range of Int. you need to use long type to receive
3. Title code
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;
}
}
3, Question 3: 5940. Remove the maximum and minimum values from the array
1. Topic introduction
2. Topic analysis
- This topic has just come up. I originally wanted to use violent recursion to do it dynamically, but then I thought about it. It seems that I can do it greedily
- We first traverse to find the subscripts of the minimum and maximum values, and then calculate their distances from 0 and length to find the minimum values of these four distances
- After removing the minimum distance, we have removed one element at this time, and then calculate the distance between another element and 0 and length
3. Title code
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;
// Exclude the smallest one first
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;
}
}
4, Question 4: 5941. Find out all experts who know the secret
1. Topic introduction
2. Topic analysis
- When you see this propagation, you can directly lock and query the set: Learn and search the collection in three minutes
- In short, we put the experts at the same time together and merge them
- After we merge, we need to judge which messages we haven't received. The main judge here thought bad at first. Later, we thought and looked up the isSame in the set. We only need to judge whether the current point and expert 0 are in the same set. If they are not in the same set, we need to restore
- For restore processing, you can directly use parent[a] = a;, Of course, you can also use initialization and query set (however, it seems to time out)
- Finally, traverse which points are in a set with 0 good experts, and output it
3. Title code
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]);
}
// The output with the highest number of occurrences, large top stack
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 {
// Who is your big brother now
private int[] parent;
// How many people are there in your team (only big brother)
private int[] size;
// Auxiliary array
private int[] help;
// There are several factions in the Jianghu
int sets;
// initialization
// Everyone's big brother is himself
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;
}
}
5, Summary
This time, because the title is simple, the three questions are already at the level of the crane tail
It's a pity that we just reviewed the collection the day before yesterday. Unexpectedly, we missed the first AK in our life
Come on next time