### 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:

copyclass 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:

copyclass 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:

copyclass 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...