LeetCode 二叉树 堆(优先级队列) 相关题目

LeetCode 二叉树 堆(优先级队列) 相关题目

文章目录

• LeeCode刷题笔记
• • 第一题:左叶子之和
  • • 解题思路:
    • 画图解析:
    • 代码实现:
  • 第二题:数组中的第K个最大元素
  • • 解题思路:
    • 代码实现:
  • 第三题:滑动窗口最大值
  • • 解题思路:
    • 画图解析:

LeeCode刷题笔记 第一题:左叶子之和

404. 左叶子之和4

描述:
计算给定二叉树的所有左叶子之和。

解题思路:

1. 情况1: root为空 直接返回0;
2. 情况2: 左子树只有一个节点,即左叶子节点,然后去遍历右子树找右子树的左叶子.
3. 情况3: 左子树需遍历到左叶子,右子树需要遍历到左叶子.

画图解析:

代码实现:

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        // root 为空 直接返回0
        if(root == null) return 0;
        // 左子树为左叶子 递归去找右子树的左叶子
        if(root.left != null && root.left.left == null && root.left.right == null){
            return root.left.val + sumOfLeftLeaves(root.right);
        }
        // 左子树不为左叶子,分别找左右子树的左叶子
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}

第二题:数组中的第K个最大元素

LeetCode 215:数组中的第K个最大元素
描述:
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

解题思路:

1. 使用优先级队列解题,即建一个大小为k的小堆.
2. 遍历数组.将堆放满
3. 堆放满后,每次需要和堆顶元素比较,如果堆顶元素比数组元素下,则出队,然后将数组元素入队.
4. 最后返回队顶元素即可.

代码实现:

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue MinHeap = new PriorityQueue<>(k,new Comparator(){
            public int compare(Integer o1,Integer o2){
                return o1 - o2;
            }
        }); //建小堆
        for(int i = 0;i < nums.length ;i++){
            //堆没满,先入队
            if(MinHeap.size() < k){
                MinHeap.offer(nums[i]);
            }else{
            	//堆满后,进行比较,堆顶元素小于数组元素,就将数组元素入队
                if(MinHeap.peek() < nums[i]){
                    MinHeap.poll();
                    MinHeap.offer(nums[i]);
                }
            }
        }
        //返回堆顶元素即可.
        return MinHeap.peek();
    }
}

第三题:滑动窗口最大值

LeetCode 239: 滑动窗口最大值
描述:
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

解题思路:

1. 可以使用优先级队列,建立大堆.存储的是nums数组的内容,和对应的下标
2. 创建一个数组,大小为 nums.length - k + 1 ,用来存储每次滑动窗口获得的最大值.
3. 遍历nums数组,首先存放k个数据存入到堆中,这样构成一个大小为k的滑动窗口,然后将第一次滑动窗口中的最大数据放入数组中(即堆顶元素).
4. 然后在堆满后,继续进行遍历,插入新遍历到的数据,然后循环判断队顶元素是否满足滑动窗口的下标,方法是使用下标比较, 队顶元素下标 <= i - k. ,根据此条件循环判断是否需要出队,循环结束后,表示堆顶元素是在滑动窗口内就将堆顶元素存入数组中.
5. 遍历结束后,直接返回数组.

画图解析:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue MaxHeap = new PriorityQueue<>(k,new Comparator(){
            public int compare(int[] arr1,int[] arr2){
                return arr1[0] != arr2[0] ? arr2[0]-arr1[0]:arr2[1]-arr1[1];
            }
        });//建立大堆,存入的是nums数组的数据和对应的下标
		
		//建立一个大小为nums.length-k+1的数组 用来存得到的数据
        int[] arr = new int[nums.length - k + 1];
        int index=0;//index表示存数据的下标
        for (int i = 0; i < nums.length; i++) {
            //这一步是构建一个大小为k的滑动窗口
            if(MaxHeap.size() < k){
                MaxHeap.offer(new int[]{nums[i],i});
                if(MaxHeap.size() == k){
                	// 堆大小 = k时,表示滑动窗口创建好了,将得到的数据存入arr数组中
                    arr[index++] = MaxHeap.peek()[0];
                }
            }else{
            	//直接将数据入队
                MaxHeap.offer(new int[]{nums[i],i});
                //判断堆顶元素是否在滑动窗口内,如果不在要出队.
                while(MaxHeap.peek()[1] <= i - k){
                    MaxHeap.poll();
                }
                //走到这里表示堆顶元素符合条件,直接存入数组中
                arr[index++] = MaxHeap.peek()[0];
            }
        }
       	//遍历结束直接返回arr即可.
        return arr;
    }
}