集合 API 速查

Array

// 声明数组
double[] arr;

// 创建数组
arr = new double[N];

// 初始化数组
for (int i = 0; i < N; i++) {
    arr[i] = 0.0;
}

简化写法：double[] arr = new double[N];

声明初始化：int[] arr = { 1, 1, 2, 3, 5, 8 }; 这里就是声明、创建并初始化一个数组。

初始化方法：

int m = 5, n = 10;

// 初始化一个大小为 10 的 int 数组
int[] nums = new int[n];

// 初始化一个 m * n 的二维布尔数组
// 其中的元素默认初始化为 false
boolean[][] visited = new boolean[m][n];

一般题目会以函数参数的形式传入，要在函数开头做一个非空检查，然后用索引下标访问其中的元素即可：

if (nums.length == 0) {
    return;
}

for (int i = 0; i < nums.length; i++>) {
    // 访问 nums[i]
}

java.util.ArrayList

动态数组 ArrayList 相当于把 Java 内置的数组类型做了包装，初始化方法如下：

ArrayList<E>()
ArrayList<E>()


// 初始化一个存储 String 类型的动态数组
ArrayList<String> strings = new ArrayList<>();

// 初始化一个存储 int 类型的动态数组
ArrayList<Integer> nums = new ArrayList<>();

常用方法如下（E代表元素类型）：

boolean isEmpty() // 判断数组是否为空

int size() // 返回数组的元素个数

E set(int index, E obj) 

E get(int index) // 返回索引 index 的元素

boolean add(E e) // 在数组尾部添加元素 e

E remove(int index)

void ensureCapacity(int capacity)

void trimToSize()

String

java.lang.String

Java 的字符串处理起来挺麻烦的，因为它不支持用[]直接访问其中的字符，而且不能直接修改，要转化成char[]类型才能修改。

String s1 = "hello world";
char c = s1.charAt(2); // 获取 s1[2] 那个字符

char[] chars = s1.toCharArray();
chars[1] = 'a';
String s2 = new String(chars);
System.out.println(s2); // 输出：hallo world

// 注意，一定要用 equals 方法判断字符串是否相同
if (s1.equals(s2)) {
    // s1 和 s2 相同
} else {
    // s1 和 s2 不相同
}

// 字符串可以用加号进行拼接
String s3 = s1 + "!";
// 输出：hello world!
System.out.println(s3);

Java 的字符串不能直接修改（字符串对象是 immutable），要用toCharArray转化成char[]的数组进行修改，然后再转换回String类型。

另一个需要检查两个字符串是否相等要用equals方法，不要用==比较。

另外，虽然字符支持用+进行拼接，但是效率并不高，并不建议在 for 循环中使用。如果需要进行频繁的字符串拼接，推荐使用StringBuilder：

StringBuilder sb = new StringBuilder();

for (char c = 'a'; c <= 'f'; c++) {
    sb.append(c);
}

// append 方法支持拼接字符、字符串、数字等类型
sb.append('g').append('hij').append(123);

String res = sb.toString();
// 输出：abcdefghij123
System.out.println(res);

java.lang.StringBuilder

StringBuilder()
int length()
StringBuilder append(String str)
StringBuilder append(char c)
String toString()

LinkedList

LinkedList

ArrayList 列表底层是用数组实现的，而LinkedList底层是用双链表实现的，初始化方法也是类似：

// 初始化一个存储 int 类型的双链表
LinkedList<Integer> nums = new LinkedList<>();

// 初始化一个存储 String 类型的双链表
LinkedList<String> strings = new LinkedList<>();

常用方法介绍（E代表元素类型）：

boolean isEmpty() // 判断链表是否为空

int size() // 返回链表的元素个数

// 判断链表中是否存在元素 o
boolean contains(Object o)

// 在链表尾部添加元素 e
boolean add(E e)

// 在链表尾部添加元素 e
void addLast(E e)

// 在链表头部添加元素 e
void addFirst(E e)

// 删除链表头部第一个元素
E removeFirst()

// 删除链表尾部最后一个元素
E removeLast()

其中 contains 方法的时间复杂度是 O(N)，是因为必须遍历整个链表才能判断元素是否存在。

有些题目要求函数返回值是 List 类型，ArrayList 和 LinkedList 都是 List 类型的子类，我们只需要根据数据结果的特性类决定使用数组合适链表，最后直接返回就行了。

HashTable

java.util.HashMap<K, V>

初始化方法如下：

HashMap();
HashMap(int initialCapacity);
HashMap(int initialCapacity, float loadFactor);
// 用给定的容量和装填因子构造一个空散列映射（装填因子是一个 0.0 ~ 1.0 之间的数。这个数决定散列表填充的百分比。一旦到了这个比例，就要再散列到更大的散列表中）。
// 默认的装填因子是 0.75

// 整数映射到字符串的哈希表
HashMap<Integer, String> map = new HashMap<>();

// 字符串映射到数组的哈希表
HashMap<String, int[]> map = new HashMap<>();

常用方法如下（K代表键的类型，V代表值的类型）：

// 判断哈希表中是否存在键 key
boolean containsKey(Object key)

// 获得键 key 对应的值，若 key 不存在，则返回 null
V get(Object key)

// 将 key, value 键值对存入哈希表
V put(K key, V value)

// 如果 key 存在，删除 key 并返回对应的值
V remove(Object key)

// 获得 key 的值，如果 key 不存在，则返回 defaultValue
V getOrDefault(Object key, V defaultValue)

// 获得哈希表中的所有 key
Set<K> keySet()

// 如果 key 不存在，则将键值对 key, value 存入哈希表
// 如果 key 存在，则什么都不做
V putIfAbsent(K key, V value)

java.util.HashSet

初始化方法：

HashSet();
HashSet(Collection<? extends E> elements);
HashSet(int initialCapacity);
HashSet(int initialCapacity, float loadFactor);

// 新建一个存储 String 的哈希集合
Set<String> set = new HashSet<>();

常用方法介绍（E代表元素类型）：

// 如果 e 不存在，则将 e 添加到哈希集合
boolean add(E e)

// 判断元素 o 是否存在于哈希集合中
boolean contains(Object o)

// 如果元素 o 存在，再删除元素 o
boolean remove(Object o)

Queue

java.util.Queue

队列 Queue 是一个接口（Interface），所以它的初始化方法有些特别

// 新建一个存储 String 的队列
Queue<String> q = new LinkedList<>();

常用方法介绍（E代表元素类型）：

boolean isEmpty() // 判断队列是否为空

int size() // 返回队列中元素的个数

E element()
E peek() // 删除并返回队头的元素

E remove()
E poll() // 删除并返回队头的元素

boolean add(E element)
boolean offer(E element) // 将元素 e 插入队尾

java.util.Deque

Stack

java.util.Stack

初始化方法：

Stack<Integer> s = new Stack<>();

常用方法介绍（E代表元素类型）：

boolean isEmpty() // 判断堆栈是否为空

int size() // 返回堆栈中元素的个数

E push(E item) // 将 item 压入栈并返回 item。

E peek() // 返回栈顶元素，但不弹出。如果栈为空，不要调用这个方法。

E pop() // 弹出并返回栈顶的 item。如果栈为空，不要调用这个方法。

Heap

PriorityQueue

优先级队列使用二叉堆的特点，可以使得插入的数据自动排序（升序或者是降序)。PriorityQueue 是一个基于优先级堆的无界队列，它的元素是按照自然顺序（natural order）排序的。在创建的时候，我们可以给它提供一个负责给元素排序的比较器。PriorityQueue 不允许 null 值，因为他们没有自然顺序，或者说他们没有任何的相关联的比较器。最后，PriorityQueue 不是线程安全的，入队和出队的时间复杂度是 O(log(n))。

PriorityQueue 不允许放入 null 元素

• 是线程不安全的队列
• 存储使用数组实现
• 利用比较器做优先级比较
• 最小堆的特性就是最小的值在最上面，每次取 O(1)，插入 O(logn)

peek() // 返回队首元素
poll() // 返回队首元素，队首元素出队列
add() // 添加元素
size() // 返回队列元素个数
isEmpty() // 判断队列是否为空，为空返回 true，不空返回 false

示例：

PriorityQueue<Integer> queue = new PriorityQueue<>();
// 添加，失败抛异常
queue.add(1);
// 添加，失败返回 false
queue.offer(2);
// 获取并删除队首元素,失败返回 null
queue.poll();
// 获取并删除队首元素,如果不成功会返回 false。
queue.remove();
// 查询队顶元素，不删除，失败返回null
queue.peek();
while (!queue.isEmpty()) {
    System.out.println(queue.poll());
}

// 使用自定义的 Comparator
Comparator<String> stringLengthComparator = new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
        // s1-s2 升序
        // s2-s1 降序
    }
};

PriorityQueue<String> namePriorityQueue = new PriorityQueue<>(stringLengthComparator);
namePriorityQueue.add("Lisa");
namePriorityQueue.add("Robert");
namePriorityQueue.add("John");
namePriorityQueue.add("Chris");
namePriorityQueue.add("Angelina");
namePriorityQueue.add("Joe");

// Joe
// John
// Lisa
// Chris
// Robert
// Angelina
while (!namePriorityQueue.isEmpty()) {
    System.out.println(namePriorityQueue.remove());
}

堆的用法：

• 利用堆的排序功能和限制堆的大小，删除最大/最小的堆顶，保留最小/最大的k个数
• 往堆里添加时，判断堆的大小用于裁剪，某些场景下判断值的大小再考虑是否入堆
• heap.poll()，是关键操作，总是删除有序队列的最大/最小值
• 例如：最大k个数，使用最小堆，循环 add，同时判断当 size 超过 k 个，就 poll 掉堆顶最小的，留下的就是“前k大的”几个数

Priority定义时，Comparator的定义是关键：

// 写法一：new
PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>()
{
    @Override
    public int compare(Integer o1, Integer o2)
    {
        // 默认，小顶堆
        return o1-o2;
        // 大顶堆
        return o2-o1;
    }
});

// 写法二：lambda
PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o1-o2);

// 写法三：
PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o));

示例：

// 示例1： 
// 定义一个 map，统计一个数组中数字出现的次数。
Map<Integer, Integer> map = new HashMap<>();
  for (int num : nums) {
  map.put(num, map.getOrDefault(num, 0) + 1);
}
// 比较器根据 key 取到的 map 进行排序
Comparator<Integer> comparator = (o1, o2) -> map.get(o1) - map.get(o2);
// heap 中存放 map 的 key，但是根据 value 排序
PriorityQueue<Integer> heap = new PriorityQueue<>(k, comparator);


// 示例2： （692. 前K个高频单词）
// 要求遍历堆返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
// ["i", "love"] 两个字符串数量相同，就按字母顺序 "i" 在 "love" 之前。
PriorityQueue<String> heap =
        new PriorityQueue<>(
                (o1, o2) -> (count.get(o1)).equals(count.get(o2))
                                ? o2.compareTo(o1)
                                : count.get(o1) - count.get(o2));

Tree

TreeSet

TreeMap