算法核心数据结构与常用方法速查表

这是一份为Java算法刷题（LeetCode/牛客等）量身定制的核心数据结构与常用方法速查表。

在刷题时，我们不追求API的全面性，而是追求高频、高效、准确。以下按使用频率分类整理：

1. 数组与字符串 (Arrays & Strings)

数组 (Array)

最基础结构，注意它是定长的。

// 初始化
int[] arr = new int[10];
int[] arr2 = {1, 2, 3};
int[][] matrix = new int[m][n]; // 二维数组

// 常用操作
int len = arr.length; // 注意：是属性，不是方法，没有括号()
Arrays.sort(arr); // 排序 O(NlogN)
Arrays.fill(arr, -1); // 填充初始值

字符串 (String)

Java中String是不可变的 (Immutable)，修改需生成新对象。

String s = "Hello World";

// 常用方法
int len = s.length(); // 方法，有括号()
char c = s.charAt(0); // 获取指定位置字符
String sub = s.substring(startIndex, endIndex); // 左闭右开 [start, end)
String sub2 = s.substring(startIndex); // 从start到末尾
boolean has = s.contains("Wor");
int idx = s.indexOf("Wor"); // 找不到返回 -1
char[] chars = s.toCharArray(); // 转为字符数组，方便遍历修改
String[] parts = s.split(","); // 分割
String upper = s.toUpperCase(); // 转大写
boolean isEqual = s.equals("target"); // 必须用equals，不能用==

StringBuilder (可变字符串)

刷题必备，用于频繁修改字符串（如拼接），避免由String不可变性导致的TLE（超时）。

StringBuilder sb = new StringBuilder();

// 常用方法
sb.append("abc"); // 尾部追加
sb.append(123);
sb.reverse(); // 反转字符串 (非常有用！)
sb.deleteCharAt(sb.length() - 1); // 删除最后一个字符 (回溯法常用)
sb.setCharAt(0, 'x'); // 修改指定位置字符
String res = sb.toString(); // 转回String

2. 线性数据结构 (List, Stack, Queue)

动态数组 (ArrayList)

List<Integer> list = new ArrayList<>();

// 常用方法
list.add(10); // 尾部添加
list.add(0, 5); // 指定位置插入
int val = list.get(0); // 获取元素
list.set(0, 99); // 修改元素
list.remove(list.size() - 1); // 删除指定位置元素
list.size(); // 获取长度
boolean isEmpty = list.isEmpty();
boolean has = list.contains(10);
List<Integer> sub = list.subList(0, 2); // 截取，左闭右开
// 列表转数组 (int[]比较麻烦，通常转Integer[])
Integer[] arr = list.toArray(new Integer[0]);

栈 (Stack)

注意： Java官方推荐使用 Deque 接口来实现栈，而不是旧的 Stack 类。

Deque<Integer> stack = new ArrayDeque<>(); 
// 或者 LinkedList 也行，但 ArrayDeque更快
// Deque<Integer> stack = new LinkedList<>();

// 常用方法
stack.push(1); // 入栈
int top = stack.pop(); // 出栈 (并返回元素)
int peek = stack.peek(); // 查看栈顶元素 (不删除)
boolean empty = stack.isEmpty();

队列 (Queue)

通常用于BFS（广度优先搜索）。

Queue<Integer> queue = new LinkedList<>(); 
// ArrayDeque也可以做Queue，但LinkedList更经典

// 常用方法
queue.offer(1); // 入队 (比add安全)
int head = queue.poll(); // 出队 (比remove安全，空时返回null)
int peek = queue.peek(); // 查看队头
int size = queue.size();

双端队列 (Deque)

既能当栈用，也能当队列用，常用于滑动窗口最大值等问题。

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

// 常用方法
deque.offerFirst(1); // 队头添加
deque.offerLast(2);  // 队尾添加 (等同于 offer)
deque.pollFirst();   // 队头移除 (等同于 poll)
deque.pollLast();    // 队尾移除
deque.peekFirst();
deque.peekLast();

3. 哈希表与集合 (Map & Set)

哈希表 (HashMap)

刷题神器，O(1) 查找。

Map<String, Integer> map = new HashMap<>();

// 常用方法
map.put("key", 1);
int val = map.get("key"); // 如果key不存在，可能报NPE，建议用getOrDefault
int valSafe = map.getOrDefault("key", 0); // **非常常用**：存在返值，不存在返0
boolean hasKey = map.containsKey("key");
map.remove("key");

// 遍历 (熟练掌握 entrySet)
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String k = entry.getKey();
    Integer v = entry.getValue();
}
// 或者只遍历key
for (String key : map.keySet()) {}

集合 (HashSet)

用于去重。

Set<Integer> set = new HashSet<>();

// 常用方法
set.add(1); // 添加成功返回true，重复返回false
set.remove(1);
boolean has = set.contains(1);
set.size();

4. 树与堆 (Tree & Heap)

优先队列 / 堆 (PriorityQueue)

默认是小顶堆 (Min Heap)。常用于 Top K 问题。

// 默认小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 大顶堆 (Max Heap) - 需要传入 Comparator
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

// 常用方法
minHeap.offer(10); // 入堆
int top = minHeap.poll(); // 弹出堆顶
int peek = minHeap.peek(); // 查看堆顶

5. 实用的工具类 (Utils)

Collections 工具类

针对 List 集合的操作。

Collections.sort(list); // 排序 (默认升序)
Collections.sort(list, (a, b) -> b - a); // 降序排序
Collections.reverse(list); // 反转
Collections.max(list); // 取最大值
Collections.swap(list, i, j); // 交换位置

类型转换 (常见的坑)

刷题时经常需要在 String, char, int 之间转换。

// char -> int
char c = '5';
int num = c - '0'; // 利用ASCII码差值，最快方式

// int -> String
String s = String.valueOf(123);

// String -> int
int n = Integer.parseInt("123");

// 数组转List
List<String> list = Arrays.asList("a", "b", "c"); // 生成的list定长，不能add/remove
// 如果需要修改，需包装一层：
List<String> modifiableList = new ArrayList<>(Arrays.asList("a", "b"));

大数处理 (BigInteger)

用于处理超过 long 范围的整数运算。

import java.math.BigInteger;
BigInteger a = new BigInteger("12345678901234567890");
BigInteger b = new BigInteger("98765432109876543210");
BigInteger sum = a.add(b);      // 加
BigInteger diff = a.subtract(b); // 减
BigInteger prod = a.multiply(b); // 乘
BigInteger quot = a.divide(b);   // 除

Note:

Length vs Size:
- 数组 ([]) 用 .length (属性)。
- 字符串 (String) 用 .length() (方法)。
- 集合 (List, Set, Map) 用 .size() (方法)。
判空: 永远先判断 != null (如果可能为null) 和 !isEmpty()。在Stack/Queue操作前务必检查 isEmpty()。
比较: 对象类型（String, Integer等）比较内容一定要用 .equals()，基本类型（int, char）用 ==。
Map的默认值: 统计频率时，map.put(key, map.getOrDefault(key, 0) + 1);

Dango