Java常用数据结构与方法

Java 常用类与算法函数介绍

本文档聚焦”函数的解释说明”：每个方法都给出 作用 / 签名 / 返回值 / 时间复杂度 / 易错点 / 示例。

---

一、数组与Arrays工具类

本节讲 Arrays 工具类；先明确数组类型本身：

数组类型基础（int[] / 二维数组）：

语法	说明	易错点
int[] a = new int[n];	定长数组，元素默认 0	n 必须 ≥ 0，否则抛 NegativeArraySizeException
int[] a = {1,2,3};	声明同时初始化	仅能在声明时用，不能 a = {1,2};
int[][] g = new int[m][n];	二维数组（每行列数相同）	默认全 0；g.length=m，g[i].length=n
int[][] g = new int[m][];	不规则（锯齿）二维数组	须再 for(i) g[i]=new int[...];，否则 g[i] 为 null
a[i]	按下标访问	越界抛 ArrayIndexOutOfBoundsException；下标从 0 开始
a.length	字段（不是方法！）	与 String.length() 区分；二维用 a[i].length
for (int x : a)	增强 for 遍历（只读）	需修改元素时用普通 for + 下标
for (int i=0;i<a.length;i++)	带下标遍历	最常用，可边遍历边修改

数组元素默认值（决定要不要手动初始化）：

• new int[] / long[] / double[] → 0 / 0L / 0.0
• new boolean[] → false
• 引用类型数组（String[]、List[] 等）→ null

注意：Arrays.fill 填充二维数组只会复制同一个一维数组的引用（各行指向同一对象）；需要各行独立时必须逐行 new int[n]。

方法	作用	复杂度	易错点
Arrays.sort(a)	对数组原地排序（基本类型用快排变体；对象用 TimSort）	O(n log n)	基本类型排序不稳定；a 会被直接修改
Arrays.sort(a, (x,y)->x-y)	自定义比较器排序（升序）	O(n log n)	x-y 在差值超 int 范围时可能溢出，超大数用 Integer.compare(x,y)
Arrays.binarySearch(a, key)	在已排序数组中二分查找	O(log n)	数组必须先排序，否则结果未定义；找不到返回负数插入点
Arrays.fill(a, val)	用 val 填充整个数组	O(n)	二维数组 fill 只会复制同一引用，行会共享（坑！）
Arrays.copyOf(a, newLen)	拷贝数组，可截断/扩容	O(n)	新长度 > 原长时多余位置填 0/null
Arrays.copyOfRange(a, from, to)	拷贝 [from, to) 区间	O(to-from)	右边界是开区间
Arrays.equals(a, b)	比较两数组内容是否相等	O(n)	别用 a == b（比的是引用）
Arrays.toString(a)	数组转可读字符串（调试用）	O(n)	多维数组要用 Arrays.deepToString
Arrays.asList(arr)	数组转 List（固定大小）	O(1) 视图	返回的 List 不能 add/remove，否则抛 UnsupportedOperationException

int[] a = {3,1,2};
Arrays.sort(a);                       // a = [1,2,3]
int p = Arrays.binarySearch(a, 2);    // p = 1
int[] b = Arrays.copyOf(a, 5);        // b = [1,2,3,0,0]
boolean eq = Arrays.equals(a, b);      // false

---

二、String（不可变字符串）

关键认知：String 对象不可变，任何”修改”都返回新对象，原串不变。

方法	作用	复杂度	易错点
s.length()	返回字符数（是方法不是字段）	O(1)	别写成 s.length（那是数组的字段）
s.charAt(i)	取第 i 个字符	O(1)	i 越界抛 StringIndexOutOfBoundsException
s.substring(l, r)	截取 [l, r) 子串	O(r-l)	右边界开区间；r 最大为 length()
s.indexOf("x") / lastIndexOf	首次/末次出现位置	O(n)	找不到返回 -1（常用 != -1 判断存在）
s.toCharArray()	转 char[] 便于按索引修改	O(n)	改完用 new String(char[]) 转回
s.split(" ")	按正则分割	O(n)	按 . 等正则元字符要转义 split("\\.")；末尾空串会被丢弃
s.replace(a, b) / replaceAll	替换（前者按字面，后者按正则）	O(n)	replace 不是正则；想用正则才用 replaceAll
s.trim()	去首尾空白	O(n)	中间空格不动；不修改原串
s.contains("x")	是否包含子串	O(n)	—
s.equals(t) / equalsIgnoreCase	内容比较	O(n)	永远用 equals，绝不用 ==
s.compareTo(t)	字典序比较（<0 小于）	O(n)	用于排序
s.startsWith/endsWith	前缀/后缀判断	O(n)	—
s.isEmpty()	长度是否为 0	O(1)	null 调用会 NPE

---

三、StringBuilder（可变字符串）

方法	作用	易错点
append(x)	尾部追加（任意类型）	链式调用 sb.append(a).append(b)
insert(i, x)	在 i 处插入	会改变后续索引
delete(l, r) / deleteCharAt(i)	删除区间/单字符	区间左闭右开
replace(l, r, s)	替换区间内容	—
reverse()	反转	原地修改，返回自身
setCharAt(i, c)	改指定位置字符	—
setLength(0)	清空复用（避免反复 new）	—
toString()	转成 String	最终输出用
length() / capacity()	当前长度 / 内部容量	容量自动扩容，无需关心

StringBuilder sb = new StringBuilder();
sb.append("ab").append(123);   // "ab123"
sb.reverse();                  // "321ba"
String r = sb.toString();

---

四、List（以 ArrayList 为主）

方法	作用	复杂度	易错点
add(e)	尾部追加	O(1) 均摊	超容量时扩容为 1.5 倍
add(i, e)	在 i 处插入	O(n)	后续元素后移
get(i) / set(i, e)	取 / 改第 i 个	O(1)	越界抛异常
remove(i) / remove(o)	按下标 / 按对象删除	O(n)	注意重载：remove(1) 删下标1，remove(Integer.valueOf(1)) 删值为1的元素
contains(o) / indexOf(o)	是否包含 / 首次下标	O(n)	对象比较用 equals
size() / isEmpty()	大小 / 空判断	O(1)	—
clear()	清空	O(n)	—
toArray()	转 Object[]	O(n)	转 Integer[] 用 list.toArray(new Integer[0])
sort(cmp)	原地排序	O(n log n)	list.sort((a,b)->a-b)
subList(l, r)	返回原表的视图	O(1)	改子列表会影响原表；不能套 Arrays.sort

---

五、Set（HashSet 哈希集 / TreeSet 有序集）

方法	作用	复杂度	易错点
add(e)	加入（已存在则忽略）	O(1) 均摊	去重核心
contains(e)	是否包含	O(1)	比 List 的 contains 快得多
remove(e)	删除	O(1)	—
size() / isEmpty()	大小 / 空	O(1)	—
TreeSet 专有：first()/last()	最小 / 最大元素	O(log n)	空集调用抛 NoSuchElementException
TreeSet 专有：ceiling(k)/floor(k)	>=k 的最小 / <=k 的最大	O(log n)	找不到返回 null
TreeSet 专有：higher(k)/lower(k)	>k 的最小 / <k 的最大	O(log n)	—

Set<Integer> set = new HashSet<>();
set.add(1); set.add(1);   // size 仍为 1（自动去重）
boolean has = set.contains(1); // true

---

六、Map（HashMap 为主）

方法	作用	复杂度	易错点
put(k, v)	存入键值对（覆盖旧值）	O(1)	返回旧值（没有则返回 null）
get(k)	取值	O(1)	未命中返回 null，直接拆箱可能 NPE
getOrDefault(k, d)	取不到返回默认值 d	O(1)	计数场景首选，避免 NPE
containsKey(k)	是否含键	O(1)	别用 map.get(k) != null 判断（值本身可能就是 null）
remove(k)	删键	O(1)	返回被删的值
putIfAbsent(k, v)	键不存在才放	O(1)	常用于首次初始化
computeIfAbsent(k, f)	键不存在时用 f(k) 计算并存入	O(1)	建邻接表/分组极方便：map.computeIfAbsent(k, x->new ArrayList<>()).add(v)
merge(k, v, fn)	合并（键存在用 fn 处理）	O(1)	计数：map.merge(k, 1, Integer::sum)
keySet()/values()/entrySet()	键/值/键值对集合	O(1) 视图	遍历用 entrySet() 最高效
forEach((k,v)->{})	遍历	O(n)	—
size() / isEmpty() / clear()	大小 / 空 / 清空	O(1)	—

Map<String, Integer> map = new HashMap<>();
map.put("a", map.getOrDefault("a", 0) + 1);   // 计数
map.computeIfAbsent("g1", k -> new ArrayList<>()).add(10); // 分组
map.merge("b", 1, Integer::sum);              // 累加
for (Map.Entry<String, Integer> e : map.entrySet()) {  // 高效遍历
    System.out.println(e.getKey() + ":" + e.getValue());
}

---

七、Deque（ArrayDeque，栈和队列）

推荐统一用 ArrayDeque 替代旧类 Stack 和 LinkedList 做栈/队列，性能更好。Deque 接口继承自 Queue，因此一个 ArrayDeque 既是队列也是栈，并且能在两端任意增删查——这才是”双端队列”名字的由来。

当栈用（LIFO）：

方法	作用	等价旧 Stack	空时行为
push(e)	入栈	addFirst	—
pop()	出栈（删并返回）	removeFirst	抛 NoSuchElementException
peek()	看栈顶不删	peekFirst	返回 null（不抛异常）
isEmpty()	判空	—	优先用它判断栈空，别用 pop()!=null
size()	元素个数	—	—

易错：pop() 在空栈上会抛异常，而 peek() 返回 null；循环条件一律用 while (!st.isEmpty())，避免空栈 NPE/异常。

当队列用（FIFO）：

方法	作用	易错点
offer(e)	入队	比 add 安全（满时返回 false 而非抛异常）
poll()	出队（删并返回）	空队列返回 null（别对 null 拆箱）
peek()	看队首不删	空队列返回 null
isEmpty()	判空	用 isEmpty 判断，别用 poll()!=null 当循环条件（会丢元素）
size()	元素个数	取当前元素数（O(1)）；BFS 层序遍历常先 int sz = q.size() 再循环 sz 次逐个 poll

栈 / 队列怎么区分”首””尾”（初学时极易混，先记这张表）：

结构	有几个开口	进 / 出分别在哪	首尾叫法
栈 Stack（LIFO）	只有 1 个开口	入栈 push 和出栈 pop 都在这同一个开口（栈顶），后进先出	没有”头/尾”之分，只有栈顶（top）
队列 Queue（FIFO）	有 2 个开口（一头进、一头出）	入队 offer 在队尾，出队 poll 在队首	出队端叫队首（head / first），入队端叫队尾（tail / last）
双端队列 Deque	2 个开口，两端都能进能出	offerFirst/offerLast、pollFirst/pollLast 两端自由	first=首，last=尾；offer=offerLast，poll=pollFirst

直观示意：

栈（只有 1 个口）：        队列（2 个口）：              双端队列（两端都能用）：
     ↑ 栈顶                   队尾 → [..] → 队首            首 ← [..] → 尾
 push / pop 都在这                                offerLast 入 / pollFirst 出

关键认知：ArrayDeque 的”栈顶”和”队列的队首”是同一个物理端（都是 first 端）——push=addFirst、pop=removeFirst、poll=pollFirst。所以一个 ArrayDeque 既能当栈又能当队列，互不冲突。记住一句：栈操作看”顶”，队列操作看”尾进、首出”。

Queue 接口的完整方法对（重点：抛异常 vs 返回特殊值）：
Deque 作为队列时实现的是 Queue 接口，每类操作都有”抛异常”与”返回特殊值”两种版本：

操作	抛异常版本	返回特殊值版本	说明
入队	add(e)	offer(e)	队列通常无界，add 也能用；offer 在容量受限时返回 false 更安全
出队（删头）	remove()	poll()	空队列时 remove() 抛 NoSuchElementException，poll() 返回 null
查看队首（不删）	element()	peek()	空队列时 element() 抛异常，peek() 返回 null
判空 / 大小	isEmpty()	size()	isEmpty() 优先用于循环条件判断

易错核心：poll()/peek() 为空返回 null，直接拆箱（如 int x = q.poll() 当元素是 Integer 时）会 NPE；remove()/element() 为空直接抛异常。优先用 offer/poll/peek + isEmpty 组合，行为最可预测。

Deque<Integer> st = new ArrayDeque<>();
st.push(1); st.push(2);
int top = st.pop();   // 2

Deque<Integer> q = new ArrayDeque<>();
q.offer(1); q.offer(2);
while (!q.isEmpty()) { int x = q.poll(); }  // 1, 2

双端队列的本职能力（两端都能操作）：
上面”栈”和”队列”只是 Deque 的两种特殊用法。Deque 真正的价值是两端均可增删查——Queue 接口只提供”队尾进、队首出”（offer / poll / peek），而 Deque 额外提供 First / Last 系列方法：

操作位置	添加（入）	删除并返回（出）	仅查看（不删）
队首（head / 头）	addFirst(e) / offerFirst(e)	removeFirst() / pollFirst()	getFirst() / peekFirst()
队尾（tail / 尾）	addLast(e) / offerLast(e)	removeLast() / pollLast()	getLast() / peekLast()

要点：

• addXxx：容量受限时抛异常；offerXxx：容量受限时返回 false（ArrayDeque 无容量上限，二者等价，习惯用 offerXxx）。
• removeXxx：为空时抛 NoSuchElementException；pollXxx：为空时返回 null（推荐用 pollXxx，避免异常）。
• getXxx：为空时抛异常；peekXxx：为空时返回 null。
• 前面”栈/队列”的方法是简写：push(e)=addFirst(e)、pop()=removeFirst()、peek()=peekFirst()；offer(e)=offerLast(e)、poll()=pollFirst()。

体现”双端”的典型场景（如单调队列、滑动窗口最大值要从尾部淘汰旧元素）：

Deque<Integer> dq = new ArrayDeque<>();
dq.offerLast(1);    // 队尾入 -> [1]
dq.offerLast(2);    // 队尾入 -> [1,2]
dq.offerFirst(0);   // 队头入 -> [0,1,2]
int h = dq.pollFirst();  // 0（队头出）
int t = dq.pollLast();   // 2（队尾出）
int p = dq.peekFirst();  // 1（看队头不删）
// 也能从队尾取：dq.pollLast() / 看队尾：dq.peekLast()

---

八、PriorityQueue（堆）

方法	作用	易错点
offer(e) / add(e)	入堆	O(log n)
poll()	弹出堆顶（最小/最大）	O(log n)；空队列返回 null
peek()	看堆顶不删	O(1)；空返回 null
size() / isEmpty()	大小 / 空	—
构造 new PriorityQueue<>()	默认小根堆（队首最小）	要大根堆必须传比较器 (a,b)->b-a
构造 new PriorityQueue<>(k, cmp)	指定初始容量与比较器	—

// 求数组中最小的 k 个数：用大根堆维护
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a);
for (int x : arr) {
    pq.offer(x);
    if (pq.size() > k) pq.poll();  // 弹走最大的，留下最小的 k 个
}

---

九、Math（静态数学方法）

方法	作用	注意
Math.abs(x)	绝对值	Integer.MIN_VALUE 取绝对值仍溢出（仍是负值），注意边界
Math.max(a,b) / Math.min(a,b)	最大/最小	重载支持 int/long/float/double
Math.sqrt(x)	平方根（返回 double）	取整 (int)Math.sqrt(x)
Math.pow(a, b)	a 的 b 次幂（double）	整数幂慎用，可能有精度误差
Math.floor/ceil/round	向下/向上取整 / 四舍五入	round 返回 long
Math.random()	[0,1) 随机 double	左闭右开
Math.signum(x)	符号：-1/0/1	—

---

十、Collections（集合工具类）

方法	作用	易错点
Collections.sort(list) / sort(list, cmp)	排序（与 list.sort 类似）	对 List 用，不是数组
Collections.reverse(list)	反转	原地修改
Collections.shuffle(list)	随机打乱	抽样/随机化用
Collections.max/min(list)	最大/最小元素	—
Collections.binarySearch(list, key)	二分查找（需先排序）	返回下标
Collections.frequency(c, o)	出现次数	O(n)
Collections.unmodifiableList(list)	返回不可修改视图	防误改，原表改了视图也变
Collections.singletonList(e)	单元素不可变 List	—

---

十一、比较器：Comparator 与 Comparable

两种排序约定方式：

1. Comparable：类自身实现 compareTo（自然序），如 Integer、String 已实现。
2. Comparator：外部比较器，不修改原类，临时指定规则。

// 升序：a 在前返回负数
(a, b) -> a - b
// 降序
(a, b) -> b - a
// 按对象字段：先按 age 升序，再按 name
(x, y) -> {
    if (x.age != y.age) return x.age - y.age;
    return x.name.compareTo(y.name);
}
// 多字段推荐用 comparing + thenComparing（清晰不易错）
list.sort(Comparator.comparing((Person p) -> p.age)
                    .thenComparing(p -> p.name));

易错点：比较器返回值只需保证”负/零/正”的符号正确，未必是 -1/0/1；但当差值可能超出 int 范围（如两个大 long 相减），用 Integer.compare(a,b) / Long.compare(a,b) 避免溢出。

---

十二、算法”函数”使用说明

套路	核心操作	说明
二分查找	mid = l + (r-l)/2；根据 a[mid] 与 target 比调整 l/r	防溢出必须写 l + (r-l)/2 而非 (l+r)/2
快排 partition	选 pivot = a[r]，遍历把 <pivot 的换到左侧，最后把 pivot 归位	返回 pivot 最终下标，用于分治
回溯	做选择 → 递归 → 撤销选择	全局状态（path/used）递归后必须还原，否则污染后续分支
BFS	队列 + 入队标记 visited + 每层取 size	用 !q.isEmpty() 判循环；层序遍历先取 size
滑动窗口	右指针扩张 + while 收缩左指针	收缩条件根据题意写；用 right-left+1 算窗口大小
前缀和	pre[i+1] = pre[i] + a[i]，区间和 pre[r+1]-pre[l]	下标偏移 1，避免边界判断
单调栈	维护”递增/递减”栈，破序时弹栈处理	栈内存的是下标（方便算距离），不是值
并查集	find 带路径压缩，union 按秩合并	find 返回值相等即连通；union 返回 false 说明已有环
动态规划	定义 dp[i] 含义 + 状态转移 + 初始化 + 遍历顺序	0/1 背包容量必须逆序遍历，完全背包才正序

---

十三、包装类、类型转换与 Character

Integer / Long 常用静态方法：

方法	作用	易错点
Integer.parseInt("123")	字符串转 int	非法字符或溢出抛异常；null 时 NPE
Long.parseLong("123")	字符串转 long	大数优先用 long 防溢出
Integer.valueOf("123")	转 Integer（带缓存）	与 parseInt 区别在返回类型（对象 vs 基本类型）
Integer.toString(123) / String.valueOf(123)	数字转字符串	String.valueOf 可接任意类型，null 会返回 "null"，注意区分
Integer.MAX_VALUE / Integer.MIN_VALUE	int 最大/最小值	初始化极值用，如 int min = Integer.MAX_VALUE
Integer.compare(a, b)	安全比较（防减法溢出）	大数比较用这个，别用 a - b
Integer.bitCount(x) / highestOneBit(x)	位运算辅助	部分位操作题用

自动装箱 / 拆箱与缓存坑：

• int 与 Integer 自动转换（装箱/拆箱）；Integer 为 null 时拆箱会 NPE。
• Integer 缓存范围 -128~127：此范围内 Integer.valueOf(1) == Integer.valueOf(1) 为 true，超出则为 false。比较内容永远用 equals，不要依赖 ==。

char 与 int 的相互转换（字符串数字处理常用）：

char c = '7';
int d = c - '0';                 // 字符数字转 int：d = 7
int code = (int) c;              // 取 Unicode 码点
char up = (char) ('a' - 32);    // 'A'（更推荐用下面的 Character 方法）

Character 类方法（逐字符处理字符串时必用）：

方法	作用
Character.isDigit(c)	是否数字 0-9
Character.isLetter(c)	是否字母
Character.isLetterOrDigit(c)	是否字母或数字
Character.isWhitespace(c)	是否空白符
Character.toLowerCase(c) / toUpperCase(c)	大小写转换

for (char c : s.toCharArray()) {
    if (Character.isLetterOrDigit(c)) { /* 处理 */ }
}

String 其它转换方法：

• String.valueOf(x)：任意类型转字符串（null 返回 "null"）。
• String.join("-", list)：用分隔符拼接集合/数组（Java 8 起）。

BigInteger（数值会超 long 范围的大数题，如阶乘、大数相加）：

BigInteger a = BigInteger.valueOf(100);                    // 从 long 构造
BigInteger b = new BigInteger("123456789012345678901234567890");
BigInteger sum = a.add(b);                                  // 加
BigInteger prod = a.multiply(b);                            // 乘
BigInteger mod = a.mod(BigInteger.valueOf(7));              // 取模
String s = a.toString();

普通题别用（慢），只有数值明确会超 long 范围时才上 BigInteger / BigDecimal。

---

十四、速记口诀

• 数组用 Arrays.sort/fill/copyOf/binarySearch（注意先排序再二分）。
• 字符串不可变，改就用 StringBuilder；判等用 equals。
• List 增删慢查慢，Set/Map 查快，去重计数首选 HashSet/HashMap。
• 栈队列统一 ArrayDeque；堆默认小根堆。
• 比较用 Comparator，差值大用 Integer.compare 防溢出。
• 二分中点永远 l + (r-l)/2。