The fourth day of swiping questions and punching cards
- 1. (Medium Questions) 1306. Jumping Game III
- 2. (Simple question) 703. The K th largest element in the data stream
- 3. (Simple question) 1337. K rows with the weakest combat power in the matrix
1. (Medium Questions) 1306. Jumping Game III
Original title link: 1306. Jumping Game III
Title description:
Here there is an array arr of non-negative integers, and you are initially located at the starting subscript start of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i]. Please judge whether you can jump to any subscript whose corresponding element value is 0. Note that you cannot jump outside of the array no matter what the circumstances.
This problem can be solved recursively. For details, please refer to the notes:
class Solution {
public boolean canReach(int[] arr,int start){
boolean[] check = new boolean[arr.length];
//A recursive function to determine whether a subscript with an element value of 0 is found
return zero(check,arr,start);
}
public boolean zero(boolean[] check,int[] arr,int start){
//If the subscript exceeds the range of the array, then false
if(start < 0 || start >= arr.length) return false;
//Find the corresponding subscript with element value 0, return true
if(arr[start] == 0) return true;
//If the current subscript has been traversed, it means that it has been traversed repeatedly, and returns false
if(check[start]){
return false;
}else{//If it is the first traversal, record it for the convenience of the next comparison
check[start] = true;
}
//Repeat the above traversal operation recursively
return zero(check,arr,start+arr[start]) || zero(check,arr,start-arr[start]);
}
}Submit results:
2. (Simple question) 703. The K th largest element in the data stream
Original title link: 703. K th Largest Element in Data Stream
Title description:
Design a class that finds the k th largest element in a data stream. Note that it is the kth largest element after sorting, not the kth distinct element.
Problem-solving ideas: The title requires the kth largest element in the data stream array. You only need to put all the elements in the minimum heap. If the number of heap nodes is greater than k, delete the top node of the heap to adjust, so that the number of heap nodes remains at k. In this way, the top of the heap The element is the k th largest element we require.
Problem-solving code:
class KthLargest {
//Set global variables, namely k and priority queue;
int k;
PriorityQueue<Integer> que;
public KthLargest(int k, int[] nums) {
que = new PriorityQueue<Integer>();//set to min-heap
this.k = k; //The integer passed in is assigned to k
for(int num : nums) //Enhanced for loop to traverse data stream
add(num);
}
public int add(int val) {
que.offer(val); //Put data into min heap
while(que.size() > k){//If the number of heap nodes is greater than k
que.poll(); //Remove the minimum value at the top of the heap
}
return que.peek(); //Return the current top element is the k th largest element
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/Submit results:
3. (Simple question) 1337. K rows with the weakest combat power in the matrix
Original title link: The K rows with the weakest combat power in the matrix
Title description:
Given a matrix mat of size m * n, the matrix is composed of several soldiers and civilians, represented by 1 and 0 respectively. Please return the indices of the k rows with the weakest combat power in the matrix, sorted from weakest to strongest. If row i has fewer soldiers than row j, or if both rows have the same number of soldiers but i is less than j, then we consider row i to be weaker than row j. Soldiers always come first in a line, that is, 1s always appear before 0s. / Example 1: input: mat= [[1,1,0,0,0], [1,1,1,1,0], [1,0,0,0,0], [1,1,0,0,0], [1,1,1,1,1]], k = 3 Output: [2,0,3] explain: Number of soldiers in each row: row 0 -> 2 line 1 -> 4 row 2 -> 1 line 3 -> 2 line 4 -> 5 Sort the rows from weakest to strongest to get [2,0,3,1,4] / Example 2: input: mat= [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]], k = 2 Output: [0,2] explain: Number of soldiers in each row: row 0 -> 1 line 1 -> 4 row 2 -> 1 Line 3 -> 1 Sort the rows from weakest to strongest to get [0,2,3,1]
Problem-solving ideas: The title requires ranking the strength of the team from weak to strong. The more soldiers, the stronger. When the number of soldiers is the same, the larger the team subscript, the stronger. Then we can use a one-dimensional array of length 2 to store each team: int[]{val，index} val represents the total number of soldiers in the team; index represents the number of rows of the team; Put the data of each team into the minimum heap and sort, the one with the smallest int[0] is the priority, and if the number of troops is the same, the one with the smallest int[1] is the priority. Finally, the elements on the top of the pile are taken out for storage, and the team is arranged in order from weak to strong.
Problem-solving code:
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
//Create a priority queue, the default is the min heap
//The node elements in the heap are arrays int[]{val,index},
//1.val represents the number of soldiers, 2.index represents the index line
//The minimum heap sorting rule is to compare the number of soldiers first, and then compare the size of the row number index if they are the same, and the smaller one is preferred
PriorityQueue<int[]> que = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a,int[] b){
return a[0] != b[0]?a[0] - b[0]:a[1]-b[1];
}
});
//Used to record the number of soldiers in each line
int sum;
for(int i = 0;i < mat.length;++i){
sum = 0;
for(int n : mat[i]){
if(n == 1) sum++;
}
que.offer(new int[]{sum,i});//Put int[]{the number of soldiers, the index line} into the minimum heap sorting
}
int[] sort = new int[k];
for(int i = 0;i < k;++i){
sort[i] = que.poll()[1];//Take out the weakest index row team at the top of the heap
}
return sort;//Output Team Ranking
}
}Submit results:
Persistence is important: ✨Follow the author and make progress together with the author...
