刷题必备- Java常见刷题使用容器整理

1 List

1.1 ArrayList

底层是数组，常见于数组类型的题目

顺序存储

可以根据下标来取数据：比如你只想取出下标为2的数据：list.get(2);

查询是O（1），插入或者删除是O（n）

头文件： import java.util.ArrayList;

import java.util.ArrayList;

public class Main {
  public static void main(String[] args) {
    ArrayList<String> cars = new ArrayList<String>();
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");
    cars.add("Mazda");
    System.out.println(cars);
  }
}

1.2 LinkedList

底层是链表

属于动态追加节点的数据结构

// Import the LinkedList class
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    LinkedList<String> cars = new LinkedList<String>();
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");
    cars.add("Mazda");
    System.out.println(cars);
  }
}

因为底层是链表结构，所以可以进行头/尾操作。

查询是O（n）, 插入或者删除是O（1）（因为不需要移动元素）

2 Set

2.1 HashSet集合

保持元素的唯一性

默认从小到大排序

常用在元素去重，元素访问标记等场景

底层是HashMap。

// Import the HashSet class
import java.util.HashSet;

public class Main {
  public static void main(String[] args) {
    HashSet<String> cars = new HashSet<String>();
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");
    cars.add("BMW");
    cars.add("Mazda");
    System.out.println(cars);
  }
}

检查元素是否存在set中：

cars.contains("Mazda");

删除某个元素：

cars.remove("Volvo");

时间复杂度：

add() 复杂度为 O(1)

remove() 复杂度为 O(1)

contains() 复杂度为 O(1)

3 Map

3.1 HashMap字典

<key, value> 键值对，key唯一。

HashMap再jdk7和jdk8种的实现略有不同：

JDK7

在创建一个HashMap对象之后,底层会创建一个长度为16的一维数组Entry[ table,当执行put(key1,value1)操

作时候,首先调用key1所在类的HashCode()计算key1的哈希希值,此哈希值经过特殊某种算法计算之后得到在En

try数组中的位置。如果此位置上为空,次数(key1,value1)添加成功,如果此时该位置数据不为空(意味着该位置

上可能有一个或者多个数据(以链表形式存在),比较Key1和已经存在在的数据的哈希值,如果都不相等则直接添

加(添加在链表前面),如果相同则调用equals方法进行比较,返回falIse则添加,返回true则将value1值替换匹配

位置的value值。在不断添加过程中,假如超过临界值(12)且要添加的位置非空,则将进行扩容,默认扩容为原

来的2倍(左移)。

JDK8:

JDK8中创建一个HashMap对象时候底层不会先创建一个长度为16的数组,而是创建一个空的Node[数组,当首

次执行put操作时候,底层才会创建一个长度为16的数组。

JDK7中HashMap涉及到的结构只有数组+链表,在JDK8中还添加了红黑树结构,当数组中某一索引位置上的链

表长度大于8且当前数据长度大于64时候,此时此索引位置」上的所有数据都会改为红黑树存储。当链表长度大于

8但是此时数据长度不大于64时候,就会执行扩容操作,而不不是进行红黑树变换。

常见刷题场景

需要快速查询历史数据的

保存图中节点的邻接节点的

需要快速判断历史是否存在过的

常见使用方法

// Import the HashMap class
import java.util.HashMap;

public class Main {
  public static void main(String[] args) {
    // Create a HashMap object called capitalCities
    HashMap<String, String> capitalCities = new HashMap<String, String>();

    // Add keys and values (Country, City)
    capitalCities.put("England", "London");
    capitalCities.put("Germany", "Berlin");
    capitalCities.put("Norway", "Oslo");
    capitalCities.put("USA", "Washington DC");
    System.out.println(capitalCities);
  }
}

put(k,v)

get(k)

remove(k)

4 Queue

4.1 Deque双端队列

底层是双向链表（https://cloud.tencent.com/developer/article/1511615）。

可以分别在队列的两头插入元素，常用来模拟队列/栈.

模拟队列时候的函数用法：

模拟栈的时候的函数用法：(这里是将链表头设置为栈顶，不过我一般习惯将表尾设置为栈顶，那么操作就改为addLast(), removeLast() 以及 peekLast()

参考：https://docs.oracle.com/javase/7/docs/api/java/util/Deque.html

peek() 方法一般用来取元素，但不会从队列中删除元素

pool() 方法用来取元素，同时还会从队列中把元素删除

4.2 PriorityQueue优先队列

底层是大根堆或者小根堆（https://www.cnblogs.com/wangchaowei/p/8288216.html）。

常用来解决每次取最小或者最大的元素，取完之后，会自动进行调整。

可以在new的时候指定排序方法，这样就能确定是小根堆还是大根堆了（默认小根堆）。

参考：https://www.cainiaojc.com/java/java-priorityqueue.html

这里举个🌰：

小根堆

    public static void main(String[] args) {
	PriorityQueue<Integer> pq = new PriorityQueue<>((x,y)->x-y);    //小根堆，lambda表达式
    pq.offer(9);
    pq.offer(8);
    pq.offer(7);

    while (!pq.isEmpty()){
        System.out.println(pq.poll());
    }

}

/*
结果：
7
8
9
*/

大根堆

    public static void main(String[] args) {
	PriorityQueue<Integer> pq = new PriorityQueue<>((x,y)->y-x);    //大根堆
    pq.offer(9);
    pq.offer(8);
    pq.offer(7);

    while (!pq.isEmpty()){
        System.out.println(pq.poll());
    }

}
/*结果987*/