刷题打卡第四天
一、（中等题）1306. 跳跃游戏 III
二、（简单题）703. 数据流中的第 K 大元素
三、（简单题）1337. 矩阵中战斗力最弱的 K 行
一、（中等题）1306. 跳跃游戏 III
原题链接：1306. 跳跃游戏 III
题目描述：
这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意，不管是什么情况下，你都无法跳到数组之外。
这道题可以用递归来解决，具体做法可以看注释：
class Solution { public boolean canReach(int[] arr,int start){ boolean[] check = new boolean[arr.length]; //判断是否找到元素值为0的下标的递归函数 return zero(check,arr,start); } public boolean zero(boolean[] check,int[] arr,int start){ //如果下标超出数组范围，然会假 if(start < 0 || start >= arr.length) return false; //找到元素值为0的对应下标，返回真 if(arr[start] == 0) return true; //如果当前下标被遍历过，说明重复遍历了，返回假 if(check[start]){ return false; }else{//如果是第一次遍历，给记录下来，方便下次比对 check[start] = true; } //递归地重复上述遍历操作 return zero(check,arr,start+arr[start]) || zero(check,arr,start-arr[start]); } }
提交结果：
二、（简单题）703. 数据流中的第 K 大元素
原题链接：703. 数据流中的第 K 大元素
题目描述：
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
解题思路：
题目要求数据流数组中的第k大元素，只需要将元素都放到最小堆中，堆节点数大于k就删除堆顶节点来调整，让堆节点数保持在k个，这么一来堆顶元素就是我们要求的第k大元素。
解题代码：
class KthLargest { //设置全局变量，分别是k以及优先队列； int k; PriorityQueue<Integer> que; public KthLargest(int k, int[] nums) { que = new PriorityQueue<Integer>();//设置为最小堆 this.k = k; //传递进来的整数赋值给k for(int num : nums) //增强for循环遍历数据流 add(num); } public int add(int val) { que.offer(val); //将数据放入最小堆 while(que.size() > k){//如果堆节点数大于k que.poll(); //删除堆顶的最小值 } return que.peek(); //返回当前堆顶元素便是第k大元素 } } /** * Your KthLargest object will be instantiated and called as such: * KthLargest obj = new KthLargest(k, nums); * int param_1 = obj.add(val); */
提交结果：
三、（简单题）1337. 矩阵中战斗力最弱的 K 行
原题链接：矩阵中战斗力最弱的 K 行
题目描述：
给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
/
示例 1：
输入：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
输出：[2,0,3]
解释：
每行中的军人数目：
行 0 -> 2
行 1 -> 4
行 2 -> 1
行 3 -> 2
行 4 -> 5
从最弱到最强对这些行排序后得到 [2,0,3,1,4]
/
示例 2：
输入：mat =
[[1,0,0,0],
[1,1,1,1],
[1,0,0,0],
[1,0,0,0]],
k = 2
输出：[0,2]
解释：
每行中的军人数目：
行 0 -> 1
行 1 -> 4
行 2 -> 1
行 3 -> 1
从最弱到最强对这些行排序后得到 [0,2,3,1]
解题思路：
题目要求给队伍的实力由弱到强排位，军人数量越多越强，军人数量一致时，队伍下标的大小越大越强。
那么我们就可以用一个长度为2的一维数组来存放每一条队伍：
int[]{val，index}
val 代表队伍中军人的总数；
index 代表队伍的行数大小；
将每条队伍的数据放入最小堆中排序，int[0]小的优先，若军人数相同时，int[1]小的优先。
最后再分别取出堆顶元素储存，便为队伍按由弱到强的顺序排好了。
解题代码：
class Solution { public int[] kWeakestRows(int[][] mat, int k) { //创建优先队列，默认为最小堆 //堆中的节点元素为数组int[]{val,index}， //1.val代表军人数量，2.index代表第index行 //最小堆排序规则是先对比军人数量，若相同再对比行数index的大小，小的优先 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]; } }); //用来记录每一行的军人数量 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});//将int[]{军人数，第index行}放入最小堆排序 } int[] sort = new int[k]; for(int i = 0;i < k;++i){ sort[i] = que.poll()[1];//取出堆顶的最弱的第index行队伍 } return sort;//输出队伍排行 } }
提交结果：
贵在坚持： ✨关注作者，与作者一同进步…
