第六感聊城网站建设梅林网站建设

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

第六感聊城网站建设,梅林网站建设,高端网站设计公司新鸿儒,wordpress主题页脚如何修改347. 前 K 个高频元素 答案 思路#xff1a; 1、首先#xff0c;用到了每个值对应的出现次数#xff0c;想到要用哈希map存放 2、还需要将出现频率从大到小进行排序#xff0c;找出前k个元素 3、时间复杂度应该比O#xff08;nlogn#xff09;小 如果想用快速排序 1、首先用到了每个值对应的出现次数想到要用哈希map存放 2、还需要将出现频率从大到小进行排序找出前k个元素 3、时间复杂度应该比Onlogn小 如果想用快速排序是达不到最后一个要求的 通过从大到小排序很可能会想到用大顶堆但是由于大顶堆是每次都把频率最大的那个元素放在堆顶上而如果达到了k个就会把当前的最大元素弹出这对于寻找所有元素中频率最大的k个元素并不方便 所以考虑小顶堆 1、小顶堆可以在堆达到k个元素后每次弹出当前最小的元素这样最后剩下的k个元素就是我们要找的 2、在当堆元素达到k个后进行判断 如果当前的堆顶元素的出现次数比当前的元素的次数小就舍弃堆顶元素并把当前遍历的元素加入堆中 如果当前的堆顶元素的出现次数比当前遍历的元素的出现次数大说明当前堆中的所有元素的出现次数都比当前遍历的元素的出现次数大则舍弃当前遍历的元素。 用到的知识点 优先级队列PriorityQueue 我们知道队列是遵循先进先出First-In-First-Out模式的但有些时候需要在队列中基于优先级处理对象。 在概念上默认为小顶堆 1、在Java1.5中引入并作为 Java Collections Framework 的一部分 2、基于优先堆的一个无界队列这个优先队列中的元素可以默认自然排序或者通过提供的Comparator比较器在队列实例化的时排序。不指定Comparator时默认为最小堆优先队列的头是基于自然排序或者Comparator排序的最小元素。堆排序只能保证根是最大最小整个堆并不是有序的 3、优先队列不允许空值 4、优先队列不允许空值 5、PriorityQueue是非线程安全的所以Java提供了PriorityBlockingQueue实现BlockingQueue接口用于Java多线程环境 6、优先队列的大小是不受限制的但在创建时可以指定初始大小。当我们向优先队列增加元素的时候队列大小会自动增加 常用方法
Map 1、HashMap、LinkedHashMap和Hashtable是Map的两个常用实现类 HashMap特点 HashMap是无序的集合存储元素和取出元素的顺序有可能不一致集合是不同步的也就是说是多线程的速度快 LinkedHashMap特点 LinkedHashMap是一个有序的集合存储元素和取出元素的顺序一致 2、常用方法 put——添加元素 putall——向map添加指定的集合 containsKey——判断是否包含指定的key containsValue——判断是否包含指定的值 get——获取指定key对应的value remove——删除指定的key对应的元素 size——获取元素个数 getOrDefault getOrDefault(Object key, V defaultValue) 意思就是当Map集合中有这个key时就使用这个key对应的value值如果没有就使用默认值defaultValue Entry Map.Entry是Map声明的一个内部接口此接口为泛型定义为EntryK,V。它表示Map中的一个实体一个key-value对。接口中有getKey(),getValue方法。 Map遍历的方法 for循环中遍历value MapString, String map new HashMap();map.put(开发, 开发);map.put(测试, 测试);for (Object value : map.values()) {System.out.println(第一种: value);}通过key遍历 for (String key: map.keySet()) {System.out.println(第二种: map.get(key));}通过entrySet实现遍历 SetMap.EntryString, String entrySet map.entrySet();for (Map.Entry entry : entrySet) {System.out.println(第三种: entry.getKey() entry.getValue());}通过Iterator迭代器实现遍历 IteratorMap.EntryString, String entryIterator map.entrySet().iterator();while (entryIterator.hasNext()) {Map.EntryString, String entry entryIterator.next();System.out.println(第四种: entry.getKey() entry.getValue());}通过lambda表达式进行遍历 map.forEach((key, value) - {System.out.println(第五种: key value);});代码 class Solution {public int[] topKFrequent(int[] nums, int k) {MapInteger,Integer mapnew HashMap();for(int num:nums){map.put(num,map.getOrDefault(num,0)1);//}PriorityQueueint[] queuenew PriorityQueue(new Comparatorint{//comparatorpublic int compare(int[] m,int[] n){return m[1]-n[1];}});for(Map.EntryInteger,Integer entry:map.entrySet()){//int numentry.getKey();int valueentry.getValue();if(queue.size()k){if(queue.peek()[1]value){queue.poll();queue.offer(new int[]{num,value});//}}else{queue.offer(new int[]{num,value});}}int[] resnew int[k];for(int i0;ik;i){res[i]queue.poll()[0];//}return res;} }注意 1、接口的书写Comparator 2、方法名不大写compare 3、再重写方法时new Comparatorint[ ]不能省略int[ ] 4、PriorityQueue的添加方法是offer 5、push和pop是栈中常用的方法 栈中常用方法push、pop、peek、isEmpty 队列常用方法offer、poll、peek、isEmpty 二叉树的基本知识 Java定义 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;} }完全二叉树 完全二叉树的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。
二叉搜索树 前面介绍的树都没有数值的而二叉搜索树是有数值的了二叉搜索树是一个有序树。 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 它的左、右子树也分别为二叉排序树 下面这两棵树都是搜索树
平衡二叉搜索树 平衡二叉搜索树又被称为AVLAdelson-Velsky and Landis树且具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。 如图
遍历方式 存储方式 二叉树可以链式存储也可以顺序存储 关于二叉树遍历的题目使用递归——144、145、94 144 class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new LinkedListInteger();preorder(root, result);return result;}public void preorder(TreeNode root, ListInteger result) {if (root null) {//这里判断的是节点是否为null不是结点的值return;}result.add(root.val);//别忘了加preorder(root.left, result);preorder(root.right, result);} }145 class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger resnew LinkedList();traversal(root,res);return res;}public void traversal(TreeNode root,List res){if(rootnull){return;}traversal(root.left,res);traversal(root.right,res);res.add(root.val);} }94 class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger resnew LinkedList();traversal(root,res);return res;}public void traversal(TreeNode root,List res){if(rootnull){return;}traversal(root.left,res);res.add(root.val);traversal(root.right,res);} }关于List的用法 1、 添加方法是.add(e)　　 获取方法是.get(index)　　 删除方法是.remove(index) 按照索引删除　　.remove(Object o) 按照元素内容删除 2、 否包含某个元素.containsObject o 返回true或者false 3、 根据索引将元素数值改变(替换) .set(index, element); set是将替换该索引位置的值 .add(index, element); add是在该索引位置插入一个值 4、 .indexOf 第一个该值的索引 lastIndexOf的不同最后一个该值的索引 5、 判断list是否为空.isEmpty(); 空则返回true非空则返回false