🗂️ Java算法题常用容器API速查

1. 数组 (Array)

特点：固定长度、随机访问快速、存储基本类型或对象。

关键API：

int[] arr = new int[10]; // 声明长度为10的整型数组
int[] arr = {1, 2, 3}; // 声明并初始化
arr[0] = 1; // 赋值
int len = arr.length; // 获取长度（注意没有括号）

数组工具类 Arrays：

import java.util.Arrays;

// 排序
Arrays.sort(arr); // 默认升序
Arrays.sort(arr, fromIndex, toIndex); // 部分排序

// 二分查找（必须先排序）
int pos = Arrays.binarySearch(arr, key);

// 填充
Arrays.fill(arr, value); // 全部填充
Arrays.fill(arr, fromIndex, toIndex, value); // 部分填充

// 复制
int[] newArr = Arrays.copyOf(arr, newLength);
int[] range = Arrays.copyOfRange(arr, from, to);

// 比较
boolean equal = Arrays.equals(arr1, arr2);

// 转换为字符串
String str = Arrays.toString(arr);

2. 字符串 (String)

特点：不可变对象，任何修改都会创建新对象。

关键API：

String s = "hello";

// 基本信息
int len = s.length();
boolean empty = s.isEmpty();

// 访问字符
char c = s.charAt(0);

// 查找
int index = s.indexOf('l'); // 第一个出现位置
int lastIndex = s.lastIndexOf('l'); // 最后一个出现位置
boolean contains = s.contains("ll");

// 子字符串
String sub = s.substring(1, 3); // [1,3) → "el"

// 比较
boolean equal = s.equals("hello");
boolean ignoreCase = s.equalsIgnoreCase("HELLO");
int cmp = s.compareTo("world");

// 转换
char[] chars = s.toCharArray();
String upper = s.toUpperCase();
String lower = s.toLowerCase();

// 分割与连接
String[] parts = s.split("l"); // 按分隔符分割
String joined = String.join("-", "a", "b", "c"); // "a-b-c"

// 替换
String newStr = s.replace('l', 'L');
String newStr2 = s.replaceAll("l", "L");

// 去除空格
String trimmed = "  hello  ".trim();

3. 列表 (List)

ArrayList：基于动态数组，随机访问快，增删较慢。
LinkedList：基于双向链表，增删快，随机访问慢。

关键API：

import java.util.*;

// 构造方法
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new LinkedList<>();
List<Integer> list3 = new ArrayList<>(Arrays.asList(1, 2, 3));

// 添加元素
list.add(element); // 末尾添加
list.add(index, element); // 指定位置插入

// 获取元素
int element = list.get(index);

// 修改元素
list.set(index, newElement);

// 删除元素
list.remove(index); // 按索引删除
list.remove(element); // 按元素删除（首次出现）

// 信息查询
int size = list.size();
boolean empty = list.isEmpty();
boolean exists = list.contains(element);
int index = list.indexOf(element);

// 遍历
for (int i = 0; i < list.size(); i++) { // 索引遍历
    System.out.println(list.get(i));
}
for (String item : list) { // foreach遍历
    System.out.println(item);
}
Iterator<String> it = list.iterator(); // 迭代器遍历
while (it.hasNext()) {
    System.out.println(it.next());
}

4. 栈 (Stack)

特点：后进先出 (LIFO)，Java官方推荐使用Deque替代Stack。

两种实现方式：

// 方式1：使用Stack类（较老，但简单）
Stack<Integer> stack = new Stack<>();
stack.push(1); // 入栈
int top = stack.pop(); // 出栈
int peek = stack.peek(); // 查看栈顶
boolean empty = stack.empty();

// 方式2：使用Deque接口（推荐）
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 入栈
int top = stack.pop(); // 出栈
int peek = stack.peek(); // 查看栈顶
boolean empty = stack.isEmpty();

5. 队列 (Queue)

特点：先进先出 (FIFO)，有多种实现方式。

普通队列：

Queue<Integer> queue = new LinkedList<>();

// 添加元素（推荐使用offer，失败返回false）
queue.offer(element); // 添加成功返回true
queue.add(element); // 失败时抛出异常

// 获取并移除
int head = queue.poll(); // 返回队首，队列空时返回null
int head = queue.remove(); // 队列空时抛出异常

// 仅获取不移除
int peek = queue.peek(); // 队列空时返回null
int element = queue.element(); // 队列空时抛出异常

// 判断
boolean empty = queue.isEmpty();

双端队列 (Deque)：

Deque<Integer> deque = new ArrayDeque<>();

// 添加操作
deque.offerFirst(1); deque.offerLast(2); // 两端添加
deque.addFirst(1); deque.addLast(2);

// 移除操作
int first = deque.pollFirst(); // 移除队首
int last = deque.pollLast(); // 移除队尾

// 查看操作
int first = deque.peekFirst(); // 查看队首
int last = deque.peekLast(); // 查看队尾

6. 优先队列 (PriorityQueue)

特点：基于堆实现，元素按优先级顺序出队，默认小根堆。

// 构造方法
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小根堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 大根堆

// 带初始容量的构造
PriorityQueue<Integer> pq = new PriorityQueue<>(10, (a, b) -> a - b); // 小根堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(10, (a, b) -> b - a); // 大根堆

// 基本操作
pq.offer(element); // 添加元素
int top = pq.poll(); // 取出堆顶元素
int peek = pq.peek(); // 查看堆顶元素（不取出）
boolean empty = pq.isEmpty();
int size = pq.size();

7. 集合 (Set)

HashSet：基于哈希表，无序，查找O(1)。
TreeSet：基于红黑树，有序，查找O(log n)。

关键API：

import java.util.*;

// 构造方法
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new TreeSet<>();
Set<Integer> set3 = new HashSet<>(Arrays.asList(1, 2, 3));

// 基本操作
set.add(element); // 添加元素
set.remove(element); // 删除元素
boolean exists = set.contains(element); // 判断存在

// 集合操作
set1.addAll(set2); // 并集
set1.retainAll(set2); // 交集
set1.removeAll(set2); // 差集

// 遍历
for (int num : set) { // foreach遍历
    System.out.println(num);
}
Iterator<Integer> it = set.iterator(); // 迭代器遍历

// TreeSet特有方法
TreeSet<Integer> treeSet = new TreeSet<>();
Integer ceiling = treeSet.ceiling(5); // 大于等于5的最小元素
Integer floor = treeSet.floor(5); // 小于等于5的最大元素
Integer higher = treeSet.higher(5); // 严格大于5的最小元素
Integer lower = treeSet.lower(5); // 严格小于5的最大元素

8. 映射 (Map)

HashMap：基于哈希表，无序，查找O(1)。
TreeMap：基于红黑树，按键排序，查找O(log n)。

关键API：

import java.util.*;

// 构造方法
Map<String, Integer> map1 = new HashMap<>();
Map<String, Integer> map2 = new TreeMap<>();

// 添加/修改
map.put("key", value); // 添加键值对
map.putIfAbsent("key", value); // 仅当key不存在时放入

// 获取
int value = map.get("key"); // 获取值，不存在返回null
int value = map.getOrDefault("key", defaultValue); // 不存在返回默认值

// 删除
map.remove("key"); // 删除指定key
map.remove("key", value); // 仅当key对应value匹配时删除

// 查询
boolean exists = map.containsKey("key"); // 判断key是否存在
boolean valueExists = map.containsValue(10); // 判断value是否存在
int size = map.size();
boolean empty = map.isEmpty();

// 遍历
for (String key : map.keySet()) { // 遍历key
    System.out.println(key + ": " + map.get(key));
}
for (Map.Entry<String, Integer> entry : map.entrySet()) { // 遍历键值对
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
for (int value : map.values()) { // 遍历value
    System.out.println(value);
}

// TreeMap特有方法
TreeMap<Integer, String> treeMap = new TreeMap<>();
Map.Entry<Integer, String> ceiling = treeMap.ceilingEntry(5); // 大于等于5的最小键
Map.Entry<Integer, String> floor = treeMap.floorEntry(5); // 小于等于5的最大键

9. 实用工具类

Collections 工具类

import java.util.Collections;

// 排序
Collections.sort(list); // 升序排序
Collections.sort(list, Collections.reverseOrder()); // 降序排序
Collections.reverse(list); // 反转列表
Collections.shuffle(list); // 随机打乱

// 查找
int index = Collections.binarySearch(list, key); // 二分查找（必须先排序）
int freq = Collections.frequency(list, element); // 出现次数

// 最值
int max = Collections.max(list);
int min = Collections.min(list);

// 填充与复制
Collections.fill(list, value);
Collections.copy(dest, src);

// 不可变集合
List<Integer> unmodifiableList = Collections.unmodifiableList(list);

StringBuilder

特点：可变字符串，适用于频繁修改字符串的场景。

StringBuilder sb = new StringBuilder();

// 添加内容
sb.append("hello");
sb.append(123);
sb.insert(2, "insert"); // 在指定位置插入

// 删除修改
sb.delete(1, 3); // 删除[1,3)位置的字符
sb.deleteCharAt(0); // 删除指定位置字符
sb.setCharAt(0, 'H'); // 设置指定位置字符

// 其他操作
sb.reverse(); // 反转
int len = sb.length(); // 长度
int cap = sb.capacity(); // 容量
sb.setLength(0); // 清空

// 转换为String
String result = sb.toString();

🎯 算法题中容器选择策略

1. 快速查询：使用 HashSet 或 HashMap（O(1)时间复杂度）
2. 维护顺序：使用 TreeSet 或 TreeMap（O(log n)时间复杂度）
3. 频繁在两端操作：使用 Deque（栈和队列场景）
4. 需要优先级处理：使用 PriorityQueue（堆场景）
5. 普通动态数组：大多数情况下使用 ArrayList
6. 频繁在中间增删：考虑使用 LinkedList

💡 实用技巧

1. 初始化技巧：

   // 快速初始化
   List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
   Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 3));
   Map<String, Integer> map = new HashMap<>() {{
       put("a", 1);
       put("b", 2);
   }};
   

2. 遍历时删除：使用迭代器而不是foreach，避免并发修改异常

   Iterator<Integer> it = list.iterator();
   while (it.hasNext()) {
       if (it.next() == target) {
           it.remove(); // 安全删除
       }
   }
   

3. 数组与集合转换：

   // 列表转数组
   List<String> list = Arrays.asList("a", "b", "c");
   String[] array = list.toArray(new String[0]);
   
   // 数组转列表
   String[] arr = {"a", "b", "c"};
   List<String> list = Arrays.asList(arr);