【day04】力扣（LeetCode）每日一刷[1306. 跳跃游戏 III ][703. 数据流中的第 K 大元素 ][1337. 矩阵中战斗力最弱的 K 行]

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]);
    }
}

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);
 */

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;//输出队伍排行

    }
}