数据结构与算法笔试核心知识点详解

前言

数据结构与算法是计算机科学的核心基础，也是技术笔试面试中的必考内容。本文将系统梳理链表、树、图、哈希表、排序算法等核心知识点，结合典型面试题型进行深入解析，帮助读者全面掌握笔试必备技能。

第一章：链表（Linked List）

1.1 链表基础概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指针域。相比数组，链表具有动态扩容、插入删除高效的优势。

1.1.1 链表分类

单链表（Singly Linked List）

  • 每个节点只有一个指向下一节点的指针
  • 只能单向遍历
  • 结构简单，内存占用少

双链表（Doubly Linked List）

  • 每个节点有两个指针：prev和next
  • 支持双向遍历
  • 插入删除操作更灵活

循环链表（Circular Linked List）

  • 尾节点指针指向头节点
  • 可以循环遍历
  • 常用于实现队列等数据结构

1.2 链表核心操作

1.2.1 单链表节点定义

1
2
3
4
5
6
7
8
9
class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

1.2.2 链表反转（经典面试题）

迭代法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    
    return prev;
}

递归法实现：

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode reversed = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    
    return reversed;
}

1.2.3 链表环检测（快慢指针法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    
    ListNode slow = head;
    ListNode fast = head.next;
    
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return true;
}

// 找到环的入口
public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    // 检测是否有环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            break;
        }
    }
    
    if (fast == null || fast.next == null) {
        return null;
    }
    
    // 找到环入口
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;
}

1.2.4 合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

1.3 链表高频面试题

  1. 删除链表的倒数第N个节点
  2. 链表的中间节点
  3. 回文链表判断
  4. 链表相交节点查找
  5. 复杂链表的复制

第二章：树结构（Tree）

2.1 树结构基础概念

树是一种非线性数据结构，由节点和边组成，具有层次关系。在计算机科学中广泛应用，如文件系统、数据库索引等。

2.1.1 二叉树分类

二叉树（Binary Tree）

  • 每个节点最多有两个子节点
  • 子节点分为左孩子和右孩子

二叉搜索树（BST）

  • 左子树所有节点值小于根节点值
  • 右子树所有节点值大于根节点值
  • 中序遍历结果为有序序列

平衡二叉树（AVL Tree）

  • 任意节点的左右子树高度差不超过1
  • 通过旋转操作保持平衡
  • 查找、插入、删除时间复杂度O(log n)

2.1.2 二叉树节点定义

1
2
3
4
5
6
7
8
9
10
11
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

2.2 二叉树遍历算法

2.2.1 前序遍历（根-左-右）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 递归实现
public void preorderTraversal(TreeNode root) {
    if (root == null) return;
    
    System.out.print(root.val + " ");
    preorderTraversal(root.left);
    preorderTraversal(root.right);
}

// 迭代实现
public List<Integer> preorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    
    return result;
}

2.2.2 中序遍历（左-根-右）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 递归实现
public void inorderTraversal(TreeNode root) {
    if (root == null) return;
    
    inorderTraversal(root.left);
    System.out.print(root.val + " ");
    inorderTraversal(root.right);
}

// 迭代实现
public List<Integer> inorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    
    return result;
}

2.2.3 后序遍历（左-右-根）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 递归实现
public void postorderTraversal(TreeNode root) {
    if (root == null) return;
    
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    System.out.print(root.val + " ");
}

// 迭代实现（双栈法）
public List<Integer> postorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        
        if (node.left != null) {
            stack1.push(node.left);
        }
        if (node.right != null) {
            stack1.push(node.right);
        }
    }
    
    while (!stack2.isEmpty()) {
        result.add(stack2.pop().val);
    }
    
    return result;
}

2.3 二叉搜索树操作

2.3.1 插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    
    return root;
}

2.3.2 查找操作

1
2
3
4
5
6
7
8
9
10
11
public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || root.val == val) {
        return root;
    }
    
    if (val < root.val) {
        return searchBST(root.left, val);
    } else {
        return searchBST(root.right, val);
    }
}

2.4 平衡二叉树（AVL Tree）

2.4.1 AVL树节点定义

1
2
3
4
5
6
7
8
9
10
11
12
13
class AVLTreeNode {
    int val;
    int height;
    AVLTreeNode left;
    AVLTreeNode right;
    
    AVLTreeNode(int val) {
        this.val = val;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
}

2.4.2 旋转操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 右旋
private AVLTreeNode rightRotate(AVLTreeNode y) {
    AVLTreeNode x = y.left;
    AVLTreeNode T2 = x.right;
    
    // 执行旋转
    x.right = y;
    y.left = T2;
    
    // 更新高度
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    
    return x;
}

// 左旋
private AVLTreeNode leftRotate(AVLTreeNode x) {
    AVLTreeNode y = x.right;
    AVLTreeNode T2 = y.left;
    
    // 执行旋转
    y.left = x;
    x.right = T2;
    
    // 更新高度
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    
    return y;
}

private int getHeight(AVLTreeNode node) {
    return (node == null) ? 0 : node.height;
}

private int getBalance(AVLTreeNode node) {
    return (node == null) ? 0 : getHeight(node.left) - getHeight(node.right);
}

2.5 B树与B+树

2.5.1 B树特点

  • 多路平衡查找树
  • 每个节点可以有多个子节点
  • 所有叶子节点在同一层
  • 常用于文件系统和数据库索引

2.5.2 B+树特点

  • B树的变种，所有数据存储在叶子节点
  • 叶子节点通过指针连接，支持顺序访问
  • 非叶子节点只存储索引信息
  • 更适合范围查询和磁盘存储

2.5.3 B树与B+树对比

特性 B树 B+树
数据存储 所有节点 仅叶子节点
范围查询 效率低 效率高
磁盘IO 较多 较少
应用场景 内存存储 磁盘存储

第三章：图结构（Graph）

3.1 图基础概念

图是由顶点（Vertex）和边（Edge）组成的非线性数据结构，用于表示对象之间的关系。

3.1.1 图分类

无向图（Undirected Graph）

  • 边没有方向
  • 边表示双向关系

有向图（Directed Graph）

  • 边有方向
  • 边表示单向关系

加权图（Weighted Graph）

  • 边带有权重值
  • 表示关系的强度或成本

3.2 图的表示方法

3.2.1 邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class GraphAdjMatrix {
    private int[][] adjMatrix;
    private int numVertices;
    
    public GraphAdjMatrix(int numVertices) {
        this.numVertices = numVertices;
        this.adjMatrix = new int[numVertices][numVertices];
    }
    
    public void addEdge(int i, int j) {
        adjMatrix[i][j] = 1;
        adjMatrix[j][i] = 1; // 无向图
    }
    
    public void removeEdge(int i, int j) {
        adjMatrix[i][j] = 0;
        adjMatrix[j][i] = 0;
    }
    
    public boolean isEdge(int i, int j) {
        return adjMatrix[i][j] == 1;
    }
}

3.2.2 邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

class GraphAdjList {
    private Map<Integer, List<Integer>> adjList;
    
    public GraphAdjList() {
        adjList = new HashMap<>();
    }
    
    public void addVertex(int vertex) {
        adjList.put(vertex, new ArrayList<>());
    }
    
    public void addEdge(int src, int dest) {
        adjList.computeIfAbsent(src, k -> new ArrayList<>()).add(dest);
        adjList.computeIfAbsent(dest, k -> new ArrayList<>()).add(src); // 无向图
    }
    
    public List<Integer> getNeighbors(int vertex) {
        return adjList.getOrDefault(vertex, new ArrayList<>());
    }
}

3.3 图遍历算法

3.3.1 深度优先搜索（DFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class DFS {
    private boolean[] visited;
    
    public void dfs(GraphAdjList graph, int start) {
        visited = new boolean[graph.size()];
        dfsHelper(graph, start);
    }
    
    private void dfsHelper(GraphAdjList graph, int vertex) {
        visited[vertex] = true;
        System.out.print(vertex + " ");
        
        for (int neighbor : graph.getNeighbors(vertex)) {
            if (!visited[neighbor]) {
                dfsHelper(graph, neighbor);
            }
        }
    }
}

// 使用栈的迭代实现
public void dfsIterative(GraphAdjList graph, int start) {
    boolean[] visited = new boolean[graph.size()];
    Stack<Integer> stack = new Stack<>();
    
    stack.push(start);
    
    while (!stack.isEmpty()) {
        int vertex = stack.pop();
        
        if (!visited[vertex]) {
            visited[vertex] = true;
            System.out.print(vertex + " ");
            
            // 逆序压栈，保证顺序访问
            List<Integer> neighbors = graph.getNeighbors(vertex);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int neighbor = neighbors.get(i);
                if (!visited[neighbor]) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

3.3.2 广度优先搜索（BFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class BFS {
    public void bfs(GraphAdjList graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> queue = new LinkedList<>();
        
        visited[start] = true;
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");
            
            for (int neighbor : graph.getNeighbors(vertex)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }
}

3.4 最短路径算法

3.4.1 Dijkstra算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Dijkstra {
    public int[] dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        for (int i = 0; i < n - 1; i++) {
            int u = findMinDistance(dist, visited);
            visited[u] = true;
            
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0 && 
                    dist[u] != Integer.MAX_VALUE && 
                    dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
        
        return dist;
    }
    
    private int findMinDistance(int[] dist, boolean[] visited) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;
        
        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] <= min) {
                min = dist[i];
                minIndex = i;
            }
        }
        
        return minIndex;
    }
}

第四章：哈希表（Hash Table）

4.1 哈希表基础概念

哈希表通过哈希函数将键映射到数组索引，实现O(1)时间复杂度的查找、插入和删除操作。

4.1.1 哈希函数设计原则

  1. 确定性：相同输入产生相同输出
  2. 高效性：计算速度快
  3. 均匀性：均匀分布，减少冲突
  4. 雪崩效应：输入微小变化导致输出巨大变化

4.1.2 冲突解决方法

链地址法（Separate Chaining）

  • 每个桶使用链表存储冲突元素
  • 简单实现，动态扩容容易
  • 内存利用率较低

开放地址法（Open Addressing）

  • 冲突时寻找下一个可用位置
  • 包括线性探测、二次探测、双重哈希
  • 内存利用率高，但删除操作复杂

4.2 Java中的哈希表实现

4.2.1 HashMap源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// HashMap核心结构
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    // 默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
    
    // 默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 链表转红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;
    
    // 红黑树转链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    
    // 最小树化容量
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    // 核心数据结构
    transient Node<K,V>[] table;
    
    // 节点定义
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}

4.2.2 ConcurrentHashMap线程安全实现

JDK 1.7实现：分段锁

  • 将数据分成多个段（Segment）
  • 每个段相当于小的HashMap
  • 不同段可以并发操作

JDK 1.8实现：CAS + synchronized

  • 使用CAS操作保证线程安全
  • 链表长度超过8时转为红黑树
  • 性能更优，并发度更高
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// ConcurrentHashMap核心方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

4.3 哈希冲突解决策略详解

4.3.1 链地址法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public class ChainingHashMap<K, V> {
    private static final int INITIAL_CAPACITY = 16;
    private static final float LOAD_FACTOR = 0.75f;
    
    private Node<K, V>[] table;
    private int size;
    private int threshold;
    
    @SuppressWarnings("unchecked")
    public ChainingHashMap() {
        table = (Node<K, V>[]) new Node[INITIAL_CAPACITY];
        threshold = (int) (INITIAL_CAPACITY * LOAD_FACTOR);
    }
    
    static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;
        final int hash;
        
        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    
    public V put(K key, V value) {
        int hash = hash(key);
        int index = indexFor(hash, table.length);
        
        // 检查是否已存在
        for (Node<K, V> e = table[index]; e != null; e = e.next) {
            if (e.hash == hash && (e.key == key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        
        // 添加新节点
        addNode(hash, key, value, index);
        return null;
    }
    
    private void addNode(int hash, K key, V value, int bucketIndex) {
        Node<K, V> newNode = new Node<>(hash, key, value, table[bucketIndex]);
        table[bucketIndex] = newNode;
        
        if (++size > threshold) {
            resize(2 * table.length);
        }
    }
    
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        Node<K, V>[] oldTable = table;
        Node<K, V>[] newTable = (Node<K, V>[]) new Node[newCapacity];
        
        for (Node<K, V> oldNode : oldTable) {
            while (oldNode != null) {
                Node<K, V> next = oldNode.next;
                int index = indexFor(oldNode.hash, newCapacity);
                oldNode.next = newTable[index];
                newTable[index] = oldNode;
                oldNode = next;
            }
        }
        
        table = newTable;
        threshold = (int) (newCapacity * LOAD_FACTOR);
    }
    
    private int hash(Object key) {
        int h = key.hashCode();
        return h ^ (h >>> 16);
    }
    
    private int indexFor(int hash, int length) {
        return hash & (length - 1);
    }
}

第五章：排序算法（Sorting Algorithms）

5.1 排序算法分类与复杂度对比

算法 时间复杂度 空间复杂度 稳定性 适用场景
冒泡排序 O(n²) O(1) 稳定 小规模数据
选择排序 O(n²) O(1) 不稳定 小规模数据
插入排序 O(n²) O(1) 稳定 近乎有序数据
希尔排序 O(n log n) O(1) 不稳定 中等规模数据
归并排序 O(n log n) O(n) 稳定 大规模数据
快速排序 O(n log n) O(log n) 不稳定 大规模数据
堆排序 O(n log n) O(1) 不稳定 大规模数据
计数排序 O(n+k) O(k) 稳定 整数范围小
桶排序 O(n+k) O(n+k) 稳定 均匀分布数据
基数排序 O(d(n+k)) O(n+k) 稳定 整数或字符串

5.2 经典排序算法实现

5.2.1 快速排序（Quick Sort）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class QuickSort {
    
    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    private 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) {
                i++;
                swap(arr, i, j);
            }
        }
        
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    // 三数取中法优化
    private int medianOfThree(int[] arr, int low, int high) {
        int mid = low + (high - low) / 2;
        
        if (arr[low] > arr[mid]) swap(arr, low, mid);
        if (arr[low] > arr[high]) swap(arr, low, high);
        if (arr[mid] > arr[high]) swap(arr, mid, high);
        
        swap(arr, mid, high - 1);
        return arr[high - 1];
    }
}

5.2.2 归并排序（Merge Sort）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class MergeSort {
    
    public void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            
            merge(arr, left, mid, right);
        }
    }
    
    private void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];
        
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[mid + 1 + j];
        }
        
        int i = 0, j = 0, k = left;
        
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }
        
        while (i < n1) {
            arr[k++] = leftArr[i++];
        }
        
        while (j < n2) {
            arr[k++] = rightArr[j++];
        }
    }
}

5.2.3 堆排序（Heap Sort）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class HeapSort {
    
    public void heapSort(int[] arr) {
        int n = arr.length;
        
        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // 一个个从堆中提取元素
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i); // 将最大值移到末尾
            heapify(arr, i, 0); // 重新调整剩余元素为最大堆
        }
    }
    
    private void heapify(int[] arr, int heapSize, int root) {
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;
        
        // 如果左子节点大于根节点
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // 如果右子节点大于当前最大值
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // 如果最大值不是根节点，交换并继续调整
        if (largest != root) {
            swap(arr, root, largest);
            heapify(arr, heapSize, largest);
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

5.3 排序算法优化技巧

5.3.1 快速排序优化

  1. 三数取中法：选择更好的基准值
  2. 小数组使用插入排序：减少递归开销
  3. 三向切分：处理大量重复元素
  4. 尾递归优化：减少栈空间使用

5.3.2 归并排序优化

  1. 小数组使用插入排序
  2. 原地归并：减少空间复杂度
  3. TimSort：结合归并和插入排序的优点

第六章：算法设计技巧

6.1 双指针技巧

双指针技巧通过使用两个指针遍历数据结构，将O(n²)的时间复杂度优化到O(n)。

6.1.1 快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
// 链表中间节点查找
public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
}

6.1.2 左右指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 两数之和（有序数组）
public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return new int[]{-1, -1};
}

6.2 分治算法

分治法将问题分解为子问题，分别解决后合并结果。

6.2.1 分治框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public Result divideAndConquer(Problem problem) {
    // 基本情况
    if (problem.isBaseCase()) {
        return problem.solveBaseCase();
    }
    
    // 分解问题
    Problem[] subProblems = problem.divide();
    
    // 解决子问题
    Result[] subResults = new Result[subProblems.length];
    for (int i = 0; i < subProblems.length; i++) {
        subResults[i] = divideAndConquer(subProblems[i]);
    }
    
    // 合并结果
    return problem.merge(subResults);
}

6.3 贪心算法

贪心算法在每一步选择当前最优解，希望最终得到全局最优解。

6.3.1 贪心算法适用条件

  1. 最优子结构：问题的最优解包含子问题的最优解
  2. 贪心选择性质：局部最优选择能导致全局最优解

6.3.2 经典贪心问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 活动选择问题
class ActivitySelection {
    public int maxActivities(int[] start, int[] end) {
        int n = start.length;
        
        // 按结束时间排序
        int[][] activities = new int[n][2];
        for (int i = 0; i < n; i++) {
            activities[i] = new int[]{start[i], end[i]};
        }
        
        Arrays.sort(activities, (a, b) -> a[1] - b[1]);
        
        int count = 1;
        int lastEnd = activities[0][1];
        
        for (int i = 1; i < n; i++) {
            if (activities[i][0] >= lastEnd) {
                count++;
                lastEnd = activities[i][1];
            }
        }
        
        return count;
    }
}

第七章：高频面试真题解析

7.1 链表高频面试题

7.1.1 LRU缓存机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class LRUCache {
    private class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) {
            key = k;
            value = v;
        }
    }
    
    private Map<Integer, Node> map;
    private Node head, tail;
    private int capacity;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            remove(node);
            addToHead(node);
            return node.value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(map.get(key));
        }
        
        Node newNode = new Node(key, value);
        addToHead(newNode);
        map.put(key, newNode);
        
        if (map.size() > capacity) {
            Node tailNode = removeTail();
            map.remove(tailNode.key);
        }
    }
    
    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private Node removeTail() {
        Node node = tail.prev;
        remove(node);
        return node;
    }
}

7.2 树结构高频面试题

7.2.1 二叉树序列化与反序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Codec {
    private static final String NULL = "#";
    private static final String SEP = ",";
    
    // 前序遍历序列化
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }
    
    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        
        sb.append(node.val).append(SEP);
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }
    
    // 前序遍历反序列化
    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(SEP)));
        return deserializeHelper(queue);
    }
    
    private TreeNode deserializeHelper(Queue<String> queue) {
        String val = queue.poll();
        if (val.equals(NULL)) {
            return null;
        }
        
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(queue);
        node.right = deserializeHelper(queue);
        
        return node;
    }
}

7.3 图论高频面试题

7.3.1 课程表问题（拓扑排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 构建邻接表
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        adj.add(new ArrayList<>());
    }
    
    // 计算入度
    int[] inDegree = new int[numCourses];
    for (int[] pre : prerequisites) {
        adj.get(pre[1]).add(pre[0]);
        inDegree[pre[0]]++;
    }
    
    // 拓扑排序
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        
        for (int next : adj.get(course)) {
            if (--inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    
    return count == numCourses;
}

第八章：算法复杂度分析

8.1 时间复杂度分析

8.1.1 大O表示法

  • O(1)：常数时间复杂度
  • O(log n)：对数时间复杂度
  • O(n)：线性时间复杂度
  • O(n log n)：线性对数时间复杂度
  • O(n²)：平方时间复杂度
  • O(2ⁿ)：指数时间复杂度

8.1.2 递归复杂度分析

主定理（Master Theorem）

对于形如T(n) = aT(n/b) + f(n)的递归式：

  1. 如果f(n) = O(n^(log_b a - ε))，则T(n) = Θ(n^(log_b a))
  2. 如果f(n) = Θ(n^(log_b a))，则T(n) = Θ(n^(log_b a) log n)
  3. 如果f(n) = Ω(n^(log_b a + ε))，且af(n/b) ≤ cf(n)，则T(n) = Θ(f(n))

8.2 空间复杂度分析

  • O(1)：原地算法
  • O(n)：需要额外线性空间
  • O(log n)：递归调用栈空间
  • O(n²)：二维数组存储

总结

数据结构与算法是计算机科学的核心基础，掌握这些知识点对于技术面试和实际开发都至关重要。本文系统梳理了：

  1. 链表：单链表、双链表、循环链表的核心操作和经典题型
  2. 树结构：二叉树、BST、AVL树、B树、B+树的原理和实现
  3. 图结构：图的表示、遍历算法和最短路径算法
  4. 哈希表：哈希函数设计、冲突解决和Java实现
  5. 排序算法：各种排序算法的原理、实现和优化技巧
  6. 算法技巧：双指针、分治、贪心等经典算法设计技巧

建议读者通过大量刷题来巩固这些知识点，推荐使用LeetCode、力扣等平台进行练习。同时，理解算法背后的思想比死记硬背更重要，要学会举一反三，灵活运用。

参考文献

  1. 《算法导论》- Thomas H. Cormen等
  2. 《数据结构与算法分析》- Mark Allen Weiss
  3. 《算法》- Robert Sedgewick
  4. LeetCode官方题解
  5. 力扣中国官方文档
  6. 《Java数据结构和算法》- Robert Lafore

本文档持续更新，如有错误或建议，欢迎指正。