数据结构与算法速查表

本页面汇总了常用数据结构和算法的核心知识，方便快速查阅。

复杂度速查

时间复杂度

复杂度	名称	典型示例
O(1)	常数阶	数组访问、哈希表查找
O(log n)	对数阶	二分查找、堆操作
O(n)	线性阶	遍历、线性查找
O(n log n)	线性对数阶	快排、归并排序、堆排序
O(n²)	平方阶	冒泡排序、选择排序
O(n³)	立方阶	三层循环
O(2ⁿ)	指数阶	斐波那契递归、子集枚举
O(n!)	阶乘阶	全排列

主定理

T(n) = aT(n/b) + f(n)

• 情况1：f(n) < n^log_b(a) → T(n) = O(n^log_b(a))
• 情况2：f(n) = n^log_b(a) → T(n) = O(n^log_b(a) * log n)
• 情况3：f(n) > n^log_b(a) → T(n) = O(f(n))

数据结构

数组

// 声明和初始化
int[] arr = new int[10];
int[] arr = {1, 2, 3, 4, 5};

// 常用操作
arr.length           // 长度
arr[i]               // 访问 O(1)
Arrays.sort(arr)     // 排序 O(n log n)
Arrays.binarySearch(arr, key)  // 二分查找 O(log n)
Arrays.copyOf(arr, newLength)  // 复制
Arrays.fill(arr, val)          // 填充

链表

// 定义
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

// 反转链表
ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 快慢指针找中点
ListNode middle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

栈

// 使用 Deque 作为栈
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);      // 入栈
stack.pop();        // 出栈
stack.peek();       // 查看栈顶
stack.isEmpty();    // 是否为空

// 单调栈模板（下一个更大元素）
int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

队列

// 普通队列
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);     // 入队
queue.poll();       // 出队
queue.peek();       // 查看队头

// 双端队列
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);  // 头部添加
deque.addLast(2);   // 尾部添加
deque.removeFirst();
deque.removeLast();

// 优先队列（小顶堆）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

哈希表

// HashMap
Map<String, Integer> map = new HashMap<>();
map.put("key", 1);          // 添加
map.get("key");             // 获取
map.getOrDefault("key", 0); // 获取或默认值
map.containsKey("key");     // 是否包含键
map.remove("key");          // 删除
map.keySet();               // 键集合
map.values();               // 值集合
map.entrySet();             // 键值对集合

// HashSet
Set<Integer> set = new HashSet<>();
set.add(1);                 // 添加
set.contains(1);            // 是否包含
set.remove(1);              // 删除

树

// 二叉树节点
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

// 前序遍历
void preorder(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);
    preorder(root.left);
    preorder(root.right);
}

// 中序遍历
void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.println(root.val);
    inorder(root.right);
}

// 后序遍历
void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.val);
}

// 层序遍历
void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

### 字典树 (Trie)
```java
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

并查集 (Union-Find)

class UF {
    int[] parent;
    UF(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union(int p, int q) {
        parent[find(p)] = find(q);
    }
}

## 排序算法

| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 | 原地 |
|------|----------|----------|------|------|------|
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✓ | ✓ |
| 选择排序 | O(n²) | O(n²) | O(1) | ✗ | ✓ |
| 插入排序 | O(n²) | O(n²) | O(1) | ✓ | ✓ |
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✓ | ✗ |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ✗ | ✓ |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ✗ | ✓ |

```java
// 快速排序
void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int p = partition(arr, low, high);
    quickSort(arr, low, p - 1);
    quickSort(arr, p + 1, high);
}

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

// 归并排序
void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

查找算法

二分查找

// 标准二分查找
int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 查找左边界
int leftBound(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) right = mid - 1;
        else left = mid + 1;
    }
    return left < arr.length && arr[left] == target ? left : -1;
}

// 查找右边界
int rightBound(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) left = mid + 1;
        else right = mid - 1;
    }
    return right >= 0 && arr[right] == target ? right : -1;
}

动态规划

核心模式

// 1. 斐波那契
int fib(int n) {
    if (n <= 1) return n;
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

// 2. 最长递增子序列
int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int max = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

// 3. 0-1 背包
int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

图算法

BFS 模板

void bfs(Graph graph, int start) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    
    queue.offer(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        // 处理节点
        
        for (int neighbor : graph.getNeighbors(node)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

DFS 模板

void dfs(Graph graph, int node, Set<Integer> visited) {
    visited.add(node);
    // 处理节点
    
    for (int neighbor : graph.getNeighbors(node)) {
        if (!visited.contains(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}

常见问题模式

双指针

// 两数之和（有序数组）
int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1};
}

// 滑动窗口
int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, minLen = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left++];
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

回溯

// 全排列
List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);
    return result;
}

void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, result);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

Java 集合框架

集合	特点	适用场景
ArrayList	动态数组，随机访问快	频繁查询
LinkedList	双向链表，增删快	频繁增删
HashMap	哈希表，O(1) 查找	键值存储
TreeMap	红黑树，有序	需要排序
HashSet	基于 HashMap	去重
TreeSet	红黑树，有序	有序去重
PriorityQueue	堆实现	优先级队列
ArrayDeque	循环数组	栈/队列

常用技巧

位运算

// 判断奇偶
boolean isOdd = (n & 1) == 1;

// 交换两数
a ^= b; b ^= a; a ^= b;

// 判断 2 的幂
boolean isPowerOfTwo = (n & (n - 1)) == 0;

// 取最低位 1
int lowbit = n & (-n);

数学

// 最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 最小公倍数
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

// 判断质数
boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

参考资源

• LeetCode
• 可视化算法
• 算法导论