current position:Home>Day04[1306. Jumping Game III][703. Kth Largest Element in Data Stream][1337. Kth Weakest Combat Row in Matrix]

Day04[1306. Jumping Game III][703. Kth Largest Element in Data Stream][1337. Kth Weakest Combat Row in Matrix]

2022-11-24 22:38:17Huawei Cloud

一、(中等题)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;//输出队伍排行    }}

提交结果:

在这里插入图片描述

copyright notice
author[Huawei Cloud],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/328/202211242226519928.html

Random recommended