Java es uno de los lenguajes más recomendados en la programación competitiva (consulte un artículo anterior para obtener más detalles)
El marco de Java Collection contiene muchos contenedores que son útiles para diferentes propósitos. En este artículo, nos vamos a centrar en los contenedores más importantes desde el punto de vista de la programación competitiva y la preparación de entrevistas.
ArrayList : array de tamaño dinámico que permite inserciones y eliminaciones sin importar el tamaño de la array. También tiene las ventajas de las arrays simples, como el acceso aleatorio y la compatibilidad con la memoria caché. Java ArrayList admite muchas operaciones adicionales como indexOf() , remove() , etc. Estas funciones no son compatibles con arrays normales.
Queue : una interfaz implementada por LinkedList . Útil en situaciones en las que deseamos tener un orden FIFO de artículos. Los problemas de ejemplo son, generar números con un dígito dado , el primer carácter que no se repite en una secuencia , el recorrido de orden de nivel de un árbol y sus variaciones, BFS de un gráfico y sus variaciones. Consulte los problemas de práctica de la cola para obtener más práctica.
Stack : Usado en situaciones donde deseamos tener orden LIFO. Los problemas de ejemplo son el paréntesis equilibrado , el problema de stock span , el siguiente elemento mayor y el área más grande en un histograma . Consulte los problemas de práctica de Stack para obtener más práctica.
Deque : Deque es una interfaz implementada por la clase LinkedList. Dequeue admite inserciones y eliminaciones en ambos extremos en tiempo O(1). Podemos usar la interfaz Deque para implementar Queue y Stack. De hecho, se recomienda usar Deque para implementar Stack en Java porque la clase Stack en Java es una clase de estilo antiguo. Los problemas de ejemplo en Deque son, visitar todas las bombas de gasolina y los máximos de todos los subarreglos de tamaño k .
Se usa un conjunto en Java (TreeSet, HashSet y LinkedHashSet que se analizan a continuación) para almacenar una colección de claves y un mapa en Java (TreeMap, HashMap y LinkedHashMap que se analizan a continuación) se usa para almacenar una colección de pares de valores clave.
TreeSet y TreeMap : ambos implementan un árbol de búsqueda binaria autoequilibrado ( Red Black Tree en particular). Útil en situaciones en las que deseamos mantener elementos ordenados con un tiempo de búsqueda, inserción y eliminación moderado (mejor que una array y peor que hash). Los problemas de ejemplo son: el valor más cercano mayor o igual en el lado izquierdo , encontrar el valor más cercano para cada elemento en una array , etc. Usamos TreeSet cuando deseamos almacenar solo claves y TreeMap cuando deseamos almacenar pares de valores clave.
HashSet y HashMap : ambos implementan hashing con enstringmiento. Útil cuando deseamos tener una búsqueda rápida, insertar y borrar (las tres operaciones son O(1)). Esta es una de las estructuras de datos más utilizadas en la industria y más subestimada en el mundo académico. Hay muchos problemas populares, contar elementos distintos , frecuencias de elementos de array , subarreglo con suma 0 y unión e intersección de dos arrays no ordenadas . Consulte Problemas de práctica de hash para obtener más práctica.
LinkedHashSet y LinkedHashMap : implemente hash con enstringmiento, pero además mantenga el orden de inserción. HashSet y HashMap no mantienen ningún orden. Entonces, si deseamos imprimir elementos distintos en el mismo orden en que aparecen en la entrada, debemos usar LinkedHashSet y si deseamos imprimir elementos y sus frecuencias en el mismo orden en que aparecen, debemos usar LinkedHashMap.
PriorityQueue : implementa Min Heap de forma predeterminada. También podemos crear un Max Heap pasando Collections.reverseOrder() como parámetro. PriorityQueue se usa siempre que deseamos encontrar eficientemente el elemento mínimo o máximo. Se utiliza para implementar algoritmos populares como el algoritmo de Prim, la ruta más corta de Dijkstra , la codificación de Huffman , los elementos más grandes de K , la cantidad máxima de juguetes para comprar y fusionar arrays ordenadas de K , la mediana de un flujo . Consulte Problemas de práctica de montones para obtener más práctica.
Cubriremos bibliotecas de Java más importantes en la siguiente parte de este artículo.