赞
踩
首先是遍历每层的节点,将每一层最大值的节点的值保留下来,最后将所有层的最大值的表返回;具体的遍历每层节点的过程如上一篇故事;
综上所述,代码如下:
/** * 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; } }
实例分析:
我们采用堆的解题方法;
创建一个大根堆,把所有的元素放入到大根堆里面;
每次返回堆顶的两个元素,得到两个数的差值在进入到大根堆里面;
最后只要大根堆的里面有元素就一直重复出堆相减的操作;
返回最后的数值即可;
综上所述,代码如下:
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(); } }
本题是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); */
解法:本题利用堆来解决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; } }
ps:本次的内容就到这里了,如果对你有所帮助的话就请一键三连哦!!!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。