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