ArrayList
基于动态数组实现，支持随机索引访问，访问索引的时间复杂度O(1)，非线程安全
| 方法 | 用处 |
|---|---|
| size() | 返回列表中的元素数量。 |
| add(E e) | 将指定元素添加到列表末尾。 |
| add(int index, E e) | 将指定元素插入到指定位置。 |
| get(int index) | 返回指定索引处的元素。 |
| remove(int index) | 删除指定索引处的元素。 |
| remove(Object o) | 删除第一个匹配的元素。 |
| set(int index, E e) | 将指定索引处的元素替换为新值。 |
| clear() | 清空列表中的所有元素。 |
| toArray() | 将列表转换为数组。 |
| contains(Object o) | 判断列表是否包含指定元素。 |
ArrayList的排序
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class LCR074 {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(3);
list.add(1);
list.add(2);
// 默认升序排序
Collections.sort(list);
System.out.println(list); // 输出：[1, 2, 3]
// 自定义降序排序
Collections.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1); // 降序
}
});
System.out.println(list); // 输出：[3, 2, 1]
}
}
LinkedList
基于双向链表实现，不支持随机索引访问，需要O(n)的时间复杂度遍历查找。但可以向头和尾以O(1)的时间复杂度插值。
| 方法 | 用法 |
|---|---|
| size() | 返回列表中的元素数量。 |
| isEmpty() | 判断列表是否为空 |
| clear() | 清空列表中的所有元素 |
| add(E e) | 将指定元素添加到列表末尾。 |
| addFirst(E e) | 将指定元素添加到列表头部。 |
| addLast(E e) | 将指定元素添加到列表尾部。 |
| add(int index, E e) | 将指定元素插入到指定位置。 |
| get(int index) | 返回指定索引处的元素。 |
| first() | 返回列表的第一个元素。 |
| last() | 返回列表的最后一个元素。 |
| remove(int index) | 删除指定索引处的元素。 |
| removeFirst() | 删除列表的第一个元素。 |
| removeLast() | 删除列表的最后一个元素。 |
| remove(Object o) | 删除第一个匹配的元素。 |
| set(int index, E e) | 将指定索引处的元素替换为新值。 |
| toArray() | 将列表转换为数组。 |
| contains(Object o) | 判断列表是否包含指定元素。 |
HashMap
JDK1.7之前，HashMap是基于数组和链表实现的，JDK1.8之后，如果链表长度超过8，链表就转为红黑树。非线程安全
| 方法 | 用法 |
|---|---|
| put(K key, V value) | 将键值对添加到 HashMap 中。如果键已存在，则更新对应的值。 |
| putIfAbsent(K key, V value) | 如果键不存在，则添加键值对；如果键已存在，则不更新。 |
| get(Object key) | 根据键获取对应的值。如果键不存在，返回 null。 |
| getOrDefault(Object key, V defaultValue) | 根据键获取对应的值。如果键不存在，返回默认值。 |
| remove(Object key) | 根据键删除对应的键值对。 |
| remove(Object key, Object value) | 只有当键和值都匹配时，才删除键值对。 |
| containsKey(Object key) | 检查是否包含指定的键。 |
| containsValue(Object value) | 检查是否包含指定的值。 |
| size() | 返回 HashMap 中键值对的数量。 |
| isEmpty() | 检查 HashMap 是否为空。 |
| replace(K key, V value) | 替换指定键的值（键必须存在）。 |
| replace(K key, V oldValue, V newValue) | 只有当键和旧值都匹配时，才替换为新值 |
Hashmap的遍历：
import java.util.HashMap;
public class LCR074 {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("nihao",1);
//遍历键值对
for (HashMap.Entry<String, Integer> entry : map.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
//遍历键
for (String key : map.keySet()) {
System.out.println("Key: " + key);
}
//遍历值
for (Integer value : map.values()) {
System.out.println("Value: " + value);
}
}
}
Queue
队列是一种先进先出（FIFO）的数据结构，支持在队尾添加元素，在队头移除元素。在 Java 中，Queue 是一个接口，而 LinkedList 是 Queue 接口的一个实现类。
| 方法 | 用法 |
|---|---|
| add(E e) | 将一个元素添加到队列末尾。如果队列已满，抛出 IllegalStateException。 |
| offer(E e) | 将一个元素添加到队列末尾。如果队列已满，返回 false，而不是抛出异常。 |
| remove() | 移除并返回队列头部的元素。如果队列为空，抛出 NoSuchElementException。 |
| poll() | 移除并返回队列头部的元素。如果队列为空，返回 null，而不是抛出异常。 |
| element() | 返回队列头部的元素，但不移除它。如果队列为空，抛出 NoSuchElementException。 |
| peek() | 返回队列头部的元素，但不移除它。如果队列为空，返回 null，而不是抛出异常。 |
| size() | 返回队列中的元素数量。 |
| clear() | 清空队列中的所有元素。 |
| toArray() | 将队列转换为数组。 |
| contains(Object o) | 判断队列是否包含指定元素。 |
常用算法：bfs
import java.util.LinkedList;
import java.util.Queue;
public class BFSExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.println("Visited: " + current);
// 添加邻接节点到队列
queue.add(current + 1);
queue.add(current + 2);
}
}
}
Stack
Stack 是 Java 中的一个类，继承自 Vector，用于实现后进先出（LIFO，Last In First Out）的栈数据结构。
| 方法 | 用法 |
|---|---|
| push(E item) | 将一个元素压入栈顶 |
| pop() | 移除并返回栈顶元素。 |
| peek() | 返回栈顶元素，但不移除它。 |
| empty() | 判断栈是否为空。 |
常用算法：括号匹配、单调栈
括号匹配：使用栈检查括号是否成对匹配。
import java.util.Stack;
public class ParenthesesMatch {
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>(); // 使用栈来存储左括号
for (char c : s.toCharArray()) { // 遍历字符串中的每个字符
// 如果是左括号，压入栈中
if (c == '(' || c == '{' || c == '[') stack.push(c);
// 如果是右括号，检查栈顶是否匹配
else if (stack.isEmpty() || // 栈为空，说明没有匹配的左括号
(c == ')' && stack.pop() != '(') || // 弹出栈顶并检查是否匹配
(c == '}' && stack.pop() != '{') ||
(c == ']' && stack.pop() != '[')) return false; // 不匹配则返回 false
}
return stack.isEmpty(); // 如果栈为空，说明所有括号都匹配
}
public static void main(String[] args) {
System.out.println(isValid("()[]{}")); // true
System.out.println(isValid("([)]")); // false
}
}
单调栈：用于解决“下一个更大元素”类问题，栈中保持单调递减。
import java.util.Stack;
public class MonotonicStack {
public static int[] nextGreaterElement(int[] nums) {
int[] result = new int[nums.length]; // 存储结果的数组
Stack<Integer> stack = new Stack<>(); // 单调栈，栈底到栈顶单调递减
for (int i = nums.length - 1; i >= 0; i--) { // 从后往前遍历数组
// 如果栈顶元素小于当前元素，弹出栈顶（维护单调性）
while (!stack.isEmpty() && stack.peek() <= nums[i]) stack.pop();
// 如果栈为空，说明没有更大的元素；否则栈顶就是下一个更大元素
result[i] = stack.isEmpty() ? -1 : stack.peek();
// 将当前元素压入栈中
stack.push(nums[i]);
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 1, 2, 4, 3};
int[] result = nextGreaterElement(nums);
for (int num : result) System.out.print(num + " "); // 输出: 4 2 4 -1 -1
}
}
PriorityQueue
优先队列，可以理解成有序的队列。
| 方法 | 用处 |
|---|---|
| add(E e) | 将元素插入优先队列。如果队列已满，抛出异常。 |
| offer(E e) | 将元素插入优先队列。如果队列已满，返回 false。 |
| remove() | 移除并返回队列头部元素（优先级最高的元素）。如果队列为空，抛出异常。 |
| poll() | 移除并返回队列头部元素（优先级最高的元素）。如果队列为空，返回 null。 |
| element() | 返回队列头部元素（不移除）。如果队列为空，抛出异常。 |
| peek() | 返回队列头部元素（不移除）。如果队列为空，返回 null。 |
| size() | 返回队列中的元素数量。 |
| isEmpty() | 检查队列是否为空。 |
| clear() | 清空队列中的所有元素。 |
| contains(Object o) | 检查队列中是否包含指定元素。 |
| toArray() | 将队列转换为数组。 |
| iterator() | 返回队列的迭代器。 |
| comparator() | 返回队列的比较器（如果未指定比较器，返回 null）。 |
(1) 最小堆优先队列，优先返回队列中最小值
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// 创建一个最小堆优先队列
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 添加元素
minHeap.add(10);
minHeap.add(5);
minHeap.add(20);
minHeap.add(15);
// 输出队列中的元素（按优先级顺序）
while (!minHeap.isEmpty()) {
System.out.println(minHeap.poll()); // 输出: 5, 10, 15, 20
}
}
}
(2) 最大堆优先队列，优先返回队列中最大值
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// 创建一个最大堆优先队列
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
// 添加元素
maxHeap.add(10);
maxHeap.add(5);
maxHeap.add(20);
maxHeap.add(15);
// 输出队列中的元素（按优先级顺序）
while (!maxHeap.isEmpty()) {
System.out.println(maxHeap.poll()); // 输出: 20, 15, 10, 5
}
}
}
(3) 自定义对象的优先队列，自己定义排序方式
import java.util.PriorityQueue;
public class PriorityQueue2DArray {
public static void main(String[] args) {
int[][] array = {
{3, 5},
{1, 2},
{4, 1},
{2, 8},
{5, 7}
};
// 创建一个优先队列，按第 0 列排序（最小堆）
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
// 将二维数组的每一行加入优先队列
for (int[] row : array) {
minHeap.offer(row);
}
// 按优先级顺序输出
while (!minHeap.isEmpty()) {
int[] row = minHeap.poll();
System.out.println("[" + row[0] + ", " + row[1] + "]");
}
}
}
常用算法：dijkstra
import java.util.*;
public class Dijkstra {
// 定义图的边
static class Edge {
int target; // 目标节点
int weight; // 边的权重
public Edge(int target, int weight) {
this.target = target;
this.weight = weight;
}
}
// Dijkstra 算法实现
public static int[] dijkstra(List<List<Edge>> graph, int start) {
int n = graph.size(); // 图中节点的数量
int[] dist = new int[n]; // 存储从起点到每个节点的最短距离
Arrays.fill(dist, Integer.MAX_VALUE); // 初始化为无穷大
dist[start] = 0; // 起点到自身的距离为 0
// 优先队列（最小堆），按距离排序
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{start, 0}); // 将起点加入队列
while (!pq.isEmpty()) {
int[] current = pq.poll(); // 取出当前距离最小的节点
int node = current[0];
int distance = current[1];
// 如果当前节点的距离已经大于记录的最短距离，跳过
if (distance > dist[node]) continue;
// 遍历当前节点的所有邻居
for (Edge edge : graph.get(node)) {
int neighbor = edge.target;
int newDist = dist[node] + edge.weight;
// 如果找到更短的路径，更新距离并加入队列
if (newDist < dist[neighbor]) {
dist[neighbor] = newDist;
pq.offer(new int[]{neighbor, newDist});
}
}
}
return dist; // 返回起点到所有节点的最短距离
}
public static void main(String[] args) {
// 示例：图的邻接表表示
int n = 5; // 节点数量
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 添加边
graph.get(0).add(new Edge(1, 4)); // 0 -> 1，权重 4
graph.get(0).add(new Edge(2, 1)); // 0 -> 2，权重 1
graph.get(1).add(new Edge(3, 1)); // 1 -> 3，权重 1
graph.get(2).add(new Edge(1, 2)); // 2 -> 1，权重 2
graph.get(2).add(new Edge(3, 5)); // 2 -> 3，权重 5
graph.get(3).add(new Edge(4, 3)); // 3 -> 4，权重 3
int start = 0; // 起点
int[] dist = dijkstra(graph, start);
// 输出结果
System.out.println("从节点 " + start + " 到其他节点的最短距离：");
for (int i = 0; i < n; i++) {
System.out.println("到节点 " + i + " 的距离: " + dist[i]);
}
}
}
