站义 拨开荷叶行,寻梦已然成。仙女莲花里,翩翩白鹭情。
IMG-LOGO
主页 文章列表 LeetCode 二叉树 堆(优先级队列) 相关题目

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

by 白鹭 - 2022-03-03 1820 0 0

文章目录

  • LeeCode刷题笔记
    • 第一题:左叶子之和
      • 解题思路:
      • 画图决议:
      • 代码实作:
    • 第二题:阵列中的第K个最大元素
      • 解题思路:
      • 代码实作:
    • 第三题:滑动视窗最大值
      • 解题思路:
      • 画图决议:

LeeCode刷题笔记

第一题:左叶子之和

  1. 左叶子之和4

描述:
计算给定二叉树的所有左叶子之和,
在这里插入图片描述

解题思路:

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

画图决议:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nzMTWBYK-1640856644467)(C:\Users\王志\AppData\Roaming\Typora\typora-user-images\image-20211228201407100.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JmpGpZt5-1640856644468)(C:\Users\王志\AppData\Roaming\Typora\typora-user-images\image-20211228201600922.png)]

代码实作:

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<Integer> MinHeap = new PriorityQueue<>(k,new Comparator<Integer>(){
            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<int[]> MaxHeap = new PriorityQueue<>(k,new Comparator<int[]>(){
            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;
    }
}
一起学习
标签:

0 评论

发表评论

您的电子邮件地址不会被公开。 必填的字段已做标记 *