PROSAGA码农传奇-笔试面试题-哪些Java库对竞争性编程有用

Java是竞争性编程中最推荐的语言之一（请参阅上一篇文章以获取更多详细信息） 
Java Collection框架包含许多用于不同目的的容器。在本文中，我们将从竞争性编程和面试准备的角度重点介绍最重要的容器。 
ArrayList：动态大小可变的数组，允许插入和删除而不关心数组的大小。它还具有纯数组的优点，例如随机访问和缓存友好性。Java ArrayList支持许多其他操作，例如 indexOf（）， remove（）等。普通数组不支持这些功能。 
队列：由 LinkedList实现的接口。在我们希望具有FIFO项目顺序的情况下很有用。实施例的问题是，产生具有给定的位数，第一非重复字符流中的， 树的层次序遍历和其变型中，图的BFS和其变体。请参阅队列练习问题以获取更多练习。 
堆栈：用于我们希望获得LIFO订单的情况。示例问题包括平衡括号，股票跨度问题，直方图中的下一个更大的元素和 最大的面积。请参阅堆栈练习问题以获取更多练习。 
Deque：Deque是由LinkedList类实现的接口。出队支持O（1）时间两端的插入和删除。我们可以使用Deque接口同时实现Queue和Stack。实际上，建议使用Deque在Java中实现Stack，因为Java中的Stack类是旧样式类。关于Deque的示例问题是，访问所有的汽油泵 和所有大小为k的子数组的最大值。 
Java中的Set（下面讨论的TreeSet，HashSet和LinkedHashSet）用于存储键的集合，而Java中的Map（下面讨论的TreeMap，HashMap和LinkedHashMap）用于存储键值对的集合。 
TreeSet和 TreeMap：这两个都实现自平衡二进制搜索树（特别是 Red Black Tree）。在我们希望通过中等（比数组更好，比哈希更差）搜索，插入和删除查询时间来维护排序项目的情况下很有用。示例问题包括：左侧的最近最大或相同的值，在arra y中查找每个元素的最接近的值等。当我们希望仅存储键时，我们使用TreeSet，而当我们希望存储键值对时，则使用TreeMap。 
HashSet和HashMap：这两个都通过链接实现散列。当我们希望快速搜索，插入和删除时很有用（所有三个操作均为O（1））。这是该行业中最常用的数据结构之一，在学术界也被低估了。有许多流行的问题，C ‘mount不同元件，的数组项的频率， 子阵列与0相加，并 联合和两个未排序阵列的交叉点。请参阅散列练习问题以获取更多练习。 
LinkedHashSet和 LinkedHashMap ：通过链接实现散列，但还可以保持插入顺序。HashSet和HashMap不维护任何顺序。因此，如果我们希望按与输入中出现的顺序相同的顺序打印不同的元素，则需要使用LinkedHashSet，并且如果我们希望按其出现的顺序打印项目及其频率，则需要使用LinkedHashMap。 
PriorityQueue：默认情况下实现最小堆。我们也可以通过传递Collections.reverseOrder（）作为参数来创建最大堆。每当我们希望有效地找到最小或最大元素时，就会使用PriorityQueue。它是用来实现流行的算法，如 Prim算法， Dijkstra的最短路径，霍夫曼编码， k个最大的元素，最大玩具到购买和合并ķ排序阵列， 一个流的中位数。请参阅堆练习问题以获取更多练习。