本地建设网站,wordpress官网主题,WordPress文件删除漏洞,全国职业生涯规划大赛官网#x1f341;1. Set系列集合
Set接口是一种不包含重复元素的集合。它继承自Collection接口#xff0c;所以可以使用Collection所拥有的方法#xff0c;Set接口的实现类主要有HashSet、LinkedHashSet、TreeSet等#xff0c;它们各自以不同的方式存储元素#xff0c;但都遵… 1. Set系列集合
Set接口是一种不包含重复元素的集合。它继承自Collection接口所以可以使用Collection所拥有的方法Set接口的实现类主要有HashSet、LinkedHashSet、TreeSet等它们各自以不同的方式存储元素但都遵循Set接口的规定。 当你需要确保集合中的元素唯一时。当你不需要保持元素的插入顺序时除非使用LinkedHashSet。当你需要元素自然排序或根据自定义排序规则排序时使用TreeSet。 1.1 HashSet
当用HashSet实例化对象时由于底层结构是哈希表所以元素是无序的而TreeSet底层是红黑树是有序的 由于Set系列集合里面不能有重复的元素在之前我们也了解到add方法的返回值是boolean类型的当遇到重复元素第二次添加就会添加失败 并且Set集合没有索引的概念不能通过下标的方式进行遍历打印 和之前一样没有索引的集合可以通过迭代器增强forlambda表达式进行遍历 IteratorString it s1.iterator();while (it.hasNext()){System.out.print(it.next() );}System.out.println();for(String s : s1){System.out.print(s );}System.out.println();s1.forEach(new ConsumerString() {Overridepublic void accept(String s) {System.out.print(s );}}); 1.2 LinkedHashSet LinkedHashSet底层也是哈希表但是存取元素的顺序是一致的因为使用了双向链表记录添加顺序 1.3 TreeSet
TreeSet是基于红黑树实现的TreeSet中的元素处于排序状态因此查找、添加、删除和遍历等操作都能以对数时间复杂度进行。但是向TreeSet中添加的元素必须实现Comparable接口或者在创建TreeSet时提供一个Comparator对象以确保元素可以被正确地排序。 排序规则Integer,Double等数值类型默认按照从小到大的顺序排序对于字符字符串类型按照ASCII码表中的数字进行升排序 接下来演示一下创建自定义类型的TreeSet
例如给出一个Student类要求按照学生的年龄排序
首先创建好Student类之后需要实现Comparable接口然后重写compareTo和toString方法
public class Student implements ComparableStudent{public String name;public int age;public Student(String name, int age) {this.name name;this.age age;}Overridepublic String toString() {return Student{ name name \ , age age };}Overridepublic int compareTo(Student o) {return this.age - o.age;//this.age表示要添加的元素}
} this.age表示要添加的元素所以如果返回值是负数表示要添加的元素是小的存左边如果是0表示元素已经存在直接舍弃
public class Text2 {public static void main(String[] args) {Student s1 new Student(zhang,18);Student s2 new Student(wang,20);Student s3 new Student(li,19);TreeSetStudent treeSet new TreeSet();treeSet.add(s1);treeSet.add(s2);treeSet.add(s3);System.out.println(treeSet);}
} 最终虽然插入时没有按顺序由于TreeSet底层是红黑树所以最终也实现了排序的效果 比较器排序
问题根据字符串长度比较长度相同再按字典序比较 //o1:当前要添加的元素//o2:红黑树中已经存在的元素TreeSetString ts new TreeSet(new ComparatorString() {Overridepublic int compare(String o1, String o2) {return (o1.length() - o2.length()) 0 ? o1.compareTo(o2) : o1.length() - o2.length();}});ts.add(bbcd);ts.add(abcde);ts.add(abcd);System.out.println(ts);
也就是在创建对象的时候传入比较器进行比较 2. 单列集合的使用场景分析
介绍完Set系列集合之后我们的单列集合就都学习完了接下来分析一下这写集合的使用场景 如果集合中元素可重复使用ArrayList基于数组 如果集合中元素可重复并且用到增删操作多余查询:使用LinkedList 如果需要对集合去重使用HashSet 如果需要在去重的前提下还要保证存取顺序使用LinkedHashSet 如果需要对集合中的元素进行排序使用TreeSet 3. Map系列集合
Map系列的集合称为双列集合 1. 双列集合一次存储一对数据分别为键和值 2. 键不能重复值可以重复 3. 键和值是一一对应的每一个键都对应一个值 4. 键值整体称为键值对也叫Entry对象 和Set集合类似Map是顶层接口底下有这些实现类 以下就是Map集合常用的API 3.1 HashMap
HashMap的底层也是哈希表和之前的HashSet不同HashMap中当插入的key相同时第二次插入会覆盖原来的value值同时如果存储的是自定义类型的对象还需要重写HashCode和equals方法
其他方法就不演示了下面来介绍一下map的遍历
Map的遍历
键找值调用keySet方法获取所有的key把返回值放在Set集合中再遍历Set集合通过get方法获取每一个key的value //获取所有的键并放在Set集合中SetString set map.keySet();//遍历set,根据所有的键获取值for(String key:set){int value map.get(key);System.out.println(key value);}
通过键值对对象进行遍历
调用entrySet方法把所有键值对对象放在Set集合中再遍历Set集合 可以看出Entry是Map接口的一个内部接口所以需要通过Map.Entry的形式调用也可以直接导入
import java.util.Map.Entry;
就可以省略Map.
遍历时可以直接打印Entry对象也可以通过get的方式获取key和value SetMap.EntryString, Integer entries map.entrySet();for(Map.EntryString,Integer entry : entries){//System.out.println(entry);String s entry.getKey();Integer i entry.getValue();System.out.println(s i);}
最后还可以通过lambda的形式遍历 map.forEach(new BiConsumerString, Integer() {Overridepublic void accept(String key, Integer value) {System.out.println(key value);}});map.forEach((key, value) - System.out.println(key value));
3.2 LinkedHashMap
和LinkedHashSet一样LinkedHashMap存储的键是有序的存储顺序和取出顺序一样 3.3 TreeMap
TreeMap和TreeSet底层一样都是红黑树根据键进行排序排序规则也是类似的对于非数值等类型可以实现Comparable接口指定比较规则也可以传入比较器 4. 面试OJ题练习
4.1 随机链表的复制
138. 随机链表的复制 也就是下面这种情况 如果说直接对链表节点进行复制是不可以的因为题目中要求的是深拷贝所以说拷贝后的 节点可能和原来的地址不一样 思路遍历原来的链表每遍历一次都创建一个新的节点把原来的节点和拷贝的新节点的映射关系使用map存储起来再通过get方法得到节点再连接next和random public Node copyRandomList(Node head) {MapNode, Node map new LinkedHashMap();Node cur head;while (cur ! null) {Node copy new Node(cur.val);map.put(cur, copy);cur cur.next;}/*cur head;while (cur ! null) {map.get(cur).next map.get(cur.next);map.get(cur).random map.get(cur.random);cur cur.next;}*/SetNode keySet map.keySet();for (Node curNode : keySet) {map.get(curNode).next map.get(curNode.next);map.get(curNode).random map.get(curNode.random);}return map.get(head);}
4.2 宝石与石头
771. 宝石与石头 这一题就可以很好的利用Set集合元素不能重复的特性了如果不用Set集合把全部元素异或一遍就可以找到了而且速度更快这里只是为了练习一下Set集合的使用只需要把jewels存一个set再遍历stones判断是否有set集合里的元素即可
public class Text {public static void main(String[] args) {String jewels aA;String stones aAABBBBB;System.out.println(numJewelsInStones(jewels, stones));}public static int numJewelsInStones(String jewels, String stones) {SetCharacter set new HashSet();for (int i 0; i jewels.length(); i) {set.add(jewels.charAt(i));}int cnt 0;for (int i 0; i stones.length(); i) {if (set.contains(stones.charAt(i))) {cnt;}}return cnt;}
}
4.3 前k个高频单词
692. 前K个高频单词 思路前k个高频词就是经典的topk问题根据之前我们学到的就是用小根堆解决首先统计一下每个单词出现的频率并通过map存储它们的映射关系接着创建小根堆套用之前的模板解决 public ListString topKFrequent(String[] words, int k) {MapString, Integer map new HashMap();//统计单词个数并存入mapfor (String s : words) {if (map.get(s) null) {map.put(s, 1);} else {int val map.get(s);map.put(s, val);}}//创建根据map的value创建小根堆PriorityQueueMap.EntryString, Integer minHeap new PriorityQueue(new ComparatorMap.EntryString, Integer() {Overridepublic int compare(Map.EntryString, Integer o1, Map.EntryString, Integer o2) {//相同时根据key创建大根堆最后反转的时候就可以把字典序靠前的排到前面了if (o1.getValue().compareTo(o2.getValue()) 0) {return o2.getKey().compareTo(o1.getKey());}return o1.getValue().compareTo(o2.getValue());}});//根据之前讲解的topk问题解决for (Map.EntryString, Integer entry : map.entrySet()) {//先把前K个元素加入大根堆if (minHeap.size() k) {minHeap.offer(entry);} else {Map.EntryString, Integer top minHeap.peek();//堆顶元素频率小于后面的if (top.getValue().compareTo(entry.getValue()) 0) {minHeap.poll();minHeap.offer(entry);} else if (top.getValue().compareTo(entry.getValue()) 0) {//堆顶元素等于后面时堆顶的key字典序大于后面的if (top.getKey().compareTo(entry.getKey()) 0) {minHeap.poll();minHeap.offer(entry);}}}}ArrayListString ans new ArrayList();//把key存入ArrayListfor (int i 0; i k; i) {ans.add(minHeap.poll().getKey());}//题目要求出现频率由高到低进行翻转Collections.reverse(ans);return ans;}
