跳到主要内容

数据结构与算法速查表

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

复杂度速查​

时间复杂度​

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

主定理​

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

情况条件结果
情况一f(n)=O(nlog⁡ba−ϵ)f(n) = O(n^{\log_b a - \epsilon})T(n)=Θ(nlog⁡ba)T(n) = \Theta(n^{\log_b a})
情况二f(n)=Θ(nlog⁡balog⁡kn)f(n) = \Theta(n^{\log_b a} \log^k n)T(n)=Θ(nlog⁡balog⁡k+1n)T(n) = \Theta(n^{\log_b a} \log^{k+1} n)
情况三f(n)=Ω(nlog⁡ba+ϵ)f(n) = \Omega(n^{\log_b a + \epsilon})T(n)=Θ(f(n))T(n) = \Theta(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）​

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

class Trie {
    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = searchNode(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchNode(prefix) != null;
    }

    private TrieNode searchNode(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
}

并查集（Union-Find）​

class UnionFind {
    int[] parent;
    int[] rank;  // 按秩合并优化

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    // 路径压缩查找
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 按秩合并
    void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        if (rank[rootP] > rank[rootQ]) {
            parent[rootQ] = rootP;
        } else if (rank[rootP] < rank[rootQ]) {
            parent[rootP] = rootQ;
        } else {
            parent[rootQ] = rootP;
            rank[rootP]++;
        }
    }

    boolean connected(int p, int q) {
        return find(p) == find(q);
    }
}

排序算法​

算法平均时间最坏时间空间稳定原地
冒泡排序O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)是是
选择排序O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)否是
插入排序O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)是是
归并排序O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(n)O(n)是否
快速排序O(nlog⁡n)O(n \log n)O(n2)O(n^2)O(log⁡n)O(\log n)否是
堆排序O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(1)O(1)否是
// 快速排序
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, int[] temp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid, temp);
    mergeSort(arr, mid + 1, right, temp);
    merge(arr, left, mid, right, temp);
}

void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (i = 0; i < k; i++) arr[left + i] = temp[i];
}

查找算法​

二分查找​

// 标准二分查找（闭区间版本）
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;
}

// lower_bound: 第一个 >= target 的位置
int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;  // 返回第一个 >= target 的位置
}

// upper_bound: 第一个 > target 的位置
int upperBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left;  // 返回第一个 > target 的位置
}

// 查找第一个等于 target 的位置
int findFirst(int[] arr, int target) {
    int i = lowerBound(arr, target);
    return (i < arr.length && arr[i] == target) ? i : -1;
}

// 查找最后一个等于 target 的位置
int findLast(int[] arr, int target) {
    int i = upperBound(arr, target) - 1;
    return (i >= 0 && arr[i] == target) ? i : -1;
}

// 统计 target 出现次数
int count(int[] arr, int target) {
    return upperBound(arr, target) - lowerBound(arr, target);
}

分治算法​

核心步骤​

  1. 分解（Divide）：将原问题分解为若干个规模较小的子问题
  2. 解决（Conquer）：递归求解子问题
  3. 合并（Combine）：合并子问题的解

经典应用​

算法时间复杂度特点
二分查找O(log⁡n)O(\log n)分解和合并都是 O(1)O(1)
归并排序O(nlog⁡n)O(n \log n)合并步骤 O(n)O(n)
快速排序O(nlog⁡n)O(n \log n) 平均分解步骤 O(n)O(n)
快速选择O(n)O(n) 平均找第 k 大元素

动态规划​

核心模式​

// 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];
}

常见 DP 类型​

类型状态定义状态转移
线性 DPdp[i] 表示以 i 结尾的最优解dp[i] = f(dp[j]) 其中 j < i
区间 DPdp[i][j] 表示区间 [i,j] 的最优解dp[i][j] = f(dp[i][k], dp[k+1][j])
背包 DPdp[i][w] 表示前 i 个物品容量 w 的最优解dp[i][w] = max(不选, 选)
树形 DPdp[node][state] 表示以 node 为根的子树的最优解后序遍历合并子树结果

图算法​

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);
        }
    }
}

最短路径​

算法适用场景时间复杂度
BFS无权图O(V+E)O(V + E)
Dijkstra非负权重图O((V+E)log⁡V)O((V + E) \log V)
Bellman-Ford含负权重图O(VE)O(VE)
Floyd-Warshall所有点对最短路径O(V3)O(V^3)

常见问题模式​

双指针​

// 两数之和（有序数组）
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)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);

// 统计 1 的个数
int count = Integer.bitCount(n);

// 快速幂
long pow(long base, int exp) {
    long result = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) result *= base;
        base *= base;
        exp >>= 1;
    }
    return result;
}

数学​

// 最大公约数
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;
}

参考资料​