专门做游戏攻略的网站,公司集团网站设计,营销型企业网站怎么制作,常德建设网站第一题
515. 在每个树行中找最大值 首先是遍历每层的节点#xff0c;将每一层最大值的节点的值保留下来#xff0c;最后将所有层的最大值的表返回#xff1b;具体的遍历每层节点的过程如上一篇故事#xff1b; 综上所述#xff0c;代码如下#xff1a; /*** Definition …第一题
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 ListInteger largestValues(TreeNode root) {ListInteger ret new ArrayList();if(root null) return ret;QueueTreeNode q new LinkedList();q.add(root);while(!q.isEmpty()){int size q.size();int tmp Integer.MIN_VALUE;for(int i 0;isize;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、创建一个大根堆PriorityQueueInteger 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 {PriorityQueueInteger 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 ListString topKFrequent(String[] words, int k) {//1、统计一下每一个单词出现的次数MapString,Integer hash new HashMap();for(String s: words){hash.put(s,hash.getOrDefault(s,0)1);}//2、创建一个大小为k的堆PriorityQueuePairString,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.EntryString,Integer e : hash.entrySet()){heap.offer(new Pair(e.getKey(),e.getValue()));if(heap.size() k){heap.poll();}}//4、提取结果ListString ret new ArrayList();while(!heap.isEmpty()){ret.add(heap.poll().getKey());}//逆序数组Collections.reverse(ret);return ret;}
} ps本次的内容就到这里了如果对你有所帮助的话就请一键三连哦
