背景

本文是《Java 后端从小白到大神》修仙系列第二十三篇，正式进入Java后端世界，本篇文章主要聊Java基础。若想详细学习请点击首篇博文，我们开始把。

文章概览

常见数据结构
常见算法

常见数据结构

1. 数组

概念：一组固定大小的同类型元素，按连续内存存储，通过索引随机访问。

示意图：

┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │  …
└───┴───┴───┴───┘
 index: 0,1,2,3,…

分类：线性、顺序存储。

Java 实现：

数组

public class ArrayDS {
    private int[] data;
    private int size;

    public ArrayDS(int compacity) {
        this.data = new int[compacity];
        this.size = 0;
    }

    public void add(int value) {
        if (size == data.length)
            throw new RuntimeException("数组已满");
        data[size++] = value;
    }

    public int get(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException();
        return data[index];
    }

    public int size() {
        return size;
    }

    // 测试方法
    public static void main(String[] args) {
        ArrayDS arr = new ArrayDS(5);
        arr.add(10);
        arr.add(20);
        arr.add(30);
        System.out.println("元素[1]=" + arr.get(1)); // 20
        System.out.println("当前大小=" + arr.size());
    }
}

2. 单向链表

概念：节点通过指针顺序相连，动态大小，插入删除 O(1)（已知节点）。

示意图：

[head] → [1 | *] → [2 | *] → [3 | null]

分类：线性、链式存储。

Java 实现：

单向链表

public class SinglyLinkedList<T> {
    private static class Node<T> {
        T val;
        Node<T> next;

        Node(T v) {
            val = v;
        }
    }

    private Node<T> head;

    public void addFirst(T v) {
        Node<T> node = new Node<>(v);
        node.next = head;
        head = node;
    }

    public void addLast(T v) {
        Node<T> node = new Node<>(v);
        if (head == null) {
            head = node;
        } else {
            Node<T> cur = head;
            while (cur.next != null)
                cur = cur.next;
            cur.next = node;
        }
    }

    public boolean contains(T v) {
        Node<T> cur = head;
        while (cur != null) {
            if (cur.val == v)
                return true;
            cur = cur.next;
        }
        return false;
    }

    public void print() {
        Node<T> cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 反转链表（迭代法）
    // 原火车：车厢A → 车厢B → 车厢C → 车厢D → null
    // prev：已调头完成的“新火车”的当前头车厢
    // current：正在处理的原火车车厢
    // next：原火车中下一节待处理车厢（防止断开后找不到）
    // 1，保存后面的火车 2，让当前火车指向前面车箱 3，前面的车厢变成前车 4，当前车变成下一个

    public void reverse() {
        Node<T> prev = null;
        Node<T> current = head;
        Node<T> next = null;

        while (current != null) {
            next = current.next; // 保存下一个节点
            current.next = prev; // 反转指针
            prev = current; // prev 前移
            current = next; // current 前移
        }
        head = prev; // 更新头节点
    }

    // 反转链表（递归法）
    // 1 -> 2 -> 3 -> 4 -> null
    // 递归到4时，reversedList：4 -> null，然后让4指向3，删除3的原指针，再返回最新的头节点

    public Node<T> reverseRecursive(Node<T> head) {
        if (head == null || head.next == null) {
            return head; // 终止条件：空链表或最后一个节点
        }
        Node<T> reversedList = reverseRecursive(head.next); // 递归反转子链表，先让后面的子链表完成反转，返回新头节点
        head.next.next = head; // 将子链表的末尾指向当前节点
        head.next = null; // 断开当前节点的原指针
        return reversedList; // 返回新头节点
    }

    // 删除最后一个节点
    public void deleteTail() {
        if (head == null || head.next == null) {
            head = null; // 链表为空或只有一个节点
            return;
        }

        Node<T> current = head;
        while (current.next.next != null) { // 找到倒数第二个节点
            current = current.next;
        }
        current.next = null;
    }

    // 删除第一个匹配值的节点
    public void deleteByValue(T value) {
        if (head == null || value == null)
            return;

        // 处理头节点为目标的情况
        if (value.equals(head.val)) {
            head = head.next;
            return;
        }

        // 遍历链表，找到目标节点的前一个节点
        Node<T> current = head;
        while (current.next != null) {
            if (value.equals(current.next.val)) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // 删除头节点
    public void deleteHead() {
        if (head != null) {
            head = head.next;
        }
    }
    // 测试代码
    public static void main(String[] args) {
        SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
        list.addLast(5);
        list.addFirst(3);
        list.addLast(7);
        list.addLast(8);
        list.addFirst(9);
        System.out.println("包含7? " + list.contains(7)); // true
        System.out.println("包含4? " + list.contains(4)); // false
        list.print(); // 原始打印
        list.reverse(); // 反转链表
        list.print(); // 反转后打印
        list.head = list.reverseRecursive(list.head); // 递归反转链表
        list.print(); // 递归反转后打印
        list.deleteByValue(8); // 删除值为8的节点
        list.print(); 
        list.addLast(10);
        list.print();
        list.deleteTail();
        list.print();
        list.deleteHead();
        list.print();

    }
}

3. 双向链表

概念：每个节点有前驱和后继指针，可双向遍历，删除节点更高效。

示意图：

       head                       tail
        ↓                          ↓
null ← [1] <--> [2] <--> [3] <--> [4] → null

分类：线性、链式存储。

Java 实现：

双向链表

public class DoublyLinkedList<T> {
    // 节点类
    private static class Node<T> {
        T value;
        Node<T> next, prev;

        Node(T value) {
            this.value = value;
        }
    }

    private Node<T> head, tail;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    // 在头部插入节点
    public void addFirst(T value) {
        Node<T> node = new Node<T>(value);
        if (head == null) {
            head = tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    // 在尾部插入节点
    public void addLast(T value) {
        Node<T> node = new Node<T>(value);
        if (tail == null) {
            head = tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }

    // 是否包含某节点
    public boolean contains(T value) {
        Node<T> node = head;
        while (node != null) {
            if (node.value == value) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    // 正向遍历
    public void traverseForward() {
        Node<T> current = head;
        while (current != null) {
            System.out.print(current.value + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // 反向遍历
    public void traverseBackward() {
        Node<T> current = tail;
        while (current != null) {
            System.out.print(current.value + " -> ");
            current = current.prev;
        }
        System.out.println("null");
    }

    // 删除节点
    public void remove(Node<T> node) {
        if (node == null) {
            throw new IllegalArgumentException("被删除节点不能为null");
        }
        if (!isNodeInList(node)) {
            throw new NoSuchElementException("节点不在链表中");
        }
        if (node == head && node == tail) {
            head = tail = null;
        } else if (node == head) {
            head = head.next;
            head.prev = null;
        } else if (node == tail) {
            tail = tail.prev;
            tail.next = null;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    // 打印链表
    public void print() {
        Node<T> node = head;
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    // 判断节点是否在链表中
    private boolean isNodeInList(Node<T> node) {
        Node<T> current = head;
        while (current != null) {
            if (current == node) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 查找节点
    public Node<T> findNode(T value) {
        Node<T> current = head;
        while (current != null) {
            if (current.value.equals(value)) {
                return current;
            }
            current = current.next;
        }
        return null;
    }

    // 测试代码
    public static void main(String[] args) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
        list.addFirst(5);
        list.addFirst(3);
        list.addLast(7);
        list.addLast(9);
        list.print();
        System.out.println(list.contains(3));
        list.traverseBackward();
        list.traverseForward();
        Node<Integer> target = list.findNode(3);
        if (target != null) {
            list.remove(target);
            System.out.println("删除成功");
        } else {
            System.out.println("节点不存在");
        }
        list.print();
    }
}

4. 栈 (Stack)

概念：后进先出 (LIFO) ，先入在底的结构。

示意图：

stack.push(1); 
stack.push(2);
stack.push(3);

栈顶（top） → 3 → 2 → 1 → 栈底

Top → [3]
       [2]
       [1]

分类：线性，可基于数组或链表实现。

Java 实现：

基于数组实现的栈

// 数组实现的栈需要固定容量，适合预先知道栈最大深度的场景
public class ArrayStack<T> {
    private Object[] array; // 存储元素的数组
    private int top; // 栈顶指针（初始为 -1）
    private int capacity; // 栈的最大容量

    // 构造函数
    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.array = new Object[capacity];
        this.top = -1;
    }

    // 入栈
    public void push(T item) {
        if (isFull()) {
            throw new IllegalStateException("Stack is full");
        }
        array[++top] = item; // 先移动指针，再存储元素
    }

    // 出栈
    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        @SuppressWarnings("unchecked")
        T item = (T) array[top];
        array[top--] = null; // 清除引用，防止内存泄漏
        return item;
    }

    // 查看栈顶元素（不出栈）
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        @SuppressWarnings("unchecked")
        T item = (T) array[top];
        return item;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 判断栈是否已满
    public boolean isFull() {
        return top == capacity - 1;
    }

    // 输出栈内元素
    public void print() {
        for (int i = top; i >= 0; i--) {
            System.out.print(array[i] + "->");
        }
    }

    // 测试代码
    public static void main(String[] args) {
        ArrayStack<Integer> stack = new ArrayStack<>(3);
        stack.push(1); // 栈顶 → 3 → 2 → 1 → 栈底
        stack.push(2);
        stack.push(3);

        System.out.println(stack.pop()); // 输出 3
        System.out.println(stack.peek()); // 输出 2
        stack.print();
    }
}

基于链表实现的栈

// 链表实现的栈无需固定容量，适合动态扩展的场景
public class LinkedStack<T> {
    private static class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node<T> top; // 栈顶节点

    public LinkedStack() {
        top = null;
    }

    // 入栈
    // 现实比喻：叠盘子
    // 想象你有一叠盘子（栈），每次新放入一个盘子时：
    // 新盘子放在最上面（成为新的栈顶）。
    // 新盘子的下方是原来的最上面的盘子（即新盘子的 next 指向原来的栈顶）。
    // 这样，盘子叠放的结构始终是 最新放入的在最上方，而取出时也只能从最上方开始拿（后进先出）。
    
    public void push(T item) {
        Node<T> newNode = new Node<>(item);
        newNode.next = top; // 新节点指向原栈顶
        top = newNode; // 更新栈顶
    }

    // 出栈
    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        T item = top.data;
        top = top.next; // 栈顶下移
        return item;
    }

    // 查看栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.data;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == null;
    }

    // 测试代码
    public static void main(String[] args) {
        LinkedStack<String> stack = new LinkedStack<>();
        stack.push("Java"); // 栈顶 → "C++" → "Python" → "Java" → 栈底
        stack.push("Python");
        stack.push("C++");
        System.out.println(stack.pop()); // 输出 C++
        System.out.println(stack.peek()); // 输出 Python
    }
}

5. 队列 (Queue)

概念：先进先出 (FIFO) 结构。

示意图：

    入队（enqueue）方向 →→→→→→→→→→→→→→→→→→，新元素从队列的 队尾（rear） 加入
队列： [front] → 元素A → 元素B → 元素C → [rear] （新元素在此插入）
    出队（dequeue）方向 ←←←←←←←←←←←←←←←←←←，元素从队列的 队首（front） 离开

分类：线性，可基于数组/环形/链表实现。

Java 实现：

基于环形数组实现队列

// 容量固定，不能动态扩展，高性能 
public class CircularQueue<T> {
    private Object[] array;
    private int front; // 队首指针（指向第一个元素）
    private int rear; // 队尾指针（指向下一个插入位置）
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity + 1; // 多留一个空位，用于区分满和空
        this.array = new Object[this.capacity];
        this.front = this.rear = 0;
    }

    // 入队
    public void enqueue(T item) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        array[rear] = item;
        rear = (rear + 1) % capacity; // 环形移动
    }

    // 出队
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        @SuppressWarnings("unchecked")
        T item = (T) array[front];
        front = (front + 1) % capacity; // 环形移动
        return item;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return front == rear;
    }

    // 判断队列是否已满
    public boolean isFull() {
        return (rear + 1) % capacity == front; // 队尾的下一个位置是队首
    }

    // 打印队列
    public void print() {
        for (int i = front; i != rear; i = (i + 1) % capacity) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

    // 测试代码
    public static void main(String[] args) {
        CircularQueue<String> queue = new CircularQueue<>(5);
        queue.enqueue("A");
        queue.enqueue("B");
        queue.enqueue("C");
        queue.enqueue("D");
        queue.enqueue("E");
        queue.dequeue();
        queue.print();

    }
}

基于链表实现队列

// 容量无限制，动态扩展的通用场景
public class LinkedQueue<T> {
    private static class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> front; // 队首指针（指向第一个元素）
    private Node<T> rear; // 队尾指针（指向最后一个元素）

    // 入队（从 rear 插入）
    public void enqueue(T item) {
        Node<T> newNode = new Node<>(item);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode; // 当前尾节点指向新节点
            rear = newNode; // 更新尾指针
        }
    }

    // 出队（从 front 移除）
    public T dequeue() {
        if (isEmpty())
            throw new IllegalStateException("Queue is empty");
        T item = front.data;
        front = front.next;
        if (front == null)
            rear = null; // 队列已空
        return item;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return front == null;
    }

    // 测试代码
    public static void main(String[] args) {
        LinkedQueue<String> queue = new LinkedQueue<>();
        queue.enqueue("A"); // rear 插入
        queue.enqueue("B");
        queue.enqueue("C");

        System.out.println(queue.dequeue()); // 输出 A（front 移除）
        System.out.println(queue.dequeue()); // 输出 B
    }
}

6. 哈希表 (Hash Table)

概念：通过哈希函数将键映射到数组索引，实现近似 O(1) 插入、查找。

示意图：

1. 以链表法为例，哈希表的结构如下：

数组索引（Buckets）       链表节点（键值对）
[0] → null
[1] → [Key1:Value1] → [Key2:Value2] → null
[2] → [Key3:Value3] → null
[3] → null
...
[n] → [KeyN:ValueN] → [KeyM:ValueM] → ...

无冲突：索引 2 的键 Key3 直接存储。
冲突：索引 1 的 Key1 和 Key2 哈希冲突，以链表形式存储。

2. 哈希表中链表的结构：

想象链表是一列火车，每个节点是一节车厢：
每节车厢（Node）：
  数据（data）：车厢里装载的货物（键值对）。
  连接钩（next）：指向下一节车厢的挂钩。
链表的头节点（head）：火车头，是整个链表的起点。

头节点（head） → [车厢1] → [车厢2] → [车厢3] → null
                   ↑          ↑          ↑
                  data       data       data
                  next →    next →     next → null

分类：哈希存储。

Java 实现：

链表实现哈希表

public class HashMapDS<K, V> {
    private static final int DEFAULT_CAPACITY = 16; // 默认初始容量
    private static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子
    private Node<K, V>[] table; // 存储桶的数组
    private int size; // 当前元素数量
    private int threshold; // 扩容阈值（capacity * loadFactor）

    // 哈希表节点定义（链表结构）
    private static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next; // 哈希表中同一桶的多个节点通过 next 链接
        final int hash; // 缓存哈希值

        public Node(K key, V value, int hash, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

    // 构造函数
    @SuppressWarnings("unchecked")
    public HashMapDS() {
        table = (Node<K, V>[]) new Node[DEFAULT_CAPACITY];
        threshold = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR);
    }

    // 计算哈希值（简化版，未使用扰动函数）
    private int hash(K key) {
        if (key == null)
            return 0;
        int h = key.hashCode();
        return h ^ (h >>> 16); // 扰动处理
    }

    // 插入键值对
    public void put(K key, V value) {
        if (key == null) {
            // 处理 key 为 null 的情况（简化版略）
            return;
        }

        int hash = hash(key);
        int index = (table.length - 1) & hash; // 计算索引

        // 遍历链表，检查是否已存在相同 key
        Node<K, V> node = table[index];
        while (node != null) {
            if (node.hash == hash && (node.key == key || node.key.equals(key))) {
                node.value = value; // 更新值
                return;
            }
            node = node.next;
        }

        // 新节点插入链表头部
        table[index] = new Node<>(key, value, hash, table[index]);
        size++;

        // 检查是否需要扩容
        if (size > threshold) {
            resize();
        }
    }

    // 获取值
    public V get(K key) {
        int hash = hash(key);
        int index = (table.length - 1) & hash;

        Node<K, V> node = table[index];
        while (node != null) {
            if (node.hash == hash && (node.key == key || node.key.equals(key))) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    // 动态扩容
    private void resize() {
        int newCapacity = table.length * 2;
        @SuppressWarnings("unchecked")
        Node<K, V>[] newTable = (Node<K, V>[]) new Node[newCapacity];
        threshold = (int) (newCapacity * DEFAULT_LOAD_FACTOR);

        // 重新哈希所有节点到新数组
        for (Node<K, V> node : table) {
            while (node != null) {
                Node<K, V> next = node.next;
                int newIndex = (newCapacity - 1) & node.hash;
                // 插入新链表头部
                // 假设旧链表为 A → B → C → null
                // 处理节点 A计算 newIndex = 5，此时 newTable[5] = null
                // 将节点 A 插入 newTable[5]，newTable[5] → A → null
                node.next = newTable[newIndex]; 
                newTable[newIndex] = node;
                node = next;    
            }
        }

        table = newTable;
    }

    // 测试代码
    public static void main(String[] args) {
        HashMapDS<String, Integer> map = new HashMapDS<>();
        map.put("apple", 10);
        map.put("banana", 20);
        map.put("orange", 30);

        System.out.println(map.get("apple")); // 输出 10
        System.out.println(map.get("banana")); // 输出 20
        System.out.println(map.get("grape")); // 输出 null
    }
}

7. 二叉搜索树 (Binary Search Tree)

概念：二叉树，每个左子树小于父节点，右子树大于父节点，中序遍历左->中->右。

示意图：

分类：非线性、树。

Java 实现：

基于链表实现二叉搜索树

public class BinarySearchTree {
    // 树节点
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    private TreeNode root; // 根节点

    // 插入节点
    public void insert(int val) {
        root = insertRecursive(root, val);
    }

    // 递归插入辅助方法
    private TreeNode insertRecursive(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val); // 创建新节点
        }
        if (val < root.val) {
            root.left = insertRecursive(root.left, val); // 插入左子树
        } else if (val > root.val) {
            root.right = insertRecursive(root.right, val); // 插入右子树
        }
        return root; // 返回当前节点（避免重复插入）
    }

    // 查找节点是否存在
    public boolean search(int val) {
        return searchRecursive(root, val);
    }

    // 递归查找辅助方法
    private boolean searchRecursive(TreeNode root, int val) {
        if (root == null) {
            return false;
        }
        if (val == root.val) {
            return true;
        } else if (val < root.val) {
            return searchRecursive(root.left, val); // 左子树查找
        } else {
            return searchRecursive(root.right, val); // 右子树查找
        }
    }

    // 删除节点
    public void delete(int val) {
        root = deleteRecursive(root, val);
    }

    // 递归删除辅助方法
    private TreeNode deleteRecursive(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (val < root.val) {
            root.left = deleteRecursive(root.left, val); // 在左子树删除
        } else if (val > root.val) {
            root.right = deleteRecursive(root.right, val); // 在右子树删除
        } else {
            // 找到目标节点，分三种情况处理
            if (root.left == null) {
                return root.right; // 情况1：无左子树，直接返回右子树
            } else if (root.right == null) {
                return root.left; // 情况2：无右子树，直接返回左子树
            } else {
                // 情况3：有左右子树
                // 找到右子树的最小节点（或左子树的最大节点）
                TreeNode minNode = findMin(root.right);
                root.val = minNode.val; // 用最小节点的值替换当前节点
                root.right = deleteRecursive(root.right, minNode.val); // 删除右子树的最小节点
            }
        }
        return root;
    }

    // 查找子树的最小节点（辅助删除操作）
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // 中序遍历（升序输出）
    public void inorderTraversal() {
        inorderRecursive(root);
    }

    private void inorderRecursive(TreeNode root) {
        if (root != null) {
            inorderRecursive(root.left);
            System.out.print(root.val + " ");
            inorderRecursive(root.right);
        }
    }

    // 测试代码
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(5);
        bst.insert(3);
        bst.insert(7);
        bst.insert(2);
        bst.insert(4);

        System.out.println("中序遍历结果:");
        bst.inorderTraversal(); // 输出: 2 3 4 5 7

        System.out.println("\n查找 4: " + bst.search(4)); // true
        System.out.println("查找 6: " + bst.search(6)); // false

        bst.delete(3);
        System.out.println("删除 3 后的中序遍历:");
        bst.inorderTraversal(); // 输出: 2 4 5 7
    }
}

8. 最小/最大堆 (Binary Heap)

概念：堆是一种完全二叉树，所有层都填满，只有最后一层可能不满，但一定是从左往右依次填充。

最小堆（Min Heap）：每个父节点的值 ≤ 其子节点的值，堆顶元素是整个堆的最小值。

示意图（最小堆）：

最大堆（Max Heap）：每个父节点的值 ≥ 其子节点的值，堆顶元素是整个堆的最大值。

示意图（最大堆）：

示意图（索引公式）：

i表示数组索引 
左子节点索引：2 * i + 1
右子节点索引：2 * i + 2
父节点索引：(i - 1) / 2

2*i + 1 < n 才有左子节点
2*i + 2 < n 才有右子节点
n 是数组的长度

int[] heap = {1, 3, 5, 7, 9, 8};
这个数组中：

i = 0 表示的是根节点，它的值是 heap[0] = 1
i = 1 表示的是第 2 个节点，值是 heap[1] = 3
i = 2 表示的是第 3 个节点，值是 heap[2] = 5
...

分类：非线性、树。

Java 实现：

基于数组实现最小堆

public class MinHeap {
    private int[] heap; // 存储堆元素的数组
    private int size; // 当前堆中元素数量
    private int capacity; // 堆的最大容量

    // 构造函数
    public MinHeap(int initialCapacity) {
        this.capacity = initialCapacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    // 插入元素
    public void insert(int val) {
        if (size == capacity) {
            resize(); // 动态扩容
        }
        heap[size] = val; // 新元素插入到索引 size 的位置
        heapifyUp(size); // 此时 size 既是元素数量，也是新元素的索引
        size++; // 更新元素数量
    }

    // 上浮调整
    private void heapifyUp(int index) {
        int current = index;
        while (current > 0) {
            int parent = (current - 1) / 2;
            if (heap[current] >= heap[parent]) {
                break; // 满足堆序特性，终止
            }
            swap(current, parent);
            current = parent;
        }
    }

    // 删除堆顶元素（最小值）
    public int extractMin() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int min = heap[0];
        heap[0] = heap[size - 1]; // 将末尾元素移到堆顶
        size--;
        heapifyDown(0);
        return min;
    }

    // 下沉调整
    private void heapifyDown(int index) {
        int current = index;
        while (true) {
            int left = 2 * current + 1;
            int right = 2 * current + 2;
            int smallest = current;

            // 比较左子节点与当前节点
            if (left < size && heap[left] < heap[smallest]) {
                smallest = left;
            }

            // 比较右子节点与当前最小值
            if (right < size && heap[right] < heap[smallest]) {
                smallest = right;
            }

            // 若当前节点已是最小，终止调整
            if (smallest == current) {
                break; // 无需调整，终止
            }

            // 交换当前节点与最小子节点
            swap(current, smallest);

            // 继续向下调整
            current = smallest;
        }
    }

    // 获取堆顶元素（不删除）
    public int peek() {
        if (size == 0)
            throw new IllegalStateException("Heap is empty");
        return heap[0];
    }

    // 动态扩容
    private void resize() {
        capacity *= 2;
        int[] newHeap = new int[capacity];
        System.arraycopy(heap, 0, newHeap, 0, size);
        heap = newHeap;
    }

    // 交换元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 测试代码
    public static void main(String[] args) {
        MinHeap heap = new MinHeap(10);
        heap.insert(5);
        heap.insert(3);
        heap.insert(7);
        heap.insert(2);
        heap.insert(4);

        System.out.println("堆顶元素: " + heap.peek()); // 输出 2

        System.out.println("依次删除堆顶元素:");
        while (heap.size > 0) {
            System.out.print(heap.extractMin() + " "); // 输出 2 3 4 5 7
        }
    }
}

基于链表实现最小堆

public class LinkedMinHeap {
    private java.util.List<Integer> heap = new java.util.ArrayList<>();
    
    // 添加元素
    public void add(int v) {
        heap.add(v);
        siftUp(heap.size() - 1);
    }

    // 移除并返回堆顶元素
    public int poll() {
        if (heap.isEmpty())
            throw new RuntimeException();
        int top = heap.get(0);
        int last = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            siftDown(0);
        }
        return top;
    }

    // 上浮
    private void siftUp(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap.get(p) <= heap.get(i))
                break;
            java.util.Collections.swap(heap, p, i);
            i = p;
        }
    }

    // 下沉堆顶元素
    private void siftDown(int i) {
        int n = heap.size();
        while (true) {
            int l = 2 * i + 1, r = 2 * i + 2, smallest = i;
            if (l < n && heap.get(l) < heap.get(smallest))
                smallest = l;
            if (r < n && heap.get(r) < heap.get(smallest))
                smallest = r;
            if (smallest == i)
                break;
            java.util.Collections.swap(heap, i, smallest);
            i = smallest;
        }
    }

    public static void main(String[] args) {
        LinkedMinHeap h = new LinkedMinHeap();
        h.add(5);
        h.add(2);
        h.add(8);
        System.out.println("堆顶=" + h.poll()); // 2
        System.out.println("新堆顶=" + h.poll()); // 5
    }
}

9. 前缀树 (Trie)

概念：前缀树（Trie）是一种高效的树形数据结构，专门用于存储、检索和操作字符串集合。每个节点代表一个字符，从根节点到某一节点的路径形成一个完整的字符串。根节点为空，不存储字符，是整棵树的起点。例如，插入单词 “apple”，路径为：根 → a → p → p → l → e，并在末尾节点标记为单词结尾。

示意图：

root
 └─ 'c'
      └─ 'a'  
           └─ 't'

标记单词结束。

分类：非线性、树。

Java 实现：

基于数组实现前缀树

public class Trie {
    // Trie 节点定义（支持大小写字母和数字）
    private static class TrieNode {
        private final TrieNode[] children; // 子节点数组（62个位置：a-z + A-Z + 0-9）
        private boolean isEnd; // 标记是否为单词结尾

        public TrieNode() {
            this.children = new TrieNode[62]; // 26小写 + 26大写 + 10数字
            this.isEnd = false;
        }

        /**
         * 将字符转换为子节点数组的索引
         * 
         * @param c 字符（支持 a-z, A-Z, 0-9）
         * @return 索引（0-61）
         * @throws IllegalArgumentException 如果字符不合法
         */
        public int getIndex(char c) {
            if (c >= 'a' && c <= 'z') {
                return c - 'a'; // 0-25: a-z
            } else if (c >= 'A' && c <= 'Z') {
                return 26 + (c - 'A'); // 26-51: A-Z
            } else if (c >= '0' && c <= '9') {
                return 52 + (c - '0'); // 52-61: 0-9
            } else {
                throw new IllegalArgumentException("非法字符: " + c);
            }
        }
    }

    private final TrieNode root; // 根节点（空节点）

    public Trie() {
        root = new TrieNode();
    }

    /**
     * 插入单词到 Trie 中（支持大小写字母和数字）
     * 
     * @param word 要插入的单词
     * @throws IllegalArgumentException 如果单词包含非法字符
     */
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = node.getIndex(c); // 通过 getIndex 计算索引
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    /**
     * 检查单词是否存在于 Trie 中
     * 
     * @param word 要搜索的单词
     * @return 是否存在
     */
    public boolean search(String word) {
        TrieNode node = searchPrefixNode(word);
        return node != null && node.isEnd;
    }

    /**
     * 检查是否存在以指定前缀开头的单词
     * 
     * @param prefix 前缀
     * @return 是否存在
     */
    public boolean startsWith(String prefix) {
        return searchPrefixNode(prefix) != null;
    }

    /**
     * 辅助方法：查找前缀对应的最后一个节点
     * 
     * @param prefix 前缀
     * @return 最后一个节点（若不存在返回 null）
     */
    private TrieNode searchPrefixNode(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            try {
                int index = node.getIndex(c);
                if (node.children[index] == null) {
                    return null;
                }
                node = node.children[index];
            } catch (IllegalArgumentException e) {
                return null; // 前缀包含非法字符，直接返回不存在
            }
        }
        return node;
    }

    /**
     * 测试代码
     */
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("Apple123");
        trie.insert("Banana");
        trie.insert("cherry456");

        // 测试搜索
        System.out.println("搜索 'Apple123': " + trie.search("Apple123")); // true
        System.out.println("搜索 'apple123': " + trie.search("apple123")); // false（区分大小写）
        System.out.println("搜索 'Cherry456': " + trie.search("Cherry456")); // false（区分大小写）

        // 测试前缀匹配
        System.out.println("前缀 'App': " + trie.startsWith("App")); // true
        System.out.println("前缀 'Ban': " + trie.startsWith("Ban")); // true
        System.out.println("前缀 'Cherry4': " + trie.startsWith("Cherry4")); // false（区分大小写）
        System.out.println("前缀 'cherry4': " + trie.startsWith("cherry4")); // true
    }
}

基于Map实现前缀树


public class Trie2 {
    private static class Node {
        boolean end;
        java.util.Map<Character, Node> next = new java.util.HashMap<>();
    }

    private Node root = new Node();

    public void insert(String s) {
        Node cur = root;
        for (char c : s.toCharArray())
            cur = cur.next.computeIfAbsent(c, k -> new Node());
        cur.end = true;
    }

    public boolean search(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.next.get(c);
            if (cur == null)
                return false;
        }
        return cur.end;
    }

    public boolean startsWith(String p) {
        Node cur = root;
        for (char c : p.toCharArray()) {
            cur = cur.next.get(c);
            if (cur == null)
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Trie2 t = new Trie2();
        t.insert("cat");
        t.insert("car");
        System.out.println("包含\"cat\"? " + t.search("cat")); // true
        System.out.println("以 ca 开头? " + t.startsWith("ca")); // true
    }
}

10. 图 (Graph)

概念：图（Graph）是一种由 顶点（Vertex） 和 边（Edge） 组成的数据结构，用于表示实体之间的复杂关系。以下是图的详细说明及其应用场景：

图的基本结构

顶点（Vertex）
表示实体或对象（如社交网络中的用户、地图中的城市）。
边（Edge）
表示顶点之间的关系，可以有以下类型：
- 无向边：关系是双向的（如微信好友关系）。
- 有向边：关系是单向的（如微博关注关系）。
- 权重边：边附带数值（如两地之间的距离、交通成本）。
图的分类
- 无向图：所有边均为无向边。
- 有向图：边有方向性。
- 加权图：边附带权重值。

图的存储方式

1. 邻接矩阵（Adjacency Matrix）

实现：用二维数组 matrix[i][j] 表示顶点 i 和 j 的关系。
- 无向图：matrix[i][j] = matrix[j][i]。
- 有向图：matrix[i][j] 表示从 i 到 j 的边。
- 加权图：matrix[i][j] 存储权重值。
特点：
- 优点：快速查询两顶点是否相邻（O(1) 时间复杂度）。
- 缺点：空间复杂度高（O(V²)，V 为顶点数），适合稠密图。

2. 邻接表（Adjacency List）

实现：每个顶点维护一个链表，存储其直接相连的邻接顶点。
- 无向图：每个边在邻接表中存储两次（如 A→B 和 B→A）。
- 有向图：仅存储单向关系。
- 加权图：链表中存储邻接顶点及权重。
特点：
- 优点：空间复杂度低（O(V + E)，E 为边数），适合稀疏图。
- 缺点：查询两顶点是否相邻需遍历链表（O(d)，d 为顶点度数）。

图的应用场景

社交网络分析
- 顶点：用户；边：好友/关注关系。
- 应用：推荐共同好友、发现社区（如 Facebook 的好友推荐）。
路径规划与导航
- 顶点：地点；边：道路（权重为距离或时间）。
- 应用：计算最短路径（如 Google 地图的路线规划）。
推荐系统
- 顶点：用户和商品；边：用户购买/浏览记录。
- 应用：基于图的协同过滤（如“购买此商品的人也买了…”）。
网络拓扑与依赖管理
- 顶点：服务器或任务；边：依赖关系。
- 应用：检测循环依赖、任务调度（如项目管理工具）。
知识图谱
- 顶点：实体（人物、地点）；边：语义关系（如“出生于”、“属于”）。
- 应用：智能问答、语义搜索（如 Google 知识图谱）。

示意图：邻接表方式

0: →1 →2
1: →2
2: →0 →3
3:

分类：非线性、图。

Java 实现：

图的邻接表实现

import java.util.*;

/*
 * 图的邻接表实现
 */
public class GraphAdjList {
    private Map<Integer, List<Integer>> adjList; // 邻接表
    private int numVertices; // 顶点数量

    public GraphAdjList(int numVertices) {
        this.numVertices = numVertices;
        adjList = new HashMap<>();
        for (int i = 0; i < numVertices; i++) {
            adjList.put(i, new LinkedList<>());
        }
    }

    // 添加边（无向图）
    public void addEdgeUndirected(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }

    // 添加边（有向图）
    public void addEdgeDirected(int src, int dest) {
        adjList.get(src).add(dest);
    }

    // 打印邻接表
    public void printGraph() {
        adjList.forEach((vertex, neighbors) -> System.out.println(vertex + " -> " + neighbors));
    }

    // 广度优先遍历 (BFS)
    public void bfs(int startVertex) {
        // 1. 初始化访问标记数组，记录顶点是否被访问过
        boolean[] visited = new boolean[numVertices];

        // 2. 创建队列，用于管理待访问的顶点
        Queue<Integer> queue = new LinkedList<>();

        // 3. 将起始顶点加入队列，并标记为已访问
        queue.add(startVertex);
        visited[startVertex] = true;

        System.out.print("BFS遍历结果: ");

        // 4. 循环处理队列中的顶点，直到队列为空
        while (!queue.isEmpty()) {
            // 4.1 取出队列头部的顶点
            int vertex = queue.poll();
            System.out.print(vertex + " ");

            // 4.2 遍历当前顶点的所有邻居
            for (int neighbor : adjList.get(vertex)) {
                // 4.3 若邻居未被访问过
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // 标记为已访问
                    queue.add(neighbor); // 加入队列以待后续处理
                }
            }
        }
        System.out.println();
    }

    // 深度优先遍历 (DFS)
    public void dfs(int startVertex) {
        // 1. 初始化访问标记数组，记录顶点是否被访问过
        boolean[] visited = new boolean[numVertices];
        System.out.print("DFS遍历结果: ");

        // 2. 调用递归方法，从起始顶点开始遍历
        dfsRecursive(startVertex, visited);
        System.out.println();
    }

    private void dfsRecursive(int vertex, boolean[] visited) {
        // 3. 标记当前顶点为已访问
        visited[vertex] = true;
        System.out.print(vertex + " ");

        // 4. 遍历当前顶点的所有邻居
        for (int neighbor : adjList.get(vertex)) {
            // 5. 若邻居未被访问过，递归调用DFS
            if (!visited[neighbor]) {
                dfsRecursive(neighbor, visited);
            }
        }
    }

    // 测试代码
    public static void main(String[] args) {
        GraphAdjList graph = new GraphAdjList(5);
        graph.addEdgeUndirected(0, 1);
        graph.addEdgeUndirected(0, 4);
        graph.addEdgeUndirected(1, 3);
        graph.addEdgeDirected(2, 3); // 有向边

        // 打印邻接表
        System.out.println("邻接表结构:");
        graph.printGraph();

        graph.bfs(0); // BFS遍历结果: 0 1 4 3
        graph.dfs(0); // DFS遍历结果: 0 1 3 2 4
    }
}

图的邻接矩阵实现

/*
 * 图的邻接矩阵实现
 */
public class GraphMatrix {
    private int[][] matrix; // 邻接矩阵
    private int numVertices; // 顶点数量

    // 初始化图 (顶点数量固定)
    public GraphMatrix(int numVertices) {
        this.numVertices = numVertices;
        matrix = new int[numVertices][numVertices];
    }

    // 添加边（无向图）
    public void addEdgeUndirected(int src, int dest) {
        matrix[src][dest] = 1; // 1 仅表示顶点间存在边
        matrix[dest][src] = 1; // 对称位置赋值
    }

    // 添加边（有向图）
    public void addEdgeDirected(int src, int dest) {
        matrix[src][dest] = 1;
    }

    // 打印邻接矩阵
    public void printMatrix() {
        for (int i = 0; i < numVertices; i++) {
            System.out.print("顶点 " + i + " 的邻接点: ");
            for (int j = 0; j < numVertices; j++) {
                if (matrix[i][j] == 1) {
                    System.out.print(j + " ");
                }
            }
            System.out.println();
        }
    }

    // 测试代码
    public static void main(String[] args) {
        GraphMatrix graph = new GraphMatrix(5);
        graph.addEdgeUndirected(0, 1);
        graph.addEdgeUndirected(0, 4);
        graph.addEdgeUndirected(1, 3);
        graph.addEdgeUndirected(2, 3);
        graph.printMatrix();
    }
}

常见算法

1. 基础算法

1.1 二分查找 (Binary Search)

原理与作用：
二分查找用于在有序数组中查找目标值。其原理是将数组分为两部分，逐步缩小查找范围，时间复杂度为 O(log n)。这是面试中非常常见的题型，也是考察对算法复杂度理解的基础题目。

Java 示例代码：

二分查找

public class BinarySearchDemo {
    // 二分查找方法：在有序数组中查找 target，如果存在则返回下标，否则返回 -1
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int 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; // 未找到目标值
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int index = binarySearch(sortedArray, target);
        System.out.println("Target " + target + " found at index: " + index);
    }
}

1.2 排序算法

排序是面试中最常考的内容之一。下面列出两种常用且高效的排序算法：

1.2.1 快速排序 (Quick Sort)

原理与作用：
快速排序利用“分治”思想，将数组分为左右两个部分，使得左边都小于某个基准值，右边都大于这个基准值，然后递归排序左右子数组。平均时间复杂度为 O(n log n)。

Java 示例代码：

快速排序


public class QuickSortDemo {
    // 快速排序方法
    public static 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);
        }
    }

    // 分区方法，返回基准值所在下标
    // i 的作用：始终标记“小于区域”的末尾位置。
    // 交换 i+1 和 high：将 pivot 放置在“小于区域”之后，确保左侧全小于 pivot，右侧全大于等于 pivot。
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = low - 1; // i 指向小于 pivot 的区域的末尾，若partition后区域是 [3,1,4]，则 i 指向最后一个元素 4 的下标。
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // 交换 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 将 pivot 放到正确的位置上
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] array = { 10, 7, 8, 9, 1, 5 };
        quickSort(array, 0, array.length - 1);
        System.out.print("Sorted array: ");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

1.2.2 归并排序 (Merge Sort)

原理与作用：
归并排序也是一种基于分治的排序方法。它将数组递归分割为两半，分别排序后再合并，时间复杂度为 O(n log n)。其特点是稳定性好，适合处理大数据量。

Java 示例代码：

归并排序

/*
以数组 [12,11,13,5,6,7] 为例：

 *1. mergeSort(0,5) → 分割为 [0-2] 和 [3-5]
│
├─ 2.mergeSort(0,2) → 分割为 [0-1] 和 [2-2]
│  │
│  ├─ 3.mergeSort(0,1) → 分割为 [0-0] 和 [1-1]
│  │  │
│  │  ├─ 4.mergeSort(0,0) → 单元素，返回
│  │  │
│  │  ├─ 5.mergeSort(1,1) → 单元素，返回
│  │  │
│  │  └─ 6.合并 [12] 和 [11] → [11,12]
│  │
│  ├─ 7.mergeSort(2,2) → 单元素，返回
│  │
│  └─ 8.合并 [11,12] 和 [13] → [11,12,13]
│
├─ 9.mergeSort(3,5) → 分割为 [3-4] 和 [5-5]
│  │
│  ├─ 10.mergeSort(3,4) → 分割为 [3-3] 和 [4-4]
│  │  │
│  │  ├─ 11.mergeSort(3,3) → 单元素，返回
│  │  │
│  │  ├─ 12.mergeSort(4,4) → 单元素，返回
│  │  │
│  │  └─ 13.合并 [5] 和 [6] → [5,6]
│  │
│  ├─ 14.mergeSort(5,5) → 单元素，返回
│  │
│  └─ 15.合并 [5,6] 和 [7] → [5,6,7]
│
└─ 16.合并 [11,12,13] 和 [5,6,7] → [5,6,7,11,12,13]


以 mergeSort(0,1) 为例（处理子数组 [12,11]）
步骤3：调用 mergeSort(0,1)
mergeSort(arr, 0, 1); // 分割为 [0-0] 和 [1-1]
步骤4：处理左半部分 mergeSort(0,0)
触发 mergeSort(0,0)，检查到 left == right（单元素），直接结束递归，返回到步骤3的代码中。
此时程序继续执行 mergeSort(0,1) 方法中的下一行代码：
mergeSort(arr, mid + 1, right); // 即 mergeSort(1,1)
步骤5：处理右半部分 mergeSort(1,1)
触发 mergeSort(1,1)，同样因为 left == right，直接结束递归，返回到步骤3的代码中。
此时 mergeSort(0,1) 方法的两部分递归均完成，执行合并操作：
merge(arr, 0, mid, right); // 即 merge(0,0,1)

全局执行流程总结：
深度优先处理左半部分：递归会一直向左分解，直到无法再分割（单元素），然后处理对应的右半部分。例如：mergeSort(0,5) → mergeSort(0,2) → mergeSort(0,1) → mergeSort(0,0)。
回溯时处理右半部分：当左半部分彻底处理完成后，递归会回到上一层的右半部分调用。例如：mergeSort(0,0) 完成后，回到 mergeSort(0,1) 处理 mergeSort(1,1)。

 */

public class MergeSortDemo {
    // 归并排序方法
    public static 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 static void merge(int[] arr, int left, int mid, int right) {
        // 临时数组存放合并结果
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        // 合并两个子数组
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 复制剩余部分
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 将排序结果复制回原数组
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    public static void main(String[] args) {
        int[] array = { 12, 11, 13, 5, 6, 7 };
        mergeSort(array, 0, array.length - 1);
        System.out.print("Sorted array: ");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

2. 图与树相关算法

2.1 深度优先搜索 (DFS) 与广度优先搜索 (BFS)

原理与作用：

DFS： 利用递归或栈实现，遍历图或树的深度优先路径。适合解决连通性、路径查找等问题。
BFS： 利用队列实现，逐层遍历图或树。常用于最短路径问题。

Java 示例代码（以图的邻接表实现）：

DFS


import java.util.*;

// 图的深度优先搜索 (DFS)
public class GraphDFS {
    private Map<Integer, List<Integer>> graph = new HashMap<>();
    private Set<Integer> visited = new HashSet<>();

    // 添加边
    public void addEdge(int src, int dest) {
        // 无向图则添加双向边
        graph.computeIfAbsent(src, k -> new ArrayList<>()).add(dest);
        graph.computeIfAbsent(dest, k -> new ArrayList<>()).add(src); 
    }

    // DFS 递归实现
    public void dfs(int vertex) {
        visited.add(vertex);
        System.out.print(vertex + " ");
        for (int neighbor : graph.getOrDefault(vertex, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor);
            }
        }
    }

    public static void main(String[] args) {
        GraphDFS graphDFS = new GraphDFS();
        graphDFS.addEdge(0, 1);
        graphDFS.addEdge(0, 2);
        graphDFS.addEdge(1, 2);
        graphDFS.addEdge(2, 0);
        graphDFS.addEdge(2, 3);
        graphDFS.addEdge(3, 3);

        System.out.print("DFS starting from vertex 2: ");
        graphDFS.dfs(2);
    }
}

Java 示例代码（以队列实现）：

BFS


import java.util.*;

// 图的广度优先搜索 (BFS)
public class GraphBFS {
    private Map<Integer, List<Integer>> graph = new HashMap<>();

    // 添加边
    public void addEdge(int src, int dest) {
        // 无向图则添加双向边
        graph.computeIfAbsent(src, k -> new ArrayList<>()).add(dest);
        graph.computeIfAbsent(dest, k -> new ArrayList<>()).add(src); 
    }

    // BFS 实现
    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        visited.add(start);
        queue.offer(start);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");
            for (int neighbor : graph.getOrDefault(vertex, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        GraphBFS graphBFS = new GraphBFS();
        graphBFS.addEdge(0, 1);
        graphBFS.addEdge(0, 2);
        graphBFS.addEdge(1, 2);
        graphBFS.addEdge(2, 0);
        graphBFS.addEdge(2, 3);
        graphBFS.addEdge(3, 3);

        System.out.print("BFS starting from vertex 2: ");
        graphBFS.bfs(2);
    }
}

3. 动态规划 (Dynamic Programming)

原理与作用：
动态规划用于解决具有重叠子问题和最优子结构性质的问题。它通过存储中间结果避免重复计算，典型问题包括斐波那契数列、最长公共子序列、背包问题等。

3.1 斐波那契数列

Java 示例代码（使用数组保存中间结果）：

斐波那契数列

public class FibonacciDP {
    // 返回第 n 个斐波那契数
    public static int fibonacci(int n) {
        if(n <= 1) return n;
        int[] dp = new int[n + 1]; // dp[i] 表示第 i 个斐波那契数，第 0～n 项，即n+1
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
        }
        return dp[n];
    }
    
    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci number at position " + n + " is " + fibonacci(n));
    }
}

3.2 0-1 背包问题（贪心思路通常不适用，动态规划是主流解法）

原理与作用：
0-1 背包问题是一个经典的组合优化问题，给定一组物品，每个物品有自己的重量 w[i] 和价值 v[i]，以及一个容量为 W 的背包，要求在不超过背包容量的前提下，选择一些物品放入背包，使得背包中物品的总价值最大。每个物品只能选择放入或者不放入背包（即 0-1 选择）。
Java 示例代码：

背包问题

public class KnapsackDP {
    // 背包容量为 W，有 n 个物品，每个物品有重量 w[i] 和价值 v[i]
    public static int knapsack(int W, int[] w, int[] v, int n) {
        int[][] dp = new int[n + 1][W + 1];
        // dp[i][j] 表示前 i 个物品中，总重量不超过 j 的最大价值
        
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= W; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0; // 边界条件
                } else if (w[i - 1] <= j) {
                    // 状态转移：选择不放入或放入当前物品
                    dp[i][j] = Math.max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - w[i - 1]]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][W];
    }
    
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 5;
        int n = weights.length;
        System.out.println("Maximum value in knapsack: " + knapsack(capacity, weights, values, n));
    }
}

4. 贪心算法 (Greedy Algorithms)

原理与作用：
贪心算法每一步都选择当前看起来最优的方案，适用于某些具有贪心选择性质的问题。例如活动选择问题、区间调度、哈夫曼编码等。

4.1 活动选择问题（Interval Scheduling）

Java 示例代码：

活动选择问题的贪心算法


import java.util.*;

class Activity implements Comparable<Activity> {
    int start, finish;

    public Activity(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }

    // 根据结束时间排序
    // 当调用a.compareTo(b)时 ，this指向a ，other指向b，返回值 < 0 → this（当前对象）应排在other（其他对象）前面，
    // 返回值 > 0 → this应排在other后面，返回值 = 0 → 两者相等，顺序不变
    @Override
    public int compareTo(Activity other) {
        return this.finish - other.finish;
    }
}

public class ActivitySelection {
    // 返回所选活动列表
    public static List<Activity> selectActivities(List<Activity> activities) {
        Collections.sort(activities);
        List<Activity> selected = new ArrayList<>();
        int lastFinishTime = -1;
        for (Activity activity : activities) {
            if (activity.start >= lastFinishTime) {
                selected.add(activity);
                lastFinishTime = activity.finish;
            }
        }
        return selected;
    }

    public static void main(String[] args) {
        List<Activity> activities = Arrays.asList(
                new Activity(1, 4),
                new Activity(3, 5),
                new Activity(0, 6),
                new Activity(5, 7),
                new Activity(3, 9),
                new Activity(5, 9),
                new Activity(6, 10),
                new Activity(8, 11),
                new Activity(8, 12),
                new Activity(2, 14),
                new Activity(12, 16));

        List<Activity> selected = selectActivities(activities);
        System.out.println("Selected activities (start, finish):");
        for (Activity activity : selected) {
            System.out.println("(" + activity.start + ", " + activity.finish + ")");
        }
    }
}

5. 回溯算法 (Backtracking)

原理与作用：
回溯算法通过递归探索所有可能的解，遇到不满足条件时回退，从而解决排列组合、子集、八皇后、全排列等问题。

5.1 求全排列

Java 示例代码：

回溯问题之全排列

import java.util.*;

public class Permutations {
    // 回溯求数组全排列
    public static void permute(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            // 将排列结果存入 result
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(new ArrayList<>(permutation));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1, result);
            swap(nums, start, i); // 回溯，恢复原状
        }
    }
    
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = new ArrayList<>();
        permute(nums, 0, result);
        System.out.println("All permutations:");
        for (List<Integer> permutation : result) {
            System.out.println(permutation);
        }
    }
}

总结

本篇列出常见数据结构及算法，也是平时必须掌握的。

背景

文章概览

常见数据结构

1. 数组

2. 单向链表

3. 双向链表

4. 栈 (Stack)

5. 队列 (Queue)

6. 哈希表 (Hash Table)

7. 二叉搜索树 (Binary Search Tree)

8. 最小/最大堆 (Binary Heap)

9. 前缀树 (Trie)

10. 图 (Graph)

常见算法

1. 基础算法

1.1 二分查找 (Binary Search)

1.2 排序算法

1.2.1 快速排序 (Quick Sort)

1.2.2 归并排序 (Merge Sort)

2. 图与树相关算法

2.1 深度优先搜索 (DFS) 与 广度优先搜索 (BFS)

3. 动态规划 (Dynamic Programming)

3.1 斐波那契数列

3.2 0-1 背包问题（贪心思路通常不适用，动态规划是主流解法）

4. 贪心算法 (Greedy Algorithms)

4.1 活动选择问题（Interval Scheduling）

5. 回溯算法 (Backtracking)

5.1 求全排列

总结

2.1 深度优先搜索 (DFS) 与广度优先搜索 (BFS)