队列+宽度优先搜索，力扣.662.二叉树最大高度 力扣515.在每个数行中找最大值力扣703.数据流中第k大元素力扣692.前k个高频词

力扣.662.二叉树最大高度

首先记录一下我的错误想法，其实也挺对的

看到这个图，感觉其实就是找两个端点[左，null,null,右]中间可以有一堆空，我是想着，把一堆空给他初始化一个节点，给他插入进队列里面，他的节点数值【100，-100】我直接-101，然后一层给他放一个List

里面，然后遍历一个begin,一个end找最小和最大，一个减法就好，也能过大部分例子，72-116，心痛

这个最后估计没准树高1500，那就要2的1500次幂

解法二:使用数组存储二叉树的方式，给定节点编号

思路肯定对，但是这个刹弊题目给的数据怪，怪的同时吧，你越界，两个越界相减还是对的，但是你假如取最小值，和最大值的话，就会在越界的时候，把那个相减的对的给去除

/**

• 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 static int widthOfBinaryTree(TreeNode root) { Dequeq=new LinkedList<>(); root.val=1; q.add(root); int count=0; while(!q.isEmpty()){ int sz=q.size(); //记录起点的同时记录有多少个 //每个都是从0开始编号 int begin=Integer.MAX_VALUE; int end=-1; int t=sz; while(sz!=0){ TreeNode root1=q.poll(); //考虑一下，最左边的是不是一定最小，最右边的是不是一定最大呢？ if(t==sz) begin=Math.min(root1.val,begin); if(sz==1) end=Math.max(end,root1.val); if(root1.left!=null) { root1.left.val=(root1.val2); q.add(root1.left); } if(root1.right!=null) { root1.right.val=(root1.val*2+1); q.add(root1.right); } t++; sz–; } count=Math.max(count,(end-begin+1)); } //此时已经遍历整体之后，我应该取出来每一个

return count; } } 最终正解，就是题数据恶心 /**

• 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 static int widthOfBinaryTree(TreeNode root) { //使用数组模拟队列，出队列，头删一个元素麻烦，所以利用一个新的覆盖就可以啦 List>q=new ArrayList<>(); q.add(new Pair(root,1)); int ret=0; //列表 while(!q.isEmpty()){ //先更新一下这一层的宽度,获取头部 Pairt1=q.get(0); //获取尾巴 Pairt2=q.get(q.size()-1); //更新这一层 ret=Math.max(t2.getValue()-t1.getValue()+1,ret); //下一层进入队列，唯一难度就是怎么让q进行插入，使用tmp存储，然后最后用tmp覆盖掉即可 List>tmp=new ArrayList<>(); for(Pairt:q){ TreeNode node=t.getKey(); int index=t.getValue(); if(node.left!=null){ tmp.add(new Pair(node.left,index2)); } if(node.right!=null){ tmp.add(new Pair(node.right,index*2+1)); } } q=tmp; } return ret; } }

力扣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 largestValues(TreeNode root) { Queueq=new LinkedList<>(); q.add(root); Listret=new LinkedList<>(); if(root==null) return ret; while(!q.isEmpty()){ int sz=q.size(); int max=Integer.MIN_VALUE; while(sz!=0){ TreeNode t=q.poll(); max=Math.max(max,t.val); if(t.left!=null) q.add(t.left); if(t.right!=null) q.add(t.right); sz–; } ret.add(max); } return ret; } }

力扣703.数据流中第k大元素

数据十分友好，我觉得他没有搞很多什么构造函数的，恶心你，蛮不错了已经。

题目中大第k大元素和k个不同元素的意思是，2，2 3，3 ，1 第三大的应该是2，不是1 class KthLargest { PriorityQueue q=new PriorityQueue<>(); public int kk; public KthLargest(int k, int[] nums) { kk=k; if(k<=nums.length){ //找第4大的，1，2，3，4，5 for(int i=0;inums.length){ //假如来个999大的，1，2，3，后面慢慢添加 for(int i=0;i 你提供的代码是一个自定义的 Comparator，用于对字符串列表 ret 进行排序。这个 Comparator 的逻辑如下：

1 首先检查两个字符串在 map 中对应的值是否相等。 2 如果相等，则按字母顺序（自然顺序）比较这两个字符串。 3 如果不相等，则按照 map 中对应的值进行降序排序。

这是一个有效的 Comparator 实现，适用于对包含字符串的列表进行排序，特别是当你希望根据字符串在 map 中的值和它们自身的字母顺序进行排序时。

这里是你提供的代码的一个完整示例，包括创建 map 和 ret 列表，以及使用自定义 Comparator 对 ret 进行排序：

- map: 存储了每个字符串及其对应的整数值。 - ret: 是一个包含字符串的列表，我们将对这个列表进行排序。 - Collections.sort: 使用自定义的 Comparator 对 ret 列表进行排序。 - Comparator: - 如果 map.get(word1) 和 map.get(word2) 相等，则按字母顺序 (word1.compareTo(word2)) 排序。 - 否则，按 map 中的值进行降序排序 (map.get(word2) - map.get(word1))。

[apple, banana, cherry, date] 解释： - "apple" 的值为 3，最大。 - "banana" 和 "cherry" 的值都为 2，但 "banana" 在字母顺序上排在 "cherry" 之前。 - "date" 的值为 1，最小。 哈希表+排序 class Solution { public static List topKFrequent(String[] words, int k) { //考虑，堆+哈希 HashMapmap=new HashMap<>(); PriorityQueueq=new PriorityQueue<>(); for(int i=0;iret=new LinkedList<>(); //这里是遍历哈希表，全部放入链表中 使用哈希表的遍历,entrySet它用于返回映射中包含的键值对的Set视图。这个方法非常有用，因为它允许开发者遍历Map中的所有键值对。 //Map.Entry就是一个相当于方便遍历的东西 for(Map.Entryentry:map.entrySet()){ ret.add(entry.getKey()); } //他的排序是排序数组，然后根据哈希表来排序 Collections.sort(ret, new Comparator() { @Override public int compare(String word1, String word2) { //假如两个个数一样，就去比较字母顺序 return map.get(word1)==map.get(word2)? word1.compareTo(word2):map.get(word2)-map.get(word1); } }); //map里面存储了很多东西 return ret.subList(0,k); } } class Solution { public static List topKFrequent(String[] words, int k) { //考虑，堆+哈希 HashMapmap=new HashMap<>(); //由大到小的排序 for(int i=0;iq=new PriorityQueue<>((String a,String b)->{//频次相同时候，字典序按照大根堆的方式排列 return map.get(a)==map.get(b)?b.compareTo(a):map.get(a)-map.get(b); }); //字典序保证之后，我们只需要负责插入即可,插入该怎么处理？肯定是前面我先随便插入 for(Map.Entry entry:map.entrySet()){ if(q.size()ret=new LinkedList<>(); Stack a=new Stack<>(); while (!q.isEmpty()){ a.add(q.poll()); } while (!a.isEmpty()){ ret.add(a.pop()); } return ret; } } class Solution { public static List topKFrequent(String[] words, int k) { //考虑，堆+哈希 HashMapmap=new HashMap<>(); //由大到小的排序 for(int i=0;i>heap=new PriorityQueue<> ((a, b)->{//频次相同时候，字典序按照大根堆的方式排列 if(a.getValue().equals(b.getValue())){ //大根堆估计就是相反次序，我总是记不清，所以实验一下会更好 return b.getKey().compareTo(a.getKey()); } return a.getValue()-b.getValue(); }); //字典序保证之后，我们只需要负责插入即可,插入该怎么处理？肯定是前面我先随便插入 for(Map.Entry entry:map.entrySet()){ heap.offer(new Pair<>(entry.getKey(),entry.getValue())); if(heap.size()>k){ heap.poll(); } } //提取结果 Listret=new LinkedList<>(); Stack a=new Stack<>(); while (!heap.isEmpty()){ a.add(heap.poll().getKey()); } while (!a.isEmpty()){ ret.add(a.pop()); } return ret; } }