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