数据结构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<>();
stack.push(1);     // 入栈
stack.pop();       // 出栈（O(1)）
stack.peek();      // 查看栈顶

二、算法高频工具方法

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();
sb.append("hello");
sb.reverse();       // 反转字符串
String s = sb.toString();

三、算法题常见套路

1. 双指针

• 场景：有序数组去重、链表环检测、滑动窗口（子数组/子串问题）
• 模板：

int left = 0, right = 0;
while (right < n) {
    // 更新窗口状态
    while (窗口需收缩) {
        // 处理 left
        left++;
    }
    right++;
}

2. 递归与回溯

• 核心：DFS + 剪枝
• 模板：

void backtrack(路径, 选择列表) {
    if (终止条件) {
        记录结果;
        return;
    }
    for (选择 : 选择列表) {
        做选择;
        backtrack(路径, 新选择列表);
        撤销选择;
    }
}

3. 动态规划（DP）

• 步骤：

定义状态（如 dp[i][j] 表示子问题的解）
状态转移方程（递推关系）
初始化边界条件
遍历顺序（自底向上或自顶向下）

4. 树的遍历

• BFS（层序遍历）：用队列实现（LinkedList）
• DFS：递归或栈实现（前序/中序/后序）

四、刷题必备代码模板

快速排序（Quick Sort）

void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int pivot = partition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, high);
    return i;
}

二叉树节点定义

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

五、高频考点速查表

数据结构	典型应用场景	时间复杂度关键点
数组	双指针、滑动窗口、动态规划	随机访问 O(1)
哈希表	快速查找（两数之和、去重）	插入/查找 O(1)
堆（优先队列）	Top K 问题、合并有序链表	插入/弹出 O(log n)
栈	括号匹配、路径问题、DFS	入栈/出栈 O(1)
队列	BFS、滑动窗口最大值	入队/出队 O(1)