数据结构java
一、数据结构与核心操作
1. 数组(Array)
• 核心操作:
• 遍历:for (int num : arr) { ... }
• 快速访问:arr[i]
(时间复杂度 O(1))
• 长度:arr.length
• 排序:Arrays.sort(arr)
(快排,O(n log n))
• 二分查找:Arrays.binarySearch(arr, key)
(需先排序)
2. 字符串(String)
• 核心方法:
• 长度:s.length()
• 转字符数组:s.toCharArray()
(便于修改字符)
• 截取子串:s.substring(start, end)
• 分割:s.split(regex)
• 拼接:用 StringBuilder
(避免频繁创建 String 对象)
3. 动态数组(ArrayList)
• 核心方法:
• 添加元素:list.add(element)
(尾部 O(1),中间 O(n))
• 获取元素:list.get(index)
(O(1))
• 删除元素:list.remove(index)
(O(n))
• 长度:list.size()
4. 链表(LinkedList)
• 核心方法:
• 模拟栈/队列:
◦ 栈:addFirst()
+ removeFirst()
◦ 队列:addLast()
+ removeFirst()
• 常用方法:poll()
, peek()
, offer()
5. 哈希表(HashMap/HashSet)
• 核心操作:
• 快速查找:map.containsKey(key)
(O(1))
• 插入/更新:map.put(key, value)
• 遍历键值对:for (Map.Entry<K,V> entry : map.entrySet())
• 去重:用 HashSet
(set.add(element)
)
6. 堆(PriorityQueue)
• 核心操作:
• 创建:new PriorityQueue<>()
(默认小顶堆)
• 自定义排序:new PriorityQueue<>((a,b) -> b - a)
(大顶堆)
• 插入/弹出:offer(element)
, poll()
(O(log n))
7. 栈(Stack)
• 推荐用 Deque 实现:
Deque<Integer> stack = new LinkedList<>(); |
二、算法高频工具方法
1. 数学工具(Math)
• Math.max(a, b)
, Math.min(a, b)
• Math.abs(x)
:绝对值
• Math.pow(a, b)
:幂运算(返回 double)
2. 数组工具(Arrays)
• 填充值:Arrays.fill(arr, value)
• 复制数组:Arrays.copyOf(arr, newLength)
• 转列表:Arrays.asList(arr)
(返回固定大小的 List)
3. 字符串工具(StringBuilder)
• 高效拼接:
StringBuilder sb = new StringBuilder(); |
三、算法题常见套路
1. 双指针
• 场景:有序数组去重、链表环检测、滑动窗口(子数组/子串问题)
• 模板:
int left = 0, right = 0; |
2. 递归与回溯
• 核心:DFS + 剪枝
• 模板:
void backtrack(路径, 选择列表) { |
3. 动态规划(DP)
• 步骤:
- 定义状态(如
dp[i][j]
表示子问题的解) - 状态转移方程(递推关系)
- 初始化边界条件
- 遍历顺序(自底向上或自顶向下)
4. 树的遍历
• BFS(层序遍历):用队列实现(LinkedList
)
• DFS:递归或栈实现(前序/中序/后序)
四、刷题必备代码模板
快速排序(Quick Sort)
void quickSort(int[] arr, int low, int high) { |
二叉树节点定义
class TreeNode { |
五、高频考点速查表
数据结构 | 典型应用场景 | 时间复杂度关键点 |
---|---|---|
数组 | 双指针、滑动窗口、动态规划 | 随机访问 O(1) |
哈希表 | 快速查找(两数之和、去重) | 插入/查找 O(1) |
堆(优先队列) | Top K 问题、合并有序链表 | 插入/弹出 O(log n) |
栈 | 括号匹配、路径问题、DFS | 入栈/出栈 O(1) |
队列 | BFS、滑动窗口最大值 | 入队/出队 O(1) |
六、注意事项
- 时间/空间复杂度:优先用 O(n) 或 O(n log n) 的算法。
- 边界条件:空数组、单元素、负数、整数溢出等。
- 字符串操作:用
StringBuilder
替代直接拼接(避免 O(n²) 时间)。 - 输入规模:若
n ≤ 10^4
,O(n²) 可能超时;若n ≤ 10^5
,需 O(n) 或 O(n log n)。
掌握这些基础内容后,可以覆盖大多数 LeetCode 简单-中等题!刷题时建议从 数组、字符串、哈希表、双指针 开始,逐步深入。