目录
力扣.662.二叉树最大高度
力扣515.在每个数行中找最大值
力扣703.数据流中第k大元素
力扣692.前k个高频词
力扣.662.二叉树最大高度
首先记录一下我的错误想法，其实也挺对的
看到这个图，感觉其实就是找两个端点[左，null,null,右]中间可以有一堆空，我是想着，把一堆空给他初始化一个节点，给他插入进队列里面，他的节点数值【100，-100】我直接-101，然后一层给他放一个List<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) {Deque<TreeNode>q=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.val*2);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<Pair<TreeNode,Integer>>q=new ArrayList<>();q.add(new Pair<TreeNode,Integer>(root,1));int ret=0;//列表while(!q.isEmpty()){//先更新一下这一层的宽度,获取头部Pair<TreeNode,Integer>t1=q.get(0);//获取尾巴Pair<TreeNode,Integer>t2=q.get(q.size()-1);//更新这一层ret=Math.max(t2.getValue()-t1.getValue()+1,ret);
//下一层进入队列，唯一难度就是怎么让q进行插入，使用tmp存储，然后最后用tmp覆盖掉即可List<Pair<TreeNode,Integer>>tmp=new ArrayList<>();for(Pair<TreeNode,Integer>t:q){TreeNode node=t.getKey();int index=t.getValue();if(node.left!=null){tmp.add(new Pair<TreeNode,Integer>(node.left,index*2));}if(node.right!=null){tmp.add(new Pair<TreeNode,Integer>(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<Integer> largestValues(TreeNode root) {Queue<TreeNode>q=new LinkedList<>();q.add(root);List<Integer>ret=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 <Integer>q=new PriorityQueue<>();public int kk;public KthLargest(int k, int[] nums) {kk=k;if(k<=nums.length){//找第4大的，1，2，3，4，5for(int i=0;i<k;i++){q.add(nums[i]);}for(int i=k;i<nums.length;i++){if(q.peek()<nums[i]){q.poll();q.add(nums[i]);}}}else if(k>nums.length){//假如来个999大的，1，2，3，后面慢慢添加for(int i=0;i<nums.length;i++) q.add(nums[i]);}}public int add(int val) {if(q.size()<kk) {q.add(val);return q.peek();}if(q.peek()<val){q.poll();q.add(val); }return q.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个高频词
你提供的代码是一个自定义的 `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<String> topKFrequent(String[] words, int k) {//考虑，堆+哈希HashMap<String,Integer>map=new HashMap<>();PriorityQueue<String>q=new PriorityQueue<>();for(int i=0;i<words.length;i++){//记录每个单词的次数map.put(words[i],map.getOrDefault(words[i],0)+1);}List<String>ret=new LinkedList<>();//这里是遍历哈希表，全部放入链表中
使用哈希表的遍历,entrySet它用于返回映射中包含的键值对的Set视图。这个方法非常有用，因为它允许开发者遍历Map中的所有键值对。
//Map.Entry<String,Integer>就是一个相当于方便遍历的东西for(Map.Entry<String,Integer>entry:map.entrySet()){ret.add(entry.getKey());}//他的排序是排序数组，然后根据哈希表来排序Collections.sort(ret, new Comparator<String>() {@Overridepublic 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<String> topKFrequent(String[] words, int k) {//考虑，堆+哈希HashMap<String,Integer>map=new HashMap<>();//由大到小的排序for(int i=0;i<words.length;i++){//记录每个单词的次数map.put(words[i],map.getOrDefault(words[i],0)+1);}PriorityQueue<String>q=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<String,Integer> entry:map.entrySet()){if(q.size()<k){//但是map怎么让他有序呢，他肯定是先根据顺序来q.add(entry.getKey());}else {if(map.get(q.peek())<map.get(entry.getKey())||//两个次数一样，判断字母(map.get(q.peek())==map.get(entry.getKey())&&entry.getKey().compareTo(q.peek())<0)){q.poll();q.add(entry.getKey());}}}List<String>ret=new LinkedList<>();Stack<String> a=new Stack<>();while (!q.isEmpty()){a.add(q.poll());}while (!a.isEmpty()){ret.add(a.pop());}return ret;}} class Solution {public static List<String> topKFrequent(String[] words, int k) {//考虑，堆+哈希HashMap<String,Integer>map=new HashMap<>();//由大到小的排序for(int i=0;i<words.length;i++){//记录每个单词的次数map.put(words[i],map.getOrDefault(words[i],0)+1);}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();});//字典序保证之后，我们只需要负责插入即可,插入该怎么处理？肯定是前面我先随便插入for(Map.Entry<String,Integer> entry:map.entrySet()){heap.offer(new Pair<>(entry.getKey(),entry.getValue()));if(heap.size()>k){heap.poll();}}
//提取结果List<String>ret=new LinkedList<>();Stack<String> a=new Stack<>();while (!heap.isEmpty()){a.add(heap.poll().getKey());}while (!a.isEmpty()){ret.add(a.pop());}return ret;}
}