描述:
计算给定二叉树的所有左叶子之和。
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);
}
}
LeetCode 215:数组中的第K个最大元素
描述:
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
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 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
nums.length - k + 1
,用来存储每次滑动窗口获得的最大值.队顶元素下标 <= i - k.
,根据此条件循环判断是否需要出队,循环结束后,表示堆顶元素是在滑动窗口内就将堆顶元素存入数组中.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;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/wwzzzzzzzzzzzzz/article/details/122242025
内容来源于网络,如有侵权,请联系作者删除!