当前位置：首页 > news >正文

算法day27

news 2025/8/8 18:32:40

第一题

515. 在每个树行中找最大值

首先是遍历每层的节点，将每一层最大值的节点的值保留下来，最后将所有层的最大值的表返回；具体的遍历每层节点的过程如上一篇故事；

综上所述，代码如下：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root== null) return ret;Queue<TreeNode> q = new LinkedList<>();q.add(root);while(!q.isEmpty()){int size = q.size();int tmp = Integer.MIN_VALUE;for(int i = 0;i<size;i++){TreeNode t = q.poll();tmp = Math.max(tmp,t.val);if(t.left != null)q.add(t.left);if(t.right != null) q.add(t.right);}ret.add(tmp);}return ret;}
}

第二题

1046. 最后一块石头的重量

实例分析：

我们采用堆的解题方法；

创建一个大根堆，把所有的元素放入到大根堆里面；

每次返回堆顶的两个元素，得到两个数的差值在进入到大根堆里面；

最后只要大根堆的里面有元素就一直重复出堆相减的操作；

返回最后的数值即可；

综上所述，代码如下：
class Solution {public int lastStoneWeight(int[] stones) {//1、创建一个大根堆PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> b-a);//2、把所有的石头放进堆里里面for(int x :stones){heap.offer(x);}//3、模拟while(heap.size()>1){int a = heap.poll();int b = heap.poll();if(a > b ){heap.offer(a-b);}}return heap.isEmpty()?0:heap.peek();}
}

第三题

703. 数据流中的第 K 大元素

本题是top-k模型，解题思路如下所示：

创建一个长度为k的小根堆，然后开始往里面加入元素，一直等加入元素后小根堆的长度大于k值时，我们进行出堆操作，即将小根堆顶部的元素退出去，在进行入堆操作，就这样一直重复操作，直到所有的元素都进行过入堆操作，这时候返回的堆顶的元素即是我们所求；

综上所述，代码如下：
class KthLargest {PriorityQueue<Integer> heap;int k1;public KthLargest(int k, int[] nums) {k1 = k;heap = new PriorityQueue<>();for(int x : nums){heap.offer(x);if(heap.size() > k1){heap.poll();}}}public int add(int val) {heap.offer(val);if(heap.size() > k1){heap.poll();}return heap.peek();}
}/*** Your KthLargest object will be instantiated and called as such:* KthLargest obj = new KthLargest(k, nums);* int param_1 = obj.add(val);*/

第四题

692. 前K个高频单词

解法：本题利用堆来解决top-k问题；

步骤：

步骤一：

预处理一下原始的字符串数组，即用一个hash表统计一下每一个单词出现的频次；

步骤二：

创建一个大小为k的堆：

频次不同：小根堆

频次相同时创建大根堆（字典序）

步骤三：

开始循环操作：

让元素依次进堆，判断条件，如果不满足条件的话就进行堆顶的元素出堆操作

步骤四：

根据实际情况对元素进行逆序操作

综上所述，代码如下：
class Solution {public List<String> topKFrequent(String[] words, int k) {//1、统计一下每一个单词出现的次数Map<String,Integer> hash = new HashMap<>();for(String s: words){hash.put(s,hash.getOrDefault(s,0)+1);}//2、创建一个大小为k的堆PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>((a,b) -> {if(a.getValue().equals(b.getValue()))//出现频次相同的时候，字典按照大根堆的顺序排列{return b.getKey().compareTo(a.getKey());}return a.getValue() - b.getValue();});//3、top-k的主逻辑for(Map.Entry<String,Integer> e : hash.entrySet()){heap.offer(new Pair<>(e.getKey(),e.getValue()));if(heap.size() > k){heap.poll();}}//4、提取结果List<String> ret = new ArrayList<>();while(!heap.isEmpty()){ret.add(heap.poll().getKey());}//逆序数组Collections.reverse(ret);return ret;}
}