一、数据结构基础
- 线性结构
- 数组（Array）
// 1.1 查找数组最大值
public class ArrayBasics {
public static int findMax(int[] arr) {
if (arr == null || arr.length == 0) throw new IllegalArgumentException("数组为空");
int max = arr[0];
for (int num : arr) {
if (num > max) max = num;
}
return max;
}
// 1.2 计算数组平均值
public static double average(int[] arr) {
if (arr == null || arr.length == 0) return 0;
double sum = 0;
for (int num : arr) {
sum += num;
}
return sum / arr.length;
}
}
================冒泡排序=================
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环控制排序轮数
for (int i = 0; i < n - 1; i++) {
// 内层循环控制每轮比较次数
for (int j = 0; j < n - i - 1; j++) {
// 相邻元素比较并交换
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
========================快速排序（时间复杂度：O(n log n)）================
public static void main(String[] args) {
// 定义一个未排序的数组
int[] arr = {10, 7, 8, 9, 1, 5};
// 打印原始数组
System.out.println("排序前: " + Arrays.toString(arr));
// 调用快速排序方法
quickSort(arr, 0, arr.length - 1);
// 打印排序后的数组
System.out.println("排序后: " + Arrays.toString(arr));
}
// 快速排序方法
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); // 递归排序右半部分
}
}
// 分区函数
private static 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++;
// 交换元素到正确区域
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准放到中间位置
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
============线性搜索（时间复杂度：O(n)）===============
public static void main(String[] args) {
// 定义一个未排序的数组
int[] arr = {10, 7, 8, 9, 1, 5};
// 定义要查找的目标值
int target = 8;
// 调用 search 方法并存储返回值
int result = search(arr, target);
// 打印查找结果
if (result != -1) {
System.out.println("目标值 " + target + " 的索引是: " + result);
} else {
System.out.println("目标值 " + target + " 不在数组中");
}
// 打印数组内容（验证数组未被修改）
System.out.println("数组内容: " + Arrays.toString(arr));
}
/**
* 查找目标值 target 在数组中的索引
*
* @param arr 待查找的数组
* @param target 目标值
* @return 找到目标值时返回其索引，否则返回 -1
*/
public static int search(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i; // 找到目标返回索引
}
return -1; // 未找到返回-1
}
=============================2分查找=============
public static void main(String[] args) {
// 定义一个未排序的字符串数组
String[] arr = {"banana", "apple", "cherry", "date", "fig", "erape"};
// 对数组进行排序（二分查找的前提条件）
Arrays.sort(arr);
// 打印排序后的数组
System.out.println("排序后的数组: " + Arrays.toString(arr));
// 定义要查找的目标值
String target = "erape";
// 调用 binarySearch 方法并存储返回值
int result = binarySearch(arr, target);
// 打印查找结果
if (result != -1) {
System.out.println("目标值 '" + target + "' 的索引是: " + result);
} else {
System.out.println("目标值 '" + target + "' 不在数组中");
}
}
/**
* 二分查找目标字符串 target 在有序字符串数组中的索引
*
* @param sortedArr 已排序的字符串数组
* @param target 目标字符串
* @return 找到目标字符串时返回其索引，否则返回 -1
*/
public static int binarySearch(String[] sortedArr, String target) {
int left = 0, right = sortedArr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止整数溢出
System.out.println(mid);
// 使用 compareTo 方法进行字符串比较
int comparisonResult = sortedArr[mid].compareTo(target);
System.out.println(comparisonResult);
if (comparisonResult == 0) return mid; // 找到目标字符串
else if (comparisonResult < 0) left = mid + 1; // 目标在右半区
else right = mid - 1; // 目标在左半区
}
return -1;
}
==================双指针=========================
public static void main(String[] args) {
// 测试 twoSumSorted 方法
int[] nums = {1, 2, 3, 4, 5, 6};
int target = 13;
int[] result = TwoSum.twoSumSorted(nums, target);
if (result[0] != -1 && result[1] != -1) {
System.out.println("两数之和的索引是: " + result[0] + ", " + result[1]);
} else {
System.out.println("没有找到符合条件的两个数");
}
// 测试 reverse 方法
int[] arr = {1, 2, 3, 4, 5};
System.out.println("原始数组: " + Arrays.toString(arr));
ReverseArray.reverse(arr);
System.out.println("反转后的数组: " + Arrays.toString(arr));
}
}
// 1.1 两数之和（有序数组）
class TwoSum {
public static int[] twoSumSorted(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};
}
}
// 1.2 反转数组
class ReverseArray {
public static void reverse(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
==================滑动窗口算法===========
public static void main(String[] args) {
// 测试 maxSubArray 方法
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4, 8};
int maxSum = MaxSubarray.maxSubArray(nums);
System.out.println("最大子数组和是: " + maxSum);
// 测试 findAverages 方法
int[] arr = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int k = 5;
double[] averages = SlidingWindow.findAverages(arr, k);
System.out.println("滑动窗口的平均值是: " + Arrays.toString(averages));
}
}
// 2.1 最大子数组和
class MaxSubarray {
public static int maxSubArray(int[] nums) {
int maxSum = nums[0], currentSum = 0;
for (int num : nums) {
currentSum = Math.max(num, currentSum + num); // 决定是否舍弃前面部分
maxSum = Math.max(maxSum, currentSum); // 更新最大值
}
return maxSum;
}
}
// 2.2 固定窗口大小求平均值
class SlidingWindow {
public static double[] findAverages(int[] arr, int k) {
double[] result = new double[arr.length - k + 1];
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i]; // 初始化窗口和
result[0] = (double) windowSum / k;
for (int i = k; i < arr.length; i++) {
windowSum = windowSum - arr[i - k] + arr[i]; // 滑动窗口
result[i - k + 1] = (double) windowSum / k;
}
return result;
}
}
===================== 前缀和数组股票炒币==================
public static void main(String[] args) {
// 定义输入数组
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4, 8};
// 调用 calculatePrefixSum 方法计算前缀和数组
int[] prefix = calculatePrefixSum(nums);
// 打印前缀和数组
System.out.println("前缀和数组: " + Arrays.toString(prefix));
// 定义查询区间 [left, right]
int left = 2; // 区间左边界（从 0 开始）
int right = 6; // 区间右边界（从 0 开始）
// 调用 rangeSum 方法查询区间 [left, right] 的和
int sum = rangeSum(prefix, left, right);
// 打印区间和
System.out.println("区间 [" + left + ", " + right + "] 的和: " + sum);
}
/**
* 计算前缀和数组
* @param nums 输入的整数数组
* @return 返回一个长度为 nums.length + 1 的前缀和数组
*/
public static int[] calculatePrefixSum(int[] nums) {
// 初始化前缀和数组，长度为 nums.length + 1，第一个元素为 0
int[] prefix = new int[nums.length + 1];
// 遍历数组，逐个累加元素值，构造前缀和数组
for (int i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i]; // 前 i 项和存储到 prefix[i+1]
}
return prefix; // 返回前缀和数组
}
/**
* 查询区间和（左闭右闭）
* @param prefix 前缀和数组
* @param left 区间的左边界（从 0 开始）
* @param right 区间的右边界（从 0 开始）
* @return 返回区间 [left, right] 的和
*/
public static int rangeSum(int[] prefix, int left, int right) {
// 利用前缀和数组快速计算区间和
return prefix[right + 1] - prefix[left];
}
- 链表（单链表、双向链表、循环链表）
public static void main(String[] args) {
// 创建单链表实例
SingleLinkedList list = new SingleLinkedList();
// 添加节点到链表尾部
list.add(10);
list.add(20);
list.add(30);
list.add(40);
// 打印链表
System.out.println("链表内容：");
list.print();
// 按顺序插入节点
list.insertSorted(15);
list.insertSorted(5);
list.insertSorted(25);
// 打印链表
System.out.println("按顺序插入后的链表内容：");
list.print();
// 删除指定值的节点
list.delete(10);
list.delete(5);
// 打印链表
System.out.println("删除节点后的链表内容：");
list.print();
}
int data;
SingleListNode next;
public SingleListNode(int data) {
this.data = data;
this.next = null;
System.out.println(next);
System.out.println(data);
}
}
// 单链表操作类
class SingleLinkedList {
private SingleListNode head; // 头节点
// 添加节点到链表尾部
public void add(int data) {
SingleListNode newNode = new SingleListNode(data);
if (head == null) {
head = newNode; // 空链表时直接设置为头节点
} else {
SingleListNode current = head;
while (current.next != null) {
current = current.next; // 遍历到最后一个节点
}
current.next = newNode; // 尾部插入新节点[7,8](@ref)
}
}
// 按顺序插入（升序）
public void insertSorted(int data) {
SingleListNode newNode = new SingleListNode(data);
if (head == null || head.data >= data) {
newNode.next = head; // 头插法
head = newNode;
} else {
SingleListNode current = head;
while (current.next != null && current.next.data < data) {
current = current.next; // 找到插入位置的前驱节点
}
newNode.next = current.next;
current.next = newNode; // 插入新节点[7](@ref)
}
}
// 删除指定值的节点
public void delete(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next; // 删除头节点
return;
}
SingleListNode current = head;
while (current.next != null && current.next.data != data) {
current = current.next; // 找到待删除节点的前驱
}
if (current.next != null) {
current.next = current.next.next; // 跳过待删除节点[7](@ref)
}
}
// 打印链表
public void print() {
SingleListNode current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}- 栈（Stack）与队列（Queue）
public static void main(String[] args) {
// 创建一个 Integer 类型的栈，并进行一系列操作演示
ArrayStack<Integer> stack = new ArrayStack<>();
// 压栈操作
stack.push(10);
stack.push(20);
stack.push(30);
// 查看栈顶元素
System.out.println("栈顶元素：" + stack.peek());
// 弹栈操作，并打印弹出的元素
System.out.println("弹出的元素：" + stack.pop());
// 再次查看栈顶元素
System.out.println("新的栈顶元素：" + stack.peek());
// 打印栈的大小
System.out.println("栈的大小：" + stack.size());
// 检查栈是否为空
if (!stack.isEmpty()) {
System.out.println("栈不为空");
}
// 继续弹栈直到栈空
while (!stack.isEmpty()) {
System.out.println("弹出的元素：" + stack.pop());
}
// 尝试对空栈进行弹栈操作
try {
stack.pop();
} catch (RuntimeException e) {
System.out.println(e.getMessage()); // 应输出 "栈为空"
}
}
}
/***
* 基于动态数组实现的栈
* 核心特性：后进先出（LIFO），支持动态扩容[7,3](@ref)
*/
class ArrayStack<T> {
private Object[] elements; // 存储元素的数组
private int top = -1; // 栈顶指针（初始化为-1表示空栈）
public ArrayStack() {
elements = new Object[10]; // 默认容量10
System.out.println("开始");
}
/***
* 压栈操作（时间复杂度：均摊O(1)）
* @param data 待压入的元素
*/
public void push(T data) {
if (top == elements.length - 1) {
resize(); // 栈满时扩容为原容量的2倍[7](@ref)
}
elements[++top] = data;
}
/***
* 弹栈操作（时间复杂度：O(1)）
* @return 栈顶元素
*/
public T pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return (T) elements[top--];
}
/***
* 查看栈顶元素（时间复杂度：O(1)）
*/
public T peek() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return (T) elements[top];
}
/***
* 动态扩容方法（时间复杂度：O(n)）
*/
private void resize() {
Object[] newArray = new Object[elements.length * 2];
System.arraycopy(elements, 0, newArray, 0, elements.length);
elements = newArray;
}
// 其他辅助方法
public boolean isEmpty() { return top == -1; }
public int size() { return top + 1; }- 哈希表（HashMap与HashSet）
/***
* 自定义HashMap实现（支持动态扩容和红黑树优化）
* 说明：通过数组+链表/红黑树解决哈希冲突，负载因子默认0.75
*/
public class MyHashMap<K, V> {
public static void main(String[] args) {
// 测试HashMap
MyHashMap<String, Integer> map = new MyHashMap<>();
map.put("A", 1);
map.put("B", 2);
System.out.println(map.get("A")); // 输出1
}
// 默认初始容量（必须是2的幂）
private static final int DEFAULT_CAPACITY = 16;
// 默认负载因子
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转红黑树的阈值（JDK8+特性）
private static final int TREEIFY_THRESHOLD = 8;
// 哈希表存储桶数组
private Node<K, V>[] table;
// 当前存储的键值对数量
private int size;
// 扩容阈值 = capacity * loadFactor
private int threshold;
// 负载因子
private final float loadFactor;
// 链表节点定义
static class Node<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;
}
}
// 构造函数：初始化容量和负载因子
public MyHashMap(int initialCapacity, float loadFactor) {
if (initialCapacity <= 0) throw new IllegalArgumentException("Illegal capacity");
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public MyHashMap() {
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 核心方法1：插入键值对
public V put(K key, V value) {
// 1. 哈希表未初始化时进行扩容
if (table == null) resize();
int hash = hash(key);
int index = (table.length - 1) & hash; // 计算桶下标
// 2. 处理链表/红黑树冲突
Node<K, V> head = table[index];
for (Node<K, V> p = head; p != null; p = p.next) {
if (p.hash == hash && Objects.equals(p.key, key)) {
V oldValue = p.value;
p.value = value; // 更新已存在的键值对
return oldValue;
}
}
// 3. 插入新节点（头插法）
addNode(hash, key, value, index, head);
return null;
}
// 核心方法2：获取键对应的值
public V get(K key) {
Node<K, V> node = getNode(key);
return node != null ? node.value : null;
}
// 辅助方法：根据键查找节点
private Node<K, V> getNode(K key) {
if (table == null) return null;
int hash = hash(key);
int index = (table.length - 1) & hash;
for (Node<K, V> p = table[index]; p != null; p = p.next) {
if (p.hash == hash && Objects.equals(p.key, key)) {
return p;
}
}
return null;
}
// 哈希函数优化（JDK8+实现）
private int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 动态扩容方法（双倍扩容）
private void resize() {
int oldCap = (table == null) ? 0 : table.length;
int newCap = (oldCap == 0) ? threshold : oldCap << 1; // 容量翻倍
threshold = (int)(newCap * loadFactor); // 更新扩容阈值
Node<K, V>[] newTable = (Node<K, V>[]) new Node[newCap];
// 数据迁移逻辑（此处简化，实际需处理树化结构）
if (table != null) {
for (int i = 0; i < oldCap; i++) {
Node<K, V> p = table[i];
while (p != null) {
Node<K, V> next = p.next;
int idx = (newCap - 1) & p.hash;
p.next = newTable[idx];
newTable[idx] = p;
p = next;
}
}
}
table = newTable;
}
// 其他辅助方法（篇幅限制，部分省略）
private void addNode(int hash, K key, V value, int index, Node<K, V> head) {
Node<K, V> newNode = new Node<>(hash, key, value, head);
table[index] = newNode;
if (++size > threshold) resize(); // 触发扩容
// 此处可添加链表转红黑树逻辑（需实现TreeNode类）
}
// 计算最小的大于等于cap的2的幂
private int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= (1 << 30)) ? (1 << 30) : n + 1;
}
// 返回当前元素数量
public int size() { return size; }
}
- 树形结构
- 二叉树（遍历、递归与非递归实现）
/***
* 二叉树实现类（包含递归与非递归遍历）
* 整合自多篇技术文档的最佳实践
*/
public class BinaryTree {
// 静态内部类定义节点[6,8](@ref)
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
@Override
public String toString() {
return String.valueOf(val);
}
}
private TreeNode root;
// 构造方法[6](@ref)
public BinaryTree() {
this.root = null;
}
// 递归遍历组 ***************************************
public void preOrderRecursive() {
preOrderHelper(root);
System.out.println();
}
private void preOrderHelper(TreeNode node) {
if (node == null) return;
System.out.print(node.val + " "); // 根[3](@ref)
preOrderHelper(node.left); // 左[8](@ref)
preOrderHelper(node.right); // 右[1](@ref)
}
public void inOrderRecursive() {
inOrderHelper(root);
System.out.println();
}
private void inOrderHelper(TreeNode node) {
if (node == null) return;
inOrderHelper(node.left); // 左[2](@ref)
System.out.print(node.val + " "); // 根[3](@ref)
inOrderHelper(node.right); // 右[1](@ref)
}
public void postOrderRecursive() {
postOrderHelper(root);
System.out.println();
}
private void postOrderHelper(TreeNode node) {
if (node == null) return;
postOrderHelper(node.left); // 左[8](@ref)
postOrderHelper(node.right); // 右[1](@ref)
System.out.print(node.val + " "); // 根[3](@ref)
}
// 非递归遍历组 **************************************
public void preOrderNonRecursive() {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " "); // 根[2](@ref)
if (node.right != null) stack.push(node.right); // 右先入栈[5](@ref)
if (node.left != null) stack.push(node.left); // 左后入栈[2](@ref)
}
System.out.println();
}
public void inOrderNonRecursive() {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) { // 左子树全入栈[2](@ref)
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
System.out.print(cur.val + " "); // 根[5](@ref)
cur = cur.right; // 转向右[2](@ref)
}
System.out.println();
}
public void postOrderNonRecursive() {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> res = new Stack<>(); // 结果逆序栈[5](@ref)
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.push(node.val); // 根先存储[5](@ref)
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
while (!res.isEmpty()) {
System.out.print(res.pop() + " "); // 逆序输出[5](@ref)
}
System.out.println();
}
// 层序遍历[2,6](@ref)
public void levelOrder() {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
System.out.println(); // 换行显示层级[6](@ref)
}
}
// 辅助方法 *****************************************
public void buildSampleTree() {
/* 构建示例树：
1
/ \
2 3
/ \ / \
4 5 6 7
*/
root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.buildSampleTree();
System.out.println("递归前序:"); // 应输出1 2 4 5 3 6 7
tree.preOrderRecursive();
System.out.println("非递归中序:"); // 应输出4 2 5 1 6 3 7
tree.inOrderNonRecursive();
System.out.println("层序遍历:");
tree.levelOrder(); // 按层级输出
}
}- 二叉搜索树（BST）与平衡树（AVL、红黑树）
public class BinarySearchTree {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// 插入测试
int[] values = {8, 3, 10, 1, 6, 14, 4, 7, 13};
for (int val : values) {
bst.insert(val);
}
// 中序遍历输出（应显示有序序列）
System.out.print("中序遍历结果: ");
bst.inOrder(); // 输出: 1 3 4 6 7 8 10 13 14[11](@ref)
// 搜索测试
System.out.println("是否存在7? " + bst.search(7)); // true
System.out.println("是否存在5? " + bst.search(5)); // false
// 删除测试
bst.delete(6); // 删除有两个子节点的元素
System.out.print("删除6后的遍历: ");
bst.inOrder(); // 输出: 1 3 4 7 8 10 13 14
bst.delete(10); // 删除有右子树的节点
System.out.print("删除10后的遍历: ");
bst.inOrder(); // 输出: 1 3 4 7 8 13 14
}
// 树节点定义（内部类）
private class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
@Override
public String toString() {
return String.valueOf(val); // 便于打印节点值[3](@ref)
}
}
private TreeNode root; // 根节点
// 核心方法：递归插入
public void insert(int val) {
root = insertNode(root, val);
}
private TreeNode insertNode(TreeNode node, int val) {
if (node == null) return new TreeNode(val); // 创建新节点
if (val < node.val) {
node.left = insertNode(node.left, val); // 递归左子树[7](@ref)
} else if (val > node.val) {
node.right = insertNode(node.right, val); // 递归右子树[7](@ref)
}
return node; // 重复值不插入[1](@ref)
}
// 核心方法：删除节点
public void delete(int val) {
root = deleteNode(root, val);
}
private TreeNode deleteNode(TreeNode node, int val) {
if (node == null) return null;
if (val < node.val) {
node.left = deleteNode(node.left, val);
} else if (val > node.val) {
node.right = deleteNode(node.right, val);
} else {
// Case1: 无子节点或单子节点[6](@ref)
if (node.left == null) return node.right;
if (node.right == null) return node.left;
// Case2: 双子节点，找右子树最小值替换[6](@ref)
TreeNode minNode = findMin(node.right);
node.val = minNode.val;
node.right = deleteNode(node.right, node.val); // 删除替换节点
}
return node;
}
// 辅助方法：找子树最小值节点
private TreeNode findMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}
// 核心方法：搜索节点
public boolean search(int val) {
return searchNode(root, val) != null;
}
private TreeNode searchNode(TreeNode node, int val) {
if (node == null || node.val == val) return node;
return val < node.val ? searchNode(node.left, val) : searchNode(node.right, val);
}
// 遍历方法：中序遍历（升序输出）
public void inOrder() {
inOrderTraversal(root);
System.out.println();
}
private void inOrderTraversal(TreeNode node) {
if (node == null) return;
inOrderTraversal(node.left);
System.out.print(node + " ");
inOrderTraversal(node.right);
}- 堆（Heap）与优先队列（PriorityQueue）
import java.util.Arrays;
/***
* 整合堆(Heap)与优先队列(PriorityQueue)的完整实现类
* 包含main方法演示运行
*/
public class HeapAndPriorityQueueDemo {
//========================= 大顶堆实现 =========================//
public static class MaxHeap {
private int[] heap;
private int capacity;
private int size;
public MaxHeap(int capacity) {
this.capacity = capacity;
this.heap = new int[capacity];
this.size = 0;
}
// 插入元素（上浮调整）
public void insert(int key) {
if (size == capacity) throw new IllegalStateException("Heap is full");
int i = size;
heap[size++] = key;
// 上浮调整
while (i != 0 && heap[parent(i)] < heap[i]) {
swap(parent(i), i);
i = parent(i);
}
}
// 提取最大值（下沉调整）
public int extractMax() {
if (size <= 0) throw new IllegalStateException("Heap is empty");
if (size == 1) return heap[--size];
int root = heap[0];
heap[0] = heap[--size];
maxHeapify(0);
return root;
}
// 堆化调整
private void maxHeapify(int i) {
int largest = i;
int l = leftChild(i);
int r = rightChild(i);
if (l < size && heap[l] > heap[largest]) largest = l;
if (r < size && heap[r] > heap[largest]) largest = r;
if (largest != i) {
swap(i, largest);
maxHeapify(largest);
}
}
// 辅助方法
private int parent(int i) { return (i-1)/2; }
private int leftChild(int i) { return 2*i + 1; }
private int rightChild(int i) { return 2*i + 2; }
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
//========================= 泛型优先队列实现 =========================//
public static class PriorityQueue<E extends Comparable<E>> {
private Object[] heap;
private int size;
private static final int DEFAULT_CAPACITY = 11;
public PriorityQueue() {
this(DEFAULT_CAPACITY);
}
public PriorityQueue(int initialCapacity) {
this.heap = new Object[initialCapacity];
this.size = 0;
}
// 添加元素（上浮调整）
public void offer(E e) {
if (e == null) throw new NullPointerException();
if (size >= heap.length) grow();
int i = size;
heap[size++] = e;
// 上浮逻辑
while (i > 0) {
int parent = (i - 1) >>> 1;
E p = (E) heap[parent];
if (e.compareTo(p) <= 0) break;
heap[i] = p;
i = parent;
}
heap[i] = e;
}
// 弹出最大元素（下沉调整）
public E poll() {
if (size == 0) return null;
E result = (E) heap[0];
E x = (E) heap[--size];
heap[size] = null;
if (size > 0) {
int i = 0;
int half = size >>> 1;
while (i < half) {
int child = (i << 1) + 1;
Object c = heap[child];
int right = child + 1;
if (right < size &&
((Comparable<E>) c).compareTo((E) heap[right]) < 0) {
c = heap[child = right];
}
if (x.compareTo((E) c) >= 0) break;
heap[i] = c;
i = child;
}
heap[i] = x;
}
return result;
}
// 动态扩容
private void grow() {
int newCapacity = size + (size >> 1);
heap = Arrays.copyOf(heap, newCapacity);
}
}
//========================= 主运行方法 =========================//
public static void main(String[] args) {
System.out.println("=== 测试大顶堆 ===");
MaxHeap maxHeap = new MaxHeap(10);
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(8);
System.out.println("提取最大值: " + maxHeap.extractMax()); // 8
System.out.println("剩余最大值: " + maxHeap.extractMax()); // 5
System.out.println("\n=== 测试优先队列 ===");
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(3);
pq.offer(8);
System.out.println("弹出元素: " + pq.poll()); // 8
System.out.println("剩余元素: " + pq.poll()); // 5
}
}- Trie树（字典树）
import java.util.Arrays;
/***
* Trie树（字典树）实现
* 功能：高效存储和检索字符串，支持前缀匹配
*/
public class Trie {
// Trie节点内部类
private static class TrieNode {
TrieNode[] children; // 子节点数组（26个小写字母）
boolean isEnd; // 标记是否是单词结尾
public TrieNode() {
children = new TrieNode[26]; // 每个节点最多26个子节点（a-z）
isEnd = false;
Arrays.fill(children, null); // 初始化子节点数组
}
}
private final TrieNode root; // 根节点（空节点）
public Trie() {
root = new TrieNode(); // 初始化根节点
}
/***
* 插入单词到Trie树
* @param word 要插入的单词（仅支持小写字母）
*/
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
int index = c - 'a'; // 计算字符对应的数组索引
// 如果对应字符的子节点不存在则创建新节点
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index]; // 移动到子节点
}
node.isEnd = true; // 标记单词结束
}
/***
* 搜索完整单词
* @param word 要搜索的单词
* @return 是否存在该单词
*/
public boolean search(String word) {
TrieNode node = traverse(word);
return node != null && node.isEnd; // 必须存在且是单词结尾[1,5](@ref)
}
/***
* 检查是否存在指定前缀
* @param prefix 要检查的前缀
* @return 是否存在该前缀
*/
public boolean startsWith(String prefix) {
return traverse(prefix) != null; // 只需路径存在[8](@ref)
}
// 辅助方法：遍历字符串路径
private TrieNode traverse(String str) {
TrieNode node = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
if (node.children[index] == null) {
return null; // 路径中断
}
node = node.children[index];
}
return node;
}
/***
* 测试方法
*/
public static void main(String[] args) {
Trie trie = new Trie();
// 插入测试
trie.insert("apple");
trie.insert("app");
trie.insert("banana");
// 搜索测试
System.out.println("Search 'apple': " + trie.search("apple")); // true
System.out.println("Search 'app': " + trie.search("app")); // true
System.out.println("Search 'appl': " + trie.search("appl")); // false
// 前缀测试
System.out.println("Prefix 'app': " + trie.startsWith("app")); // true
System.out.println("Prefix 'bana': " + trie.startsWith("bana")); // true
System.out.println("Prefix 'cat': " + trie.startsWith("cat")); // false
}
}- 图结构
- 图的表示（邻接矩阵、邻接表）
import java.util.LinkedList;
/***
* 图的两种表示方式实现类
* 功能：支持邻接矩阵和邻接表表示的无向图
*/
public class Graph {
// 邻接矩阵（适用于稠密图）
private int[][] adjMatrix;
// 邻接表（适用于稀疏图）
private LinkedList<Integer>[] adjList;
private int vertexCount; // 顶点数量
/***
* 构造函数初始化图结构
* @param vertexCount 顶点总数
*/
public Graph(int vertexCount) {
this.vertexCount = vertexCount;
// 初始化邻接矩阵（默认为0）
adjMatrix = new int[vertexCount][vertexCount];
// 初始化邻接表（每个顶点对应一个链表）
adjList = new LinkedList[vertexCount];
for (int i = 0; i < vertexCount; i++) {
adjList[i] = new LinkedList<>();
}
}
/***
* 添加边（无向图需双向处理）
* @param src 起点
* @param dest 终点
*/
public void addEdge(int src, int dest) {
// 邻接矩阵处理
adjMatrix[src][dest] = 1;
adjMatrix[dest][src] = 1; // 无向图对称
// 邻接表处理
adjList[src].add(dest);
adjList[dest].add(src); // 无向图双向添加
}
/***
* 打印邻接矩阵
*/
public void printAdjMatrix() {
System.out.println("邻接矩阵：");
for (int i = 0; i < vertexCount; i++) {
for (int j = 0; j < vertexCount; j++) {
System.out.print(adjMatrix[i][j] + " ");
}
System.out.println();
}
}
/***
* 打印邻接表
*/
public void printAdjList() {
System.out.println("\n邻接表：");
for (int i = 0; i < vertexCount; i++) {
System.out.print("顶点" + i + "的邻居：");
for (Integer neighbor : adjList[i]) {
System.out.print(neighbor + " ");
}
System.out.println();
}
}
/***
* 测试方法
*/
public static void main(String[] args) {
// 创建包含5个顶点的图
Graph graph = new Graph(5);
// 添加边（模拟无向图）
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(3, 4);
// 输出两种表示方式
graph.printAdjMatrix();
graph.printAdjList();
}
}- 图的遍历（DFS、BFS）
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/***
* 图的遍历实现类（包含DFS和BFS）
* 功能：基于邻接表实现图的深度优先遍历和广度优先遍历
*/
public class GraphTraversal {
// 邻接表存储结构
private LinkedList<Integer>[] adjList;
private int vertexCount; // 顶点总数
private boolean[] visited; // 访问标记数组
/***
* 构造函数初始化图
* @param vertexCount 顶点数量
*/
public GraphTraversal(int vertexCount) {
this.vertexCount = vertexCount;
adjList = new LinkedList[vertexCount];
visited = new boolean[vertexCount];
// 初始化邻接表
for (int i = 0; i < vertexCount; i++) {
adjList[i] = new LinkedList<>();
}
}
/***
* 添加边（无向图双向处理）
* @param src 起点
* @param dest 终点
*/
public void addEdge(int src, int dest) {
adjList[src].add(dest);
adjList[dest].add(src); // 无向图需双向添加
}
/***
* 深度优先搜索（递归实现）[1,6](@ref)
*/
public void dfsRecursive(int start) {
resetVisited(); // 重置访问标记
System.out.print("递归DFS: ");
dfsUtil(start);
System.out.println();
}
// DFS递归辅助方法
private void dfsUtil(int vertex) {
visited[vertex] = true;
System.out.print(vertex + " ");
for (int neighbor : adjList[vertex]) {
if (!visited[neighbor]) {
dfsUtil(neighbor);
}
}
}
/***
* 深度优先搜索（栈实现）[6,7](@ref)
*/
public void dfsStack(int start) {
resetVisited();
Stack<Integer> stack = new Stack<>();
System.out.print("栈DFS: ");
stack.push(start);
visited[start] = true;
while (!stack.isEmpty()) {
int current = stack.pop();
System.out.print(current + " ");
// 反向遍历保证与递归顺序一致
for (int i = adjList[current].size()-1; i >= 0; i--) {
int neighbor = adjList[current].get(i);
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
}
}
System.out.println();
}
/***
* 广度优先搜索（队列实现）[8,10](@ref)
*/
public void bfs(int start) {
resetVisited();
Queue<Integer> queue = new LinkedList<>();
System.out.print("BFS: ");
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.print(current + " ");
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
System.out.println();
}
// 重置访问标记数组
private void resetVisited() {
for (int i = 0; i < vertexCount; i++) {
visited[i] = false;
}
}
/***
* 测试方法
*/
public static void main(String[] args) {
// 创建包含6个顶点的图
GraphTraversal graph = new GraphTraversal(6);
// 添加边（构建测试图）
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 4);
// 执行遍历测试
graph.dfsRecursive(0); // 从顶点0开始递归DFS
graph.dfsStack(0); // 从顶点0开始栈DFS
graph.bfs(0); // 从顶点0开始BFS
}
}- 最短路径算法（Dijkstra、Floyd-Warshall）
import java.util.Arrays;
import java.util.PriorityQueue;
/***
* 最短路径算法实现类
* 功能：Dijkstra算法（单源最短路径）和Floyd-Warshall算法（全源最短路径）
*/
public class ShortestPathAlgorithms {
private static final int INF = Integer.MAX_VALUE / 2; // 防止加法溢出
/***
* Dijkstra算法实现（堆优化版）
* @param graph 邻接矩阵表示的图
* @param start 起始顶点编号
* @return 最短距离数组（无法到达的顶点返回INF）
*/
public static int[] dijkstra(int[][] graph, int start) {
int n = graph.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, INF);
dist[start] = 0;
// 优先队列优化：存储[顶点, 距离]并按距离排序
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.add(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int u = current[0];
if (visited[u]) continue;
visited[u] = true;
for (int v = 0; v < n; v++) {
// 仅处理邻接顶点且未访问的节点
if (graph[u][v] != 0 && !visited[v]) {
int newDist = dist[u] + graph[u][v];
if (newDist < dist[v]) {
dist[v] = newDist;
pq.add(new int[]{v, newDist}); // 允许重复入队，旧数据自动失效
}
}
}
}
return dist;
}
/***
* Floyd-Warshall算法实现
* @param graph 邻接矩阵表示的图（0表示无直接边）
* @return 包含两个结果：[0]最短距离矩阵，[1]是否存在负权环
*/
public static Object[] floydWarshall(int[][] graph) {
int n = graph.length;
int[][] dist = new int[n][n];
// 初始化距离矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = (i == j) ? 0 : (graph[i][j] != 0 ? graph[i][j] : INF);
}
}
// 动态规划核心：三重循环更新路径
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// 检测负权环（对角线存在负数）
boolean hasNegativeCycle = false;
for (int i = 0; i < n; i++) {
if (dist[i][i] < 0) {
hasNegativeCycle = true;
break;
}
}
return new Object[]{dist, hasNegativeCycle};
}
/***
* 测试方法
*/
public static void main(String[] args) {
// 测试图结构（与示例1对应）
int[][] graph = {
{0, 4, 0, 0, 0, 0},
{4, 0, 8, 0, 0, 0},
{0, 8, 0, 7, 0, 4},
{0, 0, 7, 0, 9, 14},
{0, 0, 0, 9, 0, 10},
{0, 0, 4, 14, 10, 0}
};
// Dijkstra测试（从顶点0出发）
System.out.println("Dijkstra算法结果：");
int[] dijkstraResult = dijkstra(graph, 0);
for (int i = 0; i < dijkstraResult.length; i++) {
System.out.printf("0->%d: %d\n", i, dijkstraResult[i]);
}
// Floyd-Warshall测试
System.out.println("\nFloyd-Warshall算法结果：");
Object[] floydResult = floydWarshall(graph);
int[][] fwDist = (int[][]) floydResult[0];
for (int i = 0; i < fwDist.length; i++) {
System.out.println(Arrays.toString(fwDist[i]));
}
System.out.println("存在负权环：" + floydResult[1]);
}
}- 最小生成树（Prim、Kruskal）
import java.util.*;
/***
* 最小生成树算法实现类（包含Prim和Kruskal算法）
*/
public class MinimumSpanningTree {
// 邻接矩阵存储图结构
private int[][] graph;
// 顶点数量
private int vertexCount;
// 边集合（用于Kruskal算法）
private List<Edge> edges = new ArrayList<>();
/***
* 构造函数初始化图
* @param vertexCount 顶点数量
* @param inputEdges 边集合（格式：{{start1, end1, weight1}, ...}）
*/
public MinimumSpanningTree(int vertexCount, int[][] inputEdges) {
this.vertexCount = vertexCount;
graph = new int[vertexCount][vertexCount];
// 初始化邻接矩阵（用Integer.MAX_VALUE表示不连通）
for (int[] row : graph) Arrays.fill(row, Integer.MAX_VALUE);
// 添加边到邻接矩阵和边集合
for (int[] edge : inputEdges) {
int u = edge[0], v = edge[1], w = edge[2];
graph[u][v] = w;
graph[v][u] = w;
edges.add(new Edge(u, v, w));
}
}
/***
* Prim算法实现（时间复杂度O(V^2)）
* @return 最小生成树的边集合
*/
public List<Edge> primMST() {
boolean[] visited = new boolean[vertexCount]; // 顶点访问标记
int[] parent = new int[vertexCount]; // 父节点数组
int[] key = new int[vertexCount]; // 各顶点到树的最小权重
Arrays.fill(key, Integer.MAX_VALUE);
key[0] = 0; // 从顶点0开始生成
parent[0] = -1;
for (int count = 0; count < vertexCount - 1; count++) {
int u = findMinKey(key, visited); // 找到未访问的最小key顶点
visited[u] = true;
// 更新邻接顶点的key值
for (int v = 0; v < vertexCount; v++) {
if (graph[u][v] != Integer.MAX_VALUE && !visited[v]
&& graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
return buildMSTEdges(parent);
}
/***
* Kruskal算法实现（时间复杂度O(E log E)）
* @return 最小生成树的边集合
*/
public List<Edge> kruskalMST() {
List<Edge> result = new ArrayList<>();
Collections.sort(edges); // 边按权重升序排序
UnionFind uf = new UnionFind(vertexCount);
for (Edge edge : edges) {
if (uf.find(edge.u) != uf.find(edge.v)) {
result.add(edge);
uf.union(edge.u, edge.v);
if (result.size() == vertexCount - 1) break;
}
}
return result;
}
// 辅助方法：找到未访问的最小key顶点
private int findMinKey(int[] key, boolean[] visited) {
int min = Integer.MAX_VALUE, minIndex = -1;
for (int v = 0; v < vertexCount; v++) {
if (!visited[v] && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}
// 辅助方法：构建MST边集合
private List<Edge> buildMSTEdges(int[] parent) {
List<Edge> mstEdges = new ArrayList<>();
for (int v = 1; v < vertexCount; v++) {
mstEdges.add(new Edge(parent[v], v, graph[parent[v]][v]));
}
return mstEdges;
}
/***
* 边数据结构（实现Comparable接口用于排序）
*/
static class Edge implements Comparable<Edge> {
int u, v, w;
public Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.w, other.w);
}
@Override
public String toString() {
return u + "-" + v + " (" + w + ")";
}
}
/***
* 并查集实现（用于Kruskal算法检测环）
*/
static class UnionFind {
int[] parent;
public UnionFind(int size) {
parent = new int[size];
for (int i = 0; i < size; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}
/***
* 测试方法
*/
public static void main(String[] args) {
// 测试图数据（示例与网页4相同）
int[][] edges = {
{0,1,2}, {0,2,2}, {0,3,3}, {1,2,4}, {2,3,3}
};
MinimumSpanningTree mst = new MinimumSpanningTree(4, edges);
System.out.println("Prim算法结果：");
mst.primMST().forEach(System.out::println);
System.out.println("\nKruskal算法结果：");
mst.kruskalMST().forEach(System.out::println);
}
}二、排序与搜索算法
- 经典排序算法
- 冒泡排序（Bubble Sort）
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环控制排序轮数
for (int i = 0; i < n - 1; i++) {
// 内层循环控制每轮比较次数
for (int j = 0; j < n - i - 1; j++) {
// 相邻元素比较并交换
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}- 选择排序（Selection Sort）
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
int minIndex = i;
// 在未排序部分寻找最小值[7,8](@ref)
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换元素位置[3](@ref)
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}- 插入排序（Insertion Sort）
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i-1;
// 将元素插入有序序列[9,11](@ref)
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}- 希尔排序（Shell Sort）
public static void shellSort(int[] arr) {
int n = arr.length;
// 动态定义间隔序列[12,14](@ref)
for (int gap = n/2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j-gap] > temp; j -= gap) {
arr[j] = arr[j-gap];
}
arr[j] = temp;
}
}
}- 归并排序（Merge Sort）
public static void mergeSort(int[] arr) {
if (arr.length < 2) return;
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
// 合并两个有序数组[16,17](@ref)
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
}- 快速排序（Quick Sort）
public static void main(String[] args) {
// 定义一个未排序的数组
int[] arr = {10, 7, 8, 9, 1, 5};
// 打印原始数组
System.out.println("排序前: " + Arrays.toString(arr));
// 调用快速排序方法
quickSort(arr, 0, arr.length - 1);
// 打印排序后的数组
System.out.println("排序后: " + Arrays.toString(arr));
}
// 快速排序方法
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); // 递归排序右半部分
}
}
int[] originalArray = {64, 25, 12, 22, 11};
// 测试归并排序
int[] arr4 = Arrays.copyOf(originalArray, originalArray.length);
mergeSort(arr4);
System.out.println("归并排序结果: " + Arrays.toString(arr4));
// 分区函数
private static 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++;
// 交换元素到正确区域
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准放到中间位置
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
=============================================================
/***
* 综合实现二叉搜索树、AVL树、红黑树的类
* 通过TreeType参数控制具体实现类型
*/
public class BalancedTree {
private Node root;
private final TreeType type;
// 树类型枚举
public enum TreeType {
BST, AVL, RED_BLACK
}
// 节点内部类（整合BST/AVL/红黑树属性）
private class Node {
int key;
Node left, right;
int height; // AVL树使用
boolean color; // 红黑树使用(true=红，false=黑)
Node(int key) {
this.key = key;
this.height = 1; // AVL初始高度
this.color = true; // 红黑树默认红色
}
@Override
public String toString() {
String colorMark = (type == TreeType.RED_BLACK) ?
(color ? "(R)" : "(B)") : "";
String heightMark = (type == TreeType.AVL) ?
"[h=" + height + "]" : "";
return key + colorMark + heightMark;
}
}
public BalancedTree(TreeType type) {
this.type = type;
}
// 核心插入方法
public void insert(int key) {
root = insert(root, key);
if (type == TreeType.RED_BLACK) {
root.color = false; // 红黑树根始终为黑[12](@ref)
}
}
private Node insert(Node node, int key) {
if (node == null) return new Node(key);
// 标准BST插入逻辑
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
} else {
return node; // 重复值不插入
}
// 根据类型进行平衡处理
switch (type) {
case AVL: return avlBalance(node);
case RED_BLACK: return rbBalance(node);
default: return node; // BST无需平衡
}
}
// AVL树平衡逻辑（基于高度差）
private Node avlBalance(Node node) {
updateHeight(node);
int balance = getBalance(node);
// 左左失衡（右旋）
if (balance > 1 && getBalance(node.left) >= 0) {
return rightRotate(node);
}
// 右右失衡（左旋）
if (balance < -1 && getBalance(node.right) <= 0) {
return leftRotate(node);
}
// 左右失衡（先左旋后右旋）
if (balance > 1 && getBalance(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// 右左失衡（先右旋后左旋）
if (balance < -1 && getBalance(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
// 红黑树平衡逻辑（颜色翻转与旋转）
private Node rbBalance(Node node) {
// 情况1：父节点与叔节点均为红
if (isRed(node.right) && isRed(node.left)) {
flipColors(node);
}
// 右子红且左子黑（左旋）
if (isRed(node.right) && !isRed(node.left)) {
node = leftRotate(node);
}
// 左子红且左孙红（右旋）
if (isRed(node.left) && isRed(node.left.left)) {
node = rightRotate(node);
}
return node;
}
// 通用左旋方法（同时处理AVL高度和红黑颜色）
private Node leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
// AVL高度更新
updateHeight(x);
updateHeight(y);
// 红黑颜色调整
if (type == TreeType.RED_BLACK) {
y.color = x.color;
x.color = true;
}
return y;
}
// 通用右旋方法（镜像对称逻辑）
private Node rightRotate(Node y) {
Node x = y.left;
y.left = x.right;
x.right = y;
updateHeight(y);
updateHeight(x);
if (type == TreeType.RED_BLACK) {
x.color = y.color;
y.color = true;
}
return x;
}
// 辅助方法
private void updateHeight(Node node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}
private int height(Node node) {
return (node == null) ? 0 : node.height;
}
private int getBalance(Node node) {
return height(node.left) - height(node.right);
}
private boolean isRed(Node node) {
return node != null && node.color;
}
private void flipColors(Node node) {
node.color = !node.color;
if (node.left != null) node.left.color = !node.left.color;
if (node.right != null) node.right.color = !node.right.color;
}
// 测试用例
public static void main(String[] args) {
// AVL树测试
BalancedTree avlTree = new BalancedTree(TreeType.AVL);
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30); // 触发左旋平衡[11](@ref)
System.out.println("AVL根节点：" + avlTree.root); // 输出：20[h=2]
// 红黑树测试
BalancedTree rbTree = new BalancedTree(TreeType.RED_BLACK);
rbTree.insert(10);
rbTree.insert(20);
rbTree.insert(30); // 触发颜色翻转与旋转[14](@ref)
System.out.println(rbTree.root);
}
- 堆排序（Heap Sort）
public class HeapSort {
public static void main(String[] args) {
int[] arr = {42, 13, 23, 51, 1, 0, 6, 94, 69, 99};
System.out.println("原始数组:");
printArray(arr);
heapSort(arr);
System.out.println("\n排序后数组:");
printArray(arr);
}
// 堆排序主函数
public static void heapSort(int[] arr) {
int n = arr.length;
// 步骤1：构建大顶堆（从最后一个非叶子节点开始调整）
// 最后一个非叶子节点索引计算公式：n/2 -1[3,6](@ref)
for (int i = n/2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 步骤2：逐个提取堆顶元素（最大值）并调整堆结构
for (int i = n-1; i > 0; i--) {
// 将当前堆顶元素与末尾元素交换[1,6](@ref)
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整剩余元素使其保持堆性质
heapify(arr, i, 0);
}
}
/***
* 堆化操作（调整以root为根的子树成为大顶堆）
* @param arr 待排序数组
* @param heapSize 当前堆的大小
* @param root 当前子树的根节点索引
*/
private static void heapify(int[] arr, int heapSize, int root) {
int largest = root; // 初始化最大元素为根节点
int leftChild = 2 * root + 1; // 左子节点索引[1,3](@ref)
int rightChild = 2 * root + 2; // 右子节点索引
// 比较左子节点与当前最大值
if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
// 比较右子节点与当前最大值
if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
// 如果最大值不是根节点，则交换并递归调整受影响的子树[6](@ref)
if (largest != root) {
int swap = arr[root];
arr[root] = arr[largest];
arr[largest] = swap;
// 递归调整被破坏的子堆结构
heapify(arr, heapSize, largest);
}
}
// 辅助方法：打印数组
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}- 非比较排序（计数排序、桶排序、基数排序）
public class CountingSort {
public static void countingSort(int[] arr) {
// 步骤1：找出最大最小值[7,8](@ref)
int min = arr[0], max = arr[0];
for (int num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
// 步骤2：创建计数数组[6,7](@ref)
int[] count = new int[max - min + 1];
// 步骤3：统计元素出现次数[6,8](@ref)
for (int num : arr) {
count[num - min]++; // 将元素映射到0~k的索引范围
}
// 步骤4：重构排序数组[6,7](@ref)
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i + min; // 恢复原始数值
count[i]--;
}
}
}
public static void main(String[] args) {
int[] arr = {4, -2, 2, 8, 3, 3, 1, -5};
System.out.println("原始数组：" + Arrays.toString(arr));
countingSort(arr);
System.out.println("排序后：" + Arrays.toString(arr));
}
}- 查找算法
- 线性查找与二分查找
public class LinearSearchExample {
/**
* 线性查找实现
* @param arr 待查找数组（允许无序）
* @param target 目标值
* @return 目标值索引，未找到返回-1
*/
public static int linearSearch(int[] arr, int target) {
// 处理空数组边界情况
if (arr == null || arr.length == 0) return -1;
// 遍历数组元素
for (int i = 0; i < arr.length; i++) {
// 若当前元素等于目标值，立即返回索引
if (arr[i] == target) {
return i;
}
}
// 遍历完成后未找到返回-1
return -1;
}
public static void main(String[] args) {
// 测试用例
int[] arr = {5, 3, 8, 6, 2, 9}; // 待查找数组
int target = 6; // 目标值
// 调用线性查找方法
int result = linearSearch(arr, target);
// 输出结果
if (result != -1) {
System.out.println("目标值 " + target + " 的索引为: " + result);
} else {
System.out.println("目标值 " + target + " 未找到");
}
// 测试其他情况
target = 10; // 测试未找到的情况
result = linearSearch(arr, target);
if (result != -1) {
System.out.println("目标值 " + target + " 的索引为: " + result);
} else {
System.out.println("目标值 " + target + " 未找到");
}
// 测试空数组
int[] emptyArray = {};
target = 5;
result = linearSearch(emptyArray, target);
if (result != -1) {
System.out.println("目标值 " + target + " 的索引为: " + result);
} else {
System.out.println("目标值 " + target + " 未找到（空数组）");
}
}
}
=======================================================================
/**
* 线性查找实现
* @param arr 待查找数组（允许无序）
* @param target 目标值
* @return 目标值索引，未找到返回-1
*/
public static int linearSearch(int[] arr, int target) {
// 处理空数组边界情况
if (arr == null || arr.length == 0) return -1;
// 遍历数组元素
for (int i = 0; i < arr.length; i++) {
// 若当前元素等于目标值，立即返回索引
if (arr[i] == target) {
return i;
}
}
// 遍历完成后未找到返回-1
return -1;
}
/***
* 二分查找递归实现
* @param arr 已排序数组
* @param target 目标值
* @param left 当前查找区间左边界
* @param right 当前查找区间右边界
* @return 目标值索引，未找到返回-1
*/
public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
// 终止条件：区间无效
if (left > right) return -1;
int mid = (left + right) >>> 1;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right); // 右半区递归
} else {
return binarySearchRecursive(arr, target, left, mid - 1); // 左半区递归
}
}
/***
* 二分查找实现（升序数组）
* @param arr 已排序的升序数组
* @param target 目标值
* @return 目标值索引，未找到返回-1
*/
public static int binarySearch(int[] arr, int target) {
// 处理空数组边界情况
if (arr == null || arr.length == 0) return -1;
int left = 0; // 左边界初始为数组首
int right = arr.length - 1; // 右边界初始为数组尾
while (left <= right) { // 注意循环条件包含等于[1,4](@ref)
// 计算中间索引（防溢出写法）
int mid = (left + right) >>> 1; // 等价于 left + (right - left)/2[1](@ref)
if (arr[mid] == target) {
return mid; // 找到目标直接返回
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右半区，调整左边界
} else {
right = mid - 1; // 目标在左半区，调整右边界
}
}
return -1; // 未找到返回-1
}
public static void main(String[] args) {
// 测试线性查找
int[] unorderedArr = {7, 3, 9, 2, 5};
System.out.println("线性查找 9 的索引: " + linearSearch(unorderedArr, 9)); // 输出2
// 测试二分查找
int[] sortedArr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
System.out.println("二分查找 23 的索引: " + binarySearch(sortedArr, 23)); // 输出5
System.out.println("递归二分查找 91 的索引: " +
binarySearchRecursive(sortedArr, 91, 0, sortedArr.length-1)); // 输出9
// 测试未找到的情况
System.out.println("查找不存在的 100: " + binarySearch(sortedArr, 100)); // 输出-1
}
- 哈希查找（冲突解决策略）
/***
* 哈希表实现集合类（包含链地址法和线性探测法）
* @author chenx
* @since 2025/04/06
*/
public class CombinedHashTable {
/*--------------- 链地址法实现 ---------------*/
public static class ChainingHashTable<K, V> {
private LinkedList<Entry<K, V>>[] table;
private int capacity;
private double loadFactor = 0.75;
private int size;
public ChainingHashTable() {
this(11);
}
public ChainingHashTable(int capacity) {
this.capacity = nextPrime(capacity);
table = new LinkedList[this.capacity];
initializeBuckets();
}
// 初始化桶数组
private void initializeBuckets() {
for (int i = 0; i < capacity; i++) {
table[i] = new LinkedList<>();
}
}
// 哈希函数（带符号位处理）
private int hash(K key) {
return (key.hashCode() & 0x7fffffff) % capacity; // 确保非负值[7](@ref)
}
public void put(K key, V value) {
if ((double)size / capacity > loadFactor) {
resize(2 * capacity); // 触发两倍扩容[8](@ref)
}
int index = hash(key);
LinkedList<Entry<K, V>> bucket = table[index];
// 遍历链表更新已存在键
for (Entry<K, V> entry : bucket) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
bucket.add(new Entry<>(key, value));
size++;
}
public V get(K key) {
int index = hash(key);
for (Entry<K, V> entry : table[index]) {
if (entry.key.equals(key)) {
return entry.value;
}
}
return null;
}
// 动态扩容方法
private void resize(int newCapacity) {
newCapacity = nextPrime(newCapacity);
LinkedList<Entry<K, V>>[] newTable = new LinkedList[newCapacity];
for (int i = 0; i < newCapacity; i++) {
newTable[i] = new LinkedList<>();
}
// 重新哈希所有元素
for (LinkedList<Entry<K, V>> bucket : table) {
for (Entry<K, V> entry : bucket) {
int newIndex = (entry.key.hashCode() & 0x7fffffff) % newCapacity;
newTable[newIndex].add(entry);
}
}
table = newTable;
capacity = newCapacity;
}
}
/*--------------- 线性探测法实现 ---------------*/
public static class LinearProbingHashTable<K, V> {
private Entry<K, V>[] table;
private int capacity;
private int size;
private double loadFactor = 0.75;
public LinearProbingHashTable(int capacity) {
this.capacity = nextPrime(capacity);
table = new Entry[this.capacity];
}
private int hash(K key) {
return (key.hashCode() & 0x7fffffff) % capacity; // 同链地址法哈希处理[7](@ref)
}
public void put(K key, V value) {
if (size >= capacity * loadFactor) {
resize(2 * capacity); // 线性探测扩容[6](@ref)
}
int index = hash(key);
// 线性探测寻找空位[3](@ref)
while (table[index] != null && !table[index].key.equals(key)) {
index = (index + 1) % capacity;
}
if (table[index] == null) {
size++;
}
table[index] = new Entry<>(key, value);
}
public V get(K key) {
int index = hash(key);
int start = index;
while (table[index] != null) {
if (table[index].key.equals(key)) {
return table[index].value;
}
index = (index + 1) % capacity;
if (index == start) break; // 避免无限循环
}
return null;
}
// 线性探测扩容方法
private void resize(int newCapacity) {
newCapacity = nextPrime(newCapacity);
Entry<K, V>[] newTable = new Entry[newCapacity];
for (Entry<K, V> entry : table) {
if (entry != null) {
int index = (entry.key.hashCode() & 0x7fffffff) % newCapacity;
while (newTable[index] != null) {
index = (index + 1) % newCapacity;
}
newTable[index] = entry;
}
}
table = newTable;
capacity = newCapacity;
}
}
/*--------------- 公共工具方法 ---------------*/
// 内部键值对类
private static class Entry<K, V> {
final K key;
V value;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
// 素数计算（优化版）
private static int nextPrime(int n) {
if (n <= 1) return 2;
while (!isPrime(n)) n++;
return n;
}
private static boolean isPrime(int n) {
if (n <= 3) return n > 1;
if (n%2 == 0 || n%3 == 0) return false;
for(int i=5; i*i<=n; i+=6) {
if(n%i == 0 || n%(i+2) == 0)
return false;
}
return true;
}
/*--------------- 测试用例 ---------------*/
public static void main(String[] args) {
// 链地址法测试
ChainingHashTable<String, Integer> chainTable = new ChainingHashTable<>();
chainTable.put("apple", 10);
chainTable.put("banana", 20);
chainTable.put("apricot", 30);
System.out.println("链地址法查找apricot: " + chainTable.get("apricot")); // 输出30
// 线性探测法测试
LinearProbingHashTable<String, Integer> linearTable = new LinearProbingHashTable<>(10);
linearTable.put("cat", 100);
linearTable.put("dog", 200);
linearTable.put("cow", 300);
System.out.println("线性探测查找cow: " + linearTable.get("cow")); // 输出300
}
}- 插值查找与斐波那契查找
/***
* 高级查找算法实现类
* 包含插值查找和斐波那契查找两种算法
* @author chenx
* @since 2025/04/07
*/
public class AdvancedSearch {
// region 插值查找实现
/***
* 插值查找算法（迭代实现）
* 时间复杂度：O(log log n) 最优情况，O(n) 最坏情况
* @param arr 有序数组（必须升序排列）
* @param key 查找目标值
* @return 目标值索引，未找到返回-1
*/
public static int interpolationSearch(int[] arr, int key) {
int left = 0;
int right = arr.length - 1;
// 提前排除越界情况和空数组
if (arr.length == 0 || key < arr[left] || key > arr[right]) {
return -1;
}
while (left <= right) {
// 处理分母为零的特殊情况（所有元素相同）
if (arr[left] == arr[right]) {
return (arr[left] == key) ? left : -1;
}
// 计算插值位置（核心公式）
int mid = left + ((key - arr[left]) * (right - left)) / (arr[right] - arr[left]);
// 防止计算越界
mid = Math.max(left, Math.min(mid, right));
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1; // 右半区继续查找
} else {
right = mid - 1; // 左半区继续查找
}
}
return -1;
}
// endregion
// region 斐波那契查找实现
private static final int FIB_MAX = 20; // 预生成斐波那契数列长度
/***
* 斐波那契查找算法
* 时间复杂度：O(log n)
* @param arr 有序数组（必须升序排列）
* @param key 查找目标值
* @return 目标值索引，未找到返回-1
*/
public static int fibonacciSearch(int[] arr, int key) {
int[] fib = generateFibonacci(); // 生成斐波那契数列
int left = 0;
int right = arr.length - 1;
int k = 0; // 斐波那契数列索引
// 寻找满足F(k)-1 >= arr.length的最小k值
while (right > fib[k] - 1) {
k++;
}
// 扩展数组到F(k)-1的长度
int[] temp = Arrays.copyOf(arr, fib[k] - 1);
Arrays.fill(temp, right + 1, temp.length, arr[right]);
while (left <= right) {
int mid = left + fib[k - 1] - 1; // 黄金分割点
if (key < temp[mid]) { // 左半区查找
right = mid - 1;
k -= 1; // F(k-1)区域
} else if (key > temp[mid]) { // 右半区查找
left = mid + 1;
k -= 2; // F(k-2)区域
} else { // 找到目标值
return Math.min(mid, right); // 处理扩展数组的情况
}
}
return -1;
}
/***
* 生成斐波那契数列
* 数列公式：F(0)=1, F(1)=1, F(n)=F(n-1)+F(n-2)
*/
private static int[] generateFibonacci() {
int[] fib = new int[FIB_MAX];
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < FIB_MAX; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib;
}
// endregion
// region 测试用例
public static void main(String[] args) {
int[] uniformArr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; // 均匀分布数组
int[] randomArr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; // 随机分布数组
// 插值查找测试
System.out.println("插值查找结果:");
System.out.println("查找16的索引: " + interpolationSearch(uniformArr, 16)); // 输出7
System.out.println("查找0的索引: " + interpolationSearch(uniformArr, 0)); // 输出-1
// 斐波那契查找测试
System.out.println("\n斐波那契查找结果:");
System.out.println("查找13的索引: " + fibonacciSearch(randomArr, 13)); // 输出6
System.out.println("查找20的索引: " + fibonacciSearch(randomArr, 20)); // 输出-1
}
// endregion
}三、动态规划与贪心算法
- 动态规划基础
- 背包问题（0-1背包、完全背包）
import java.util.Arrays;
import java.util.Comparator;
/***
* 背包问题综合解决方案类
* 功能：支持0-1背包（动态规划）、完全背包（动态规划+贪心对比）
*/
public class KnapsackSolutions {
/***
* 0-1背包动态规划解法
* @param weights 物品重量数组
* @param values 物品价值数组
* @param capacity 背包容量
* @return 最大总价值
*/
public static int knapsack01DP(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1]; // dp[i][j]表示前i个物品容量j的最大价值[6](@ref)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (j < weights[i-1]) {
dp[i][j] = dp[i-1][j]; // 当前物品无法放入
} else {
// 状态转移方程：max(不放入，放入)
dp[i][j] = Math.max(
dp[i-1][j],
dp[i-1][j - weights[i-1]] + values[i-1]
);
}
}
}
return dp[n][capacity];
}
/***
* 完全背包动态规划解法（优化空间版）
* @param weights 物品重量数组
* @param values 物品价值数组
* @param capacity 背包容量
* @return 最大总价值
*/
public static int knapsackUnboundedDP(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1]; // 一维数组优化[9](@ref)
for (int i = 0; i < weights.length; i++) {
for (int j = weights[i]; j <= capacity; j++) { // 正序循环实现物品复用[10](@ref)
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
/***
* 贪心算法实现（仅适用于分数背包，此处作为对比）
* @param weights 物品重量数组
* @param values 物品价值数组
* @param capacity 背包容量
* @return 近似最大价值
*/
public static double greedyApproach(int[] weights, int[] values, int capacity) {
Item[] items = new Item[weights.length];
for (int i = 0; i < weights.length; i++) {
items[i] = new Item(weights[i], values[i]);
}
// 按单位价值降序排序[3](@ref)
Arrays.sort(items, Comparator.comparingDouble(Item::getValuePerWeight).reversed());
double totalValue = 0;
int remaining = capacity;
for (Item item : items) {
if (remaining >= item.weight) {
totalValue += item.value;
remaining -= item.weight;
} else {
// 贪心算法完整实现需处理分数，此处仅作对比
break;
}
}
return totalValue;
}
// 辅助类：物品信息
static class Item {
int weight;
int value;
double valuePerWeight;
public Item(int w, int v) {
weight = w;
value = v;
valuePerWeight = (double)v / w;
}
public double getValuePerWeight() {
return valuePerWeight;
}
}
/***
* 测试方法
*/
public static void main(String[] args) {
// 0-1背包测试数据
int[] weights01 = {2, 3, 4, 5};
int[] values01 = {3, 4, 5, 6};
int capacity01 = 8;
// 完全背包测试数据
int[] weightsUnbounded = {3, 4, 2};
int[] valuesUnbounded = {4, 5, 3};
int capacityUnbounded = 7;
System.out.println("=== 0-1背包测试 ===");
System.out.println("动态规划结果：" +
knapsack01DP(weights01, values01, capacity01)); // 应输出10
System.out.println("\n=== 完全背包测试 ===");
System.out.println("动态规划结果：" +
knapsackUnboundedDP(weightsUnbounded, valuesUnbounded, capacityUnbounded)); // 应输出11
System.out.println("贪心算法结果：" +
greedyApproach(weightsUnbounded, valuesUnbounded, capacityUnbounded)); // 应输出9
}
}- 最长公共子序列（LCS）
/***
* 最长公共子序列(LCS)动态规划实现
*/
public class LongestCommonSubsequence {
private int[][] dp; // 动态规划表
private char[] X; // 序列X字符数组
private char[] Y; // 序列Y字符数组
/***
* 构造函数初始化输入序列
* @param str1 序列X
* @param str2 序列Y
*/
public LongestCommonSubsequence(String str1, String str2) {
this.X = (" " + str1).toCharArray(); // 添加虚拟首字符便于索引计算[1](@ref)
this.Y = (" " + str2).toCharArray();
this.dp = new int[X.length][Y.length];
}
/***
* 构建动态规划表并计算LCS长度
* @return LCS长度
*/
public int computeLCS() {
// 初始化边界条件
for (int i = 0; i < X.length; i++) dp[i][0] = 0;
for (int j = 0; j < Y.length; j++) dp[0][j] = 0;
// 填充动态规划表
for (int i = 1; i < X.length; i++) {
for (int j = 1; j < Y.length; j++) {
if (X[i] == Y[j]) {
dp[i][j] = dp[i-1][j-1] + 1; // 字符匹配情况[3,5](@ref)
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // 字符不匹配情况[3](@ref)
}
}
}
return dp[X.length-1][Y.length-1];
}
/***
* 回溯获取具体LCS内容
* @return 最长公共子序列字符串
*/
public String getLCSString() {
StringBuilder lcs = new StringBuilder();
int i = X.length - 1, j = Y.length - 1;
while (i > 0 && j > 0) {
if (X[i] == Y[j]) { // 当前字符属于LCS[1](@ref)
lcs.append(X[i]);
i--;
j--;
} else if (dp[i-1][j] > dp[i][j-1]) { // 向上回溯[5](@ref)
i--;
} else { // 向左回溯[5](@ref)
j--;
}
}
return lcs.reverse().toString(); // 反转得到正确顺序
}
/***
* 测试方法
*/
public static void main(String[] args) {
String str1 = "ABCDBC";
String str2 = "ABCEAC";
LongestCommonSubsequence lcs = new LongestCommonSubsequence(str1, str2);
System.out.println("LCS长度: " + lcs.computeLCS());
System.out.println("LCS内容: " + lcs.getLCSString());
}
}- 最长递增子序列（LIS）
import java.util.Arrays;
/***
* 最长递增子序列(LIS)解决方案类
* 包含动态规划与二分优化两种实现方式
*/
public class LongestIncreasingSubsequence {
/***
* 动态规划解法 (时间复杂度O(n²))
* @param nums 输入序列
* @return LIS长度
*
* 算法思路：
* 1. 定义dp[i]表示以nums[i]结尾的LIS长度
* 2. 初始化每个元素的LIS长度为1（自身）
* 3. 双重循环遍历，若当前元素比之前元素大则更新dp值
* 4. 最终取dp数组最大值[3,5](@ref)
*/
public static int lisDP(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
Arrays.fill(dp, 1); // 每个元素自身构成长度为1的序列
int maxLen = 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);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
/***
* 贪心+二分优化解法 (时间复杂度O(n log n))
* @param nums 输入序列
* @return LIS长度
*
* 算法思路：
* 1. 维护tails数组记录各长度LIS的最小末尾值
* 2. 遍历时用二分查找确定插入位置
* 3. 若大于末尾则追加，否则替换更小的值
* 4. tails数组长度即为结果[5,10](@ref)
*/
public static int lisBinary(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] tails = new int[nums.length];
int size = 0;
for (int num : nums) {
// 二分查找插入位置
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num;
if (left == size) size++;
}
return size;
}
/***
* 测试方法
*/
public static void main(String[] args) {
// 测试案例1（典型情况）
int[] test1 = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("DP解法结果: " + lisDP(test1)); // 应输出4
System.out.println("二分解法结果: " + lisBinary(test1)); // 应输出4
// 测试案例2（全递减序列）
int[] test2 = {5,4,3,2,1};
System.out.println("\nDP解法结果: " + lisDP(test2)); // 应输出1
System.out.println("二分解法结果: " + lisBinary(test2)); // 应输出1
// 测试案例3（包含重复元素）
int[] test3 = {2,2,3,1,2,4,3};
System.out.println("\nDP解法结果: " + lisDP(test3)); // 应输出3
System.out.println("二分解法结果: " + lisBinary(test3)); // 应输出3
}
}- 矩阵链乘法
public class MatrixChainMultiplication {
// 动态规划计算矩阵链最小乘法次数
public static int matrixChainOrder(int[] p, int[][] s) {
int n = p.length - 1; // 矩阵数量
int[][] m = new int[n][n]; // 存储最小乘法次数
// 初始化对角线（单个矩阵不需要乘法）
for (int i = 0; i < n; i++) {
m[i][i] = 0;
}
// 自底向上计算所有子问题
for (int len = 2; len <= n; len++) { // 链的长度（从2个矩阵开始）
for (int i = 0; i < n - len + 1; i++) { // 子链起始位置
int j = i + len - 1; // 子链结束位置
m[i][j] = Integer.MAX_VALUE;
// 遍历所有可能的分割点
for (int k = i; k < j; k++) {
// 计算当前分割方式的代价
int cost = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
if (cost < m[i][j]) {
m[i][j] = cost;
s[i][j] = k; // 记录最优分割点
}
}
}
}
return m[0][n-1]; // 返回总最小代价
}
// 递归构造最优括号化方案
private static String buildOptimalParenthesis(int[][] s, int i, int j) {
if (i == j) {
return "A" + (i+1); // 单个矩阵直接返回编号
}
return "(" + buildOptimalParenthesis(s, i, s[i][j])
+ buildOptimalParenthesis(s, s[i][j]+1, j) + ")";
}
public static void main(String[] args) {
// 测试案例：矩阵维度数组（3个矩阵：10x30, 30x5, 5x60）
int[] p = {10, 30, 5, 60};
int n = p.length - 1;
int[][] s = new int[n][n]; // 分割点记录数组
// 计算最小乘法次数
int minCost = matrixChainOrder(p, s);
System.out.println("最小乘法次数: " + minCost);
// 构造最优括号化方案
String optimal = buildOptimalParenthesis(s, 0, n-1);
System.out.println("最优括号化方案: " + optimal);
}
}- 贪心算法应用
- 活动选择问题
/***
* 贪心算法实现活动选择问题
* 策略：优先选择结束时间最早的活动（可最大化后续活动选择空间）
*/
public class ActivitySelector {
// 定义活动实体类
static class Activity implements Comparable<Activity> {
int id; // 活动编号
int startTime; // 开始时间
int endTime; // 结束时间
public Activity(int id, int startTime, int endTime) {
this.id = id;
this.startTime = startTime;
this.endTime = endTime;
}
// 按结束时间升序排序
@Override
public int compareTo(Activity other) {
return this.endTime - other.endTime;
}
}
/***
* 贪心算法实现活动选择
* @param activities 活动数组
*/
public static void selectActivities(Activity[] activities) {
// 1. 按结束时间排序（贪心策略核心）
Arrays.sort(activities);
// 2. 初始化结果集
System.out.println("已选择活动列表：");
System.out.println("活动" + activities[0].id + " ("
+ activities[0].startTime + "-" + activities[0].endTime + ")");
// 3. 记录上一个选中活动的结束时间
int lastEnd = activities[0].endTime;
// 4. 遍历选择后续活动
for (int i = 1; i < activities.length; i++) {
// 当前活动开始时间 >= 上一个活动结束时间时选择
if (activities[i].startTime >= lastEnd) {
System.out.println("活动" + activities[i].id + " ("
+ activities[i].startTime + "-" + activities[i].endTime + ")");
lastEnd = activities[i].endTime;
}
}
}
/***
* 测试主方法
*/
public static void main(String[] args) {
// 测试数据（活动编号，开始时间，结束时间）
Activity[] activities = {
new Activity(1, 1, 4),
new Activity(2, 3, 5),
new Activity(3, 0, 6),
new Activity(4, 5, 7),
new Activity(5, 3, 9),
new Activity(6, 5, 9),
new Activity(7, 6, 10),
new Activity(8, 8, 11),
new Activity(9, 8, 12),
new Activity(10, 2, 13),
new Activity(11, 12, 14)
};
// 执行活动选择算法
selectActivities(activities);
}
}- 霍夫曼编码
import java.util.*;
import java.util.*;
public class HuffmanCoding {
// 霍夫曼节点定义（保持不变）
private static class HuffmanNode implements Comparable<HuffmanNode> {
Character character;
int frequency;
HuffmanNode left, right;
public HuffmanNode(Character character, int frequency) {
this.character = character;
this.frequency = frequency;
}
public HuffmanNode(HuffmanNode left, HuffmanNode right) {
this.frequency = left.frequency + right.frequency;
this.left = left;
this.right = right;
}
@Override
public int compareTo(HuffmanNode other) {
return this.frequency - other.frequency;
}
}
// 修改方法：返回包含根节点和编码表的对象
private static class HuffmanResult {
HuffmanNode root;
Map<Character, String> codes;
public HuffmanResult(HuffmanNode root, Map<Character, String> codes) {
this.root = root;
this.codes = codes;
}
}
// 重构方法：返回包含根节点和编码表的对象
private static HuffmanResult buildHuffmanTreeWithCodes(String input) {
Map<Character, Integer> freqMap = new HashMap<>();
for (char c : input.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
}
while (pq.size() > 1) {
HuffmanNode left = pq.poll();
HuffmanNode right = pq.poll();
pq.offer(new HuffmanNode(left, right));
}
HuffmanNode root = pq.poll();
Map<Character, String> codes = new HashMap<>();
buildCodes(root, new StringBuilder(), codes);
return new HuffmanResult(root, codes);
}
private static void buildCodes(HuffmanNode node, StringBuilder code, Map<Character, String> codes) {
if (node == null) return;
if (node.character != null) {
codes.put(node.character, code.toString());
return;
}
code.append('0');
buildCodes(node.left, code, codes);
code.deleteCharAt(code.length() - 1);
code.append('1');
buildCodes(node.right, code, codes);
code.deleteCharAt(code.length() - 1);
}
// 编码方法
public static String encode(String input, Map<Character, String> codes) {
StringBuilder sb = new StringBuilder();
for (char c : input.toCharArray()) {
sb.append(codes.get(c));
}
return sb.toString();
}
// 解码方法（使用正确的根节点）
public static String decode(String encoded, HuffmanNode root) {
StringBuilder result = new StringBuilder();
HuffmanNode current = root;
for (char bit : encoded.toCharArray()) {
current = (bit == '0') ? current.left : current.right;
if (current.character != null) {
result.append(current.character);
current = root; // 重置到根节点
}
}
return result.toString();
}
// 测试方法
public static void main(String[] args) {
String testStr = "i like like like java do you like a java";
// 获取包含根节点和编码表的结果对象
HuffmanResult result = buildHuffmanTreeWithCodes(testStr);
// 编码
String encoded = encode(testStr, result.codes);
System.out.println("Encoded: " + encoded);
// 解码（直接使用正确的根节点）
String decoded = decode(encoded, result.root);
System.out.println("Decoded: " + decoded);
}
}- 最小生成树（Kruskal算法的贪心策略）
import java.util.*;
/***
* Kruskal算法实现最小生成树（基于贪心策略）
*/
public class KruskalMST {
// 边类（内部类）
static class Edge implements Comparable<Edge> {
int src; // 起点
int dest; // 终点
int weight; // 权重
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return this.weight - other.weight; // 按权重升序排列（贪心策略核心）
}
}
// 并查集类（内部类）
static class UnionFind {
int[] parent;
int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i; // 初始时每个节点都是自己的父节点
rank[i] = 0; // 初始秩为0
}
}
// 带路径压缩的查找
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩优化
}
return parent[x];
}
// 按秩合并
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) { // 只有根不同时才需要合并
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++; // 秩增加
}
}
}
}
// Kruskal算法核心实现
public static List<Edge> kruskalMST(List<Edge> edges, int vertices) {
List<Edge> result = new ArrayList<>();
Collections.sort(edges); // 贪心策略：按边权重排序[1,6](@ref)
UnionFind uf = new UnionFind(vertices);
int edgeCount = 0;
for (Edge edge : edges) {
if (edgeCount == vertices - 1) break; // MST边数为顶点数-1[3](@ref)
int rootSrc = uf.find(edge.src);
int rootDest = uf.find(edge.dest);
if (rootSrc != rootDest) { // 检测环路[5,9](@ref)
result.add(edge);
uf.union(rootSrc, rootDest);
edgeCount++;
}
}
if (result.size() != vertices - 1) {
throw new RuntimeException("图不连通，无法生成完整MST");
}
return result;
}
// 测试主方法
public static void main(String[] args) {
/* 测试用例（来自典型示例）：
(0)----1---(1)
| \ / |
6 5 2 3
| \ / |
(2)--4-(3)--5
*/
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 1));
edges.add(new Edge(0, 2, 6));
edges.add(new Edge(0, 3, 5));
edges.add(new Edge(1, 3, 2));
edges.add(new Edge(1, 4, 3));
edges.add(new Edge(2, 3, 4));
edges.add(new Edge(3, 4, 5));
try {
List<Edge> mst = kruskalMST(edges, 5);
System.out.println("最小生成树边：");
int totalWeight = 0;
for (Edge edge : mst) {
System.out.printf("%d - %d : %d\n", edge.src, edge.dest, edge.weight);
totalWeight += edge.weight;
}
System.out.println("总权重：" + totalWeight);
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}四、高级算法与设计模式
- 分治算法
- 归并排序的实现
import java.util.Arrays;
/***
* 归并排序实现（分治算法经典案例）
* 时间复杂度：O(n log n)，空间复杂度：O(n)
*/
public class MergeSort {
/***
* 归并排序入口方法
* @param arr 待排序数组
*/
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) return;
int[] temp = new int[arr.length]; // 预分配临时数组避免重复创建[7](@ref)
mergeSort(arr, 0, arr.length - 1, temp);
}
/***
* 递归拆分方法（分治阶段）
* @param arr 原始数组
* @param left 左边界索引
* @param right 右边界索引
* @param temp 临时数组
*/
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left >= right) return; // 终止条件：子数组长度为1
int mid = left + (right - left) / 2; // 防止整数溢出[7](@ref)
// 递归拆分左半部[3,4](@ref)
mergeSort(arr, left, mid, temp);
// 递归拆分右半部
mergeSort(arr, mid + 1, right, temp);
// 合并有序子序列
merge(arr, left, mid, right, temp);
}
/***
* 合并两个有序子数组（治的阶段）
* @param arr 原始数组
* @param left 左边界
* @param mid 中间分割点
* @param right 右边界
* @param temp 临时存储数组
*/
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 复制数据到临时数组[2,7](@ref)
System.arraycopy(arr, left, temp, left, right - left + 1);
int i = left; // 左子数组起始指针
int j = mid + 1; // 右子数组起始指针
int k = left; // 合并数组的写入指针
// 双指针合并有序序列[3,6](@ref)
while (i <= mid && j <= right) {
arr[k++] = (temp[i] <= temp[j]) ? temp[i++] : temp[j++];
}
// 处理剩余元素（只会执行其中一个循环）[4](@ref)
while (i <= mid) arr[k++] = temp[i++];
while (j <= right) arr[k++] = temp[j++];
}
/***
* 测试方法
*/
public static void main(String[] args) {
int[] data = {8, 4, 5, 7, 1, 3, 6, 2};
System.out.println("原始数组：" + Arrays.toString(data));
sort(data);
System.out.println("排序结果：" + Arrays.toString(data));
/* 测试用例验证：
原始数组：[8, 4, 5, 7, 1, 3, 6, 2]
排序结果应为：[1, 2, 3, 4, 5, 6, 7, 8]
*/
}
}- 快速幂算法
public class ExponentiationTest {
// region 核心计算方法
/***
* 处理大整数幂运算（支持正/负指数）
* @param base 基数（支持大整数）
* @param exponent 指数
* @return 计算结果
*/
public static BigInteger calculatePower(BigInteger base, int exponent) {
if (exponent == 0) return BigInteger.ONE; // 零指数处理[1,4](@ref)
if (exponent < 0) { // 负指数转换[4](@ref)
return BigInteger.ONE.divide(
base.pow(Math.abs(exponent))
);
}
return base.pow(exponent);
}
/***
* 处理小数幂运算（支持高精度）
* @param base 基数（支持字符串构造精确值）
* @param exponent 指数
* @return 计算结果（四舍五入保留8位小数）
*/
public static BigDecimal decimalPower(String base, int exponent) {
BigDecimal num = new BigDecimal(base);
if (exponent == 0) return BigDecimal.ONE;
if (exponent < 0) { // 负指数处理[4,7](@ref)
return BigDecimal.ONE.divide(
num.pow(Math.abs(exponent)),
8, RoundingMode.HALF_UP
);
}
return num.pow(exponent);
}
// endregion
// region 测试方法优化
/***
* 通用测试方法（支持大整数验证）
* @param base 基数
* @param exponent 指数
* @param expected 预期结果（字符串形式）
*/
private static void testCase(String base, int exponent, String expected) {
try {
BigInteger result = calculatePower(new BigInteger(base), exponent);
boolean valid = result.toString().equals(expected);
System.out.printf("测试 %s^%d | 结果: %s | %s%n",
base, exponent, result,
valid ? "√ 通过" : "× 失败（预期：" + expected + "）"
);
} catch (ArithmeticException e) {
System.out.println("检测到除零错误: " + e.getMessage());
}
}
/***
* 小数测试专用方法
* @param base 基数（字符串形式）
* @param exponent 指数
* @param expected 预期值（字符串形式）
*/
private static void testDecimalCase(String base, int exponent, String expected) {
BigDecimal result = decimalPower(base, exponent);
BigDecimal expectedValue = new BigDecimal(expected);
boolean valid = result.compareTo(expectedValue) == 0;
System.out.printf("测试 %s^%d | 结果: %s | %s%n",
base, exponent, result.toPlainString(),
valid ? "√ 通过" : "× 失败（预期：" + expected + "）"
);
}
// endregion
// region 主测试方法
public static void main(String[] args) {
// 大整数测试（通过字符串避免字面量溢出）
System.out.println("--- 大整数测试 ---");
testCase("2", 10, "1024");
testCase("10", 20, "100000000000000000000"); // 原字面量改为字符串构造
// 负指数测试（需要转小数验证）
System.out.println("\n--- 负指数测试 ---");
testDecimalCase("3", -2, "0.11111111"); // 1/9≈0.11111111[3,7](@ref)
testDecimalCase("2", -3, "0.125");
// 零指数测试
System.out.println("\n--- 零指数测试 ---");
testCase("5", 0, "1");
testDecimalCase("0.5", 0, "1");
// 边界测试（超过Long.MAX_VALUE）
System.out.println("\n--- 超长数测试 ---");
testCase("9223372036854775807", 2, "85070591730234615847396907784232501249"); // (Long.MAX_VALUE)^2
}
}
- 最近点对问题
/**
* 〈简述〉<br>
* 〈〉
*
* @author chenx
* @create 08/04/2025
* @since 1.0.0
*/
import java.util.*;
/***
* 最近点对问题的分治算法实现
* 时间复杂度：O(n logn) 空间复杂度：O(n)
*/
public class ClosestPair {
// 内部类表示二维点
static class Point {
final double x;
final double y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
}
/***
* 分治法主函数
* @param points 点集合
* @return 最近点对的距离
*/
public static double closestPair(Point[] points) {
// 预处理：按x坐标排序[1,6](@ref)
Point[] px = Arrays.copyOf(points, points.length);
Arrays.sort(px, Comparator.comparingDouble(p -> p.x));
// 按y坐标预排序[3,8](@ref)
Point[] py = Arrays.copyOf(points, points.length);
Arrays.sort(py, Comparator.comparingDouble(p -> p.y));
return closestUtil(px, py, 0, px.length-1);
}
/***
* 递归核心算法[2,7](@ref)
* @param px x排序后的数组
* @param py y排序后的数组
* @param low 起始索引
* @param high 结束索引
*/
private static double closestUtil(Point[] px, Point[] py, int low, int high) {
// 基本情况：点数<=3时使用暴力法[2,8](@ref)
if (high - low <= 2) {
return bruteForce(Arrays.copyOfRange(px, low, high+1));
}
int mid = (low + high) / 2;
Point midPoint = px[mid];
// 递归处理左右子集[1,6](@ref)
double dl = closestUtil(px, py, low, mid);
double dr = closestUtil(px, py, mid+1, high);
double d = Math.min(dl, dr);
// 收集距离中线d范围内的点[3,7](@ref)
List<Point> strip = new ArrayList<>();
for (Point p : py) {
if (Math.abs(p.x - midPoint.x) < d) {
strip.add(p);
}
}
// 检查带状区域内的最近点对[8,6](@ref)
return Math.min(d, stripClosest(strip, d));
}
/***
* 处理带状区域内的点对比较
* @param strip 候选点集合
* @param d 当前最小距离
* @return 更新后的最小距离
*/
private static double stripClosest(List<Point> strip, double d) {
double min = d;
// 每个点最多比较后续6个点[3,8](@ref)
for (int i=0; i<strip.size(); i++) {
for (int j=i+1; j<Math.min(i+6, strip.size()); j++) {
double dist = distance(strip.get(i), strip.get(j));
if (dist < min) {
min = dist;
}
}
}
return min;
}
/***
* 暴力法计算最近距离（用于小规模数据集）
*/
private static double bruteForce(Point[] points) {
double min = Double.MAX_VALUE;
for (int i=0; i<points.length; i++) {
for (int j=i+1; j<points.length; j++) {
double dist = distance(points[i], points[j]);
if (dist < min) {
min = dist;
}
}
}
return min;
}
/***
* 计算两点间欧氏距离[2,7](@ref)
*/
private static double distance(Point a, Point b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return Math.sqrt(dx*dx + dy*dy);
}
/***
* 测试方法
*/
public static void main(String[] args) {
// 测试用例（来自文献示例）[6,8](@ref)
Point[] points = {
new Point(2, 3), new Point(12, 30),
new Point(40, 50), new Point(5, 1),
new Point(12, 10), new Point(3, 4)
};
System.out.println("最近点对距离：" + closestPair(points));
}
}- 回溯算法
- 八皇后问题
import java.util.Arrays;
/***
* 八皇后问题回溯算法实现
* 时间复杂度：O(n!) 空间复杂度：O(n)
*/
public class EightQueens {
private static final int N = 8; // 皇后数量
private static int[] queens = new int[N]; // 皇后位置数组（索引为行号，值为列号）
private static int solutionCount = 0; // 解法计数器
/***
* 主回溯方法
* @param row 当前处理的行号
*/
private static void placeQueen(int row) {
if (row == N) { // 终止条件：所有皇后已放置
printSolution();
solutionCount++;
return;
}
// 遍历当前行的所有列
for (int col = 0; col < N; col++) {
if (isSafe(row, col)) { // 检查是否安全
queens[row] = col; // 放置皇后
placeQueen(row + 1); // 递归处理下一行
queens[row] = -1; // 回溯（实际可省略，新值会覆盖旧值）
}
}
}
/***
* 安全性检查（列和对角线冲突检测）
* @param row 待检查行
* @param col 待检查列
*/
private static boolean isSafe(int row, int col) {
// 检查与之前所有皇后的位置关系
for (int i = 0; i < row; i++) {
// 列冲突或对角线冲突检测（核心算法）
if (queens[i] == col ||
Math.abs(row - i) == Math.abs(col - queens[i])) {
return false;
}
}
return true;
}
/***
* 打印解法（网页7的优化打印方式）
*/
private static void printSolution() {
if (solutionCount < 3) { // 仅打印前3种解法示例
System.out.println("解法 " + (solutionCount+1) + ":");
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
System.out.print(queens[row] == col ? "Q " : "* ");
}
System.out.println();
}
System.out.println();
}
}
/***
* 测试主方法（网页2和网页7的测试逻辑结合）
*/
public static void main(String[] args) {
Arrays.fill(queens, -1); // 初始化数组（可省略）
placeQueen(0); // 从第0行开始回溯
System.out.println("八皇后问题共有 " + solutionCount + " 种解法");
System.out.println("[网页2][网页7]验证结果符合经典92解");
}
}- 数独求解
/***
* 数独求解器（回溯算法实现）
* 时间复杂度：O(9^(n*n)) 空间复杂度：O(n*n)
*/
public class SudokuSolver {
private static final int SIZE = 9; // 数独尺寸
private static final int BOX_SIZE = 3; // 子网格尺寸
/***
* 主求解方法（入口）
* @param board 数独二维数组（0表示空格）
* @return 是否找到解
*/
public static boolean solve(int[][] board) {
for (int row = 0; row < SIZE; row++) {
for (int col = 0; col < SIZE; col++) {
if (board[row][col] == 0) { // 发现空格
for (int num = 1; num <= SIZE; num++) { // 尝试1-9
if (isValid(board, row, col, num)) {
board[row][col] = num; // 临时填充
if (solve(board)) { // 递归求解
return true; // 找到解立即返回[7](@ref)
}
board[row][col] = 0; // 回溯[2,4](@ref)
}
}
return false; // 当前空格无解，触发回溯[3](@ref)
}
}
}
return true; // 所有单元格已填满[3](@ref)
}
/***
* 验证数字合法性（行、列、子网格）
* @param num 待验证数字
*/
private static boolean isValid(int[][] board, int row, int col, int num) {
// 行检查（横向遍历）[2](@ref)
for (int c = 0; c < SIZE; c++) {
if (board[row][c] == num) return false;
}
// 列检查（纵向遍历）[2](@ref)
for (int r = 0; r < SIZE; r++) {
if (board[r][col] == num) return false;
}
// 3x3子网格检查[3,7](@ref)
int boxRow = row - row % BOX_SIZE; // 子网格起始行
int boxCol = col - col % BOX_SIZE; // 子网格起始列
for (int r = boxRow; r < boxRow + BOX_SIZE; r++) {
for (int c = boxCol; c < boxCol + BOX_SIZE; c++) {
if (board[r][c] == num) return false;
}
}
return true; // 通过所有检查
}
/***
* 测试主方法（包含经典数独案例）
*/
public static void main(String[] args) {
// 初始化数独问题（0表示空格）[3](@ref)
int[][] puzzle = {
{8,0,0, 0,0,0, 0,0,0},
{0,0,3, 6,0,0, 0,0,0},
{0,7,0, 0,9,0, 2,0,0},
{0,5,0, 0,0,7, 0,0,0},
{0,0,0, 0,4,5, 7,0,0},
{0,0,0, 1,0,0, 0,3,0},
{0,0,1, 0,0,0, 0,6,8},
{0,0,8, 5,0,0, 0,1,0},
{0,9,0, 0,0,0, 4,0,0}
};
System.out.println("原始数独:");
printBoard(puzzle);
long start = System.currentTimeMillis();
boolean solved = solve(puzzle);
long duration = System.currentTimeMillis() - start;
if (solved) {
System.out.println("\n求解结果（耗时 " + duration + "ms）:");
printBoard(puzzle);
} else {
System.out.println("无解");
}
}
/***
* 打印数独棋盘（带网格线）
*/
private static void printBoard(int[][] board) {
for (int i = 0; i < SIZE; i++) {
if (i % BOX_SIZE == 0 && i != 0) {
System.out.println("------+-------+------");
}
for (int j = 0; j < SIZE; j++) {
if (j % BOX_SIZE == 0 && j != 0) {
System.out.print("| ");
}
System.out.print(board[i][j] == 0 ? "." : board[i][j]);
System.out.print(" ");
}
System.out.println();
}
}
}- 组合与排列问题
import java.util.ArrayList;
import java.util.List;
/***
* 回溯算法解决组合与排列问题
* 包含：
* 1. 组合问题：从n个数中选取k个数的所有组合
* 2. 排列问题：给定数组的全排列
*/
public class BacktrackingSolutions {
// ================== 组合问题解决方案 ==================
/***
* 组合问题主方法
* @param n 数字范围[1, n]
* @param k 选取元素个数
* @return 所有可能的k个数组合
*/
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> results = new ArrayList<>();
backtrackCombine(n, k, 1, new ArrayList<>(), results);
return results;
}
/***
* 组合回溯核心算法
* @param start 起始索引（避免重复）
* @param current 当前路径
* @param results 结果集合
*/
private void backtrackCombine(int n, int k, int start,
List<Integer> current,
List<List<Integer>> results) {
// 终止条件：当前组合长度达到k
if (current.size() == k) {
results.add(new ArrayList<>(current)); // 复制当前路径
return;
}
// 遍历选择列表（优化剪枝：n - (k - current.size()) + 1）
for (int i = start; i <= n - (k - current.size()) + 1; i++) {
current.add(i); // 做出选择
backtrackCombine(n, k, i + 1, current, results); // 递归
current.remove(current.size() - 1); // 撤销选择
}
}
// ================== 排列问题解决方案 ==================
/***
* 排列问题主方法
* @param nums 输入数组
* @return 所有可能的全排列
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
backtrackPermute(nums, new ArrayList<>(), results);
return results;
}
/***
* 排列回溯核心算法
* @param current 当前路径
* @param results 结果集合
*/
private void backtrackPermute(int[] nums,
List<Integer> current,
List<List<Integer>> results) {
// 终止条件：路径包含所有元素
if (current.size() == nums.length) {
results.add(new ArrayList<>(current)); // 保存结果
return;
}
// 遍历所有可能选择
for (int num : nums) {
if (current.contains(num)) continue; // 剪枝：跳过已选元素
current.add(num); // 做出选择
backtrackPermute(nums, current, results); // 递归
current.remove(current.size() - 1); // 撤销选择
}
}
// ================== 测试方法 ==================
public static void main(String[] args) {
BacktrackingSolutions solver = new BacktrackingSolutions();
// 测试组合问题（n=4, k=2）
System.out.println("组合结果（n=4, k=2）：");
solver.combine(4, 2).forEach(System.out::println);
// 测试排列问题（数组[1,2,3]）
System.out.println("\n排列结果（[1,2,3]）：");
solver.permute(new int[]{1, 2, 3}).forEach(System.out::println);
}
}- 位运算与数学算法
- 位操作技巧（如判断奇偶、交换数值）
import java.util.BitSet;
/***
* 位操作工具类 - 集成常用位操作技巧与数学算法
* 应用工厂方法模式封装不同位操作策略
* 包含：数值交换、奇偶判断、快速幂等经典算法
*/
public class BitwiseMagic {
// ================== 基础位操作 ==================
/***
* 无临时变量交换两个整数（异或法）[4,5](@ref)
* @param a 第一个数（将被交换为第二个数）
* @param b 第二个数（将被交换为第一个数）
*/
public static void swapNumbers(int[] nums) {
nums[0] ^= nums[1];
nums[1] ^= nums[0];
nums[0] ^= nums[1];
}
/***
* 判断奇偶（与操作法）[5,7](@ref)
* @param n 待检测数
* @return true表示奇数，false表示偶数
*/
public static boolean isOdd(int n) {
return (n & 1) == 1;
}
// ================== 数学算法 ==================
/***
* 快速幂算法（位运算优化）[6](@ref)
* @param base 基数
* @param exponent 指数
* @return 计算结果
*/
public static long fastPower(int base, int exponent) {
long result = 1;
long temp = base;
while (exponent > 0) {
if ((exponent & 1) == 1) {
result *= temp;
}
temp *= temp;
exponent >>= 1;
}
return result;
}
/***
* 计算汉明距离（异或+位计数）[6,7](@ref)
* @param x 第一个数
* @param y 第二个数
* @return 不同位的数量
*/
public static int hammingDistance(int x, int y) {
int xor = x ^ y;
int distance = 0;
while (xor != 0) {
xor &= (xor - 1); // Brian Kernighan算法[1](@ref)
distance++;
}
return distance;
}
// ================== 高级应用 ==================
/***
* 布隆过滤器实现（位集合应用）[6](@ref)
*/
private static class BloomFilter {
private final BitSet bitSet;
private final int size;
public BloomFilter(int size) {
this.size = size;
this.bitSet = new BitSet(size);
}
// 双重哈希函数设计
private int[] hashFunctions(String element) {
int h1 = element.hashCode() % size;
int h2 = (element.hashCode() * 31) % size;
return new int[]{Math.abs(h1), Math.abs(h2)};
}
public void add(String element) {
int[] hashes = hashFunctions(element);
for (int hash : hashes) {
bitSet.set(hash % size);
}
}
public boolean contains(String element) {
int[] hashes = hashFunctions(element);
for (int hash : hashes) {
if (!bitSet.get(hash % size)) return false;
}
return true;
}
}
// ================== 测试方法 ==================
public static void main(String[] args) {
// 数值交换测试
int[] nums = {3, 7};
System.out.println("交换前: a=" + nums[0] + ", b=" + nums[1]);
swapNumbers(nums);
System.out.println("交换后: a=" + nums[0] + ", b=" + nums[1]);
// 奇偶判断测试
System.out.println("\n247是奇数? " + isOdd(247));
// 快速幂测试
System.out.println("2^10 = " + fastPower(2, 10));
// 汉明距离测试
System.out.println("4与1的汉明距离: " + hammingDistance(4, 1));
// 布隆过滤器测试
BloomFilter filter = new BloomFilter(100);
filter.add("algorithm");
System.out.println("\n包含'algorithm'? " + filter.contains("algorithm"));
System.out.println("包含'bitwise'? " + filter.contains("bitwise"));
}
}- 素数筛法（埃拉托斯特尼筛法）
import java.util.Arrays;
/***
* 素数筛选器 - 实现埃拉托斯特尼筛法
* 包含：
* 1. 基本筛法实现
* 2. 空间优化版本（BitSet）
* 3. 性能测试方法
*/
public class PrimeSieve {
// ================== 基础筛法实现 ==================
/***
* 经典埃氏筛法实现
* @param n 筛选范围上限
* @return 小于等于n的素数数量
*/
public static int sieveOfEratosthenes(int n) {
if (n < 2) return 0;
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false; // 标记0和1为非素数[1](@ref)
// 核心筛法逻辑：i只需遍历到√n[6](@ref)
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
// 从i²开始标记，避免重复计算[4,6](@ref)
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
// 统计素数数量
int count = 0;
for (boolean prime : isPrime) {
if (prime) count++;
}
return count;
}
// ================== 空间优化版本 ==================
/***
* 使用位运算优化空间（BitSet实现）
* 空间效率提升8倍，适用于大范围筛选[5](@ref)
*/
public static int sieveWithBitSet(int n) {
if (n < 2) return 0;
java.util.BitSet primes = new java.util.BitSet(n + 1);
primes.set(2, n + 1); // 初始标记2-n为素数
for (int i = 2; i * i <= n; i = primes.nextSetBit(i + 1)) {
if (i == -1) break; // 遍历结束条件
for (int j = i * i; j <= n; j += i) {
primes.clear(j);
}
}
return primes.cardinality();
}
// ================== 测试方法 ==================
public static void main(String[] args) {
// 测试用例验证
int testNum = 30;
System.out.println("经典筛法结果（n=30）：");
printPrimes(testNum);
System.out.println("素数数量：" + sieveOfEratosthenes(testNum));
System.out.println("\n位运算优化结果（n=30）：");
System.out.println("素数数量：" + sieveWithBitSet(testNum));
// 性能对比测试
int largeNum = 100_000_000;
benchmark(largeNum);
}
// 辅助方法：打印指定范围内的素数
private static void printPrimes(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) sb.append(i).append(" ");
}
System.out.println(sb.toString().trim());
}
// 性能测试方法
private static void benchmark(int n) {
System.out.println("\n性能测试（n=" + n + "）:");
long start = System.currentTimeMillis();
int count1 = sieveOfEratosthenes(n);
long time1 = System.currentTimeMillis() - start;
System.out.printf("经典筛法: %dms → 找到%d个素数\n", time1, count1);
start = System.currentTimeMillis();
int count2 = sieveWithBitSet(n);
long time2 = System.currentTimeMillis() - start;
System.out.printf("位运算优化: %dms → 找到%d个素数\n", time2, count2);
}
}- 最大公约数（欧几里得算法）
import java.math.BigInteger;
import java.util.Arrays;
/***
* 最大公约数计算器 - 集成多种算法实现
* 应用策略模式封装不同算法逻辑
* 包含：经典欧几里得算法、二进制优化算法、JDK内置方法
*/
public class GCDCalculator {
// ================== 算法策略枚举 ==================
/***
* 算法策略类型（策略模式实现）
*/
public enum AlgorithmType {
CLASSIC, // 经典欧几里得算法
BINARY, // 二进制优化算法
BUILT_IN // JDK内置方法
}
// ================== 核心算法实现 ==================
/***
* 经典欧几里得算法（辗转相除法）
* 时间复杂度：O(log(min(a,b)))
* 空间复杂度：O(1)
*/
private static int gcdClassic(int a, int b) {
a = Math.abs(a); // 处理负数
b = Math.abs(b);
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
/***
* 二进制优化算法（Stein算法）
* 使用位运算替代除法操作，适合大数计算
* 优化点：
* 1. 消除除法运算
* 2. 移位操作加速
*/
private static int gcdBinary(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
// 计算公共因子2的幂
int shift;
for (shift = 0; ((a | b) & 1) == 0; ++shift) {
a >>= 1;
b >>= 1;
}
// 消除因子2后的奇数
while ((a & 1) == 0) a >>= 1;
do {
while ((b & 1) == 0) b >>= 1;
if (a > b) {
int temp = b;
b = a;
a = temp;
}
b -= a;
} while (b != 0);
return a << shift; // 恢复公共因子2的幂
}
/***
* 使用BigInteger内置方法
* 适合处理超大整数（超过Long范围）
*/
private static int gcdBuiltIn(int a, int b) {
return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue();
}
// ================== 策略调度方法 ==================
/***
* 根据策略类型选择算法
* @param type 算法策略枚举
* @return 最大公约数计算结果
*/
public static int calculate(int a, int b, AlgorithmType type) {
return switch (type) {
case CLASSIC -> gcdClassic(a, b);
case BINARY -> gcdBinary(a, b);
case BUILT_IN -> gcdBuiltIn(a, b);
};
}
/***
* 计算数组的最大公约数（先找极值再计算）
* 应用场景：蓝桥杯算法题（网页3案例）
*/
public static int arrayGCD(int[] nums, AlgorithmType type) {
if (nums == null || nums.length == 0) return 0;
// 找出数组极值
int min = Arrays.stream(nums).min().getAsInt();
int max = Arrays.stream(nums).max().getAsInt();
return calculate(min, max, type);
}
// ================== 性能测试方法 ==================
/***
* 算法性能对比测试
*/
private static void benchmark(int a, int b) {
long start = System.nanoTime();
calculate(a, b, AlgorithmType.CLASSIC);
long classicTime = System.nanoTime() - start;
start = System.nanoTime();
calculate(a, b, AlgorithmType.BINARY);
long binaryTime = System.nanoTime() - start;
start = System.nanoTime();
calculate(a, b, AlgorithmType.BUILT_IN);
long builtInTime = System.nanoTime() - start;
System.out.printf("性能对比（%d vs %d）:\n", a, b);
System.out.println("经典算法: " + classicTime + "ns");
System.out.println("二进制优化: " + binaryTime + "ns");
System.out.println("内置方法: " + builtInTime + "ns");
}
// ================== 测试方法 ==================
public static void main(String[] args) {
// 基础测试
System.out.println("56和98的最大公约数：");
System.out.println("经典算法 → " + calculate(56, 98, AlgorithmType.CLASSIC)); // 14
System.out.println("二进制优化 → " + calculate(56, 98, AlgorithmType.BINARY)); // 14
System.out.println("内置方法 → " + calculate(56, 98, AlgorithmType.BUILT_IN)); // 14
// 数组测试（网页2案例）
int[] nums = {42, 56, 14};
System.out.println("\n数组[42,56,14]的GCD：");
System.out.println(arrayGCD(nums, AlgorithmType.BINARY)); // 14
// 性能测试（大数对比）
benchmark(123456789, 987654321);
benchmark(1_000_000_007, 1_000_000_009);
}
}五、算法面试实战
- 《剑指Offer》经典题解
- 链表操作（反转链表、环形链表检测）
/**
* 链表操作示例：包含反转链表和环形链表检测功能
*/
public class LinkedListOperations {
// 定义链表节点类
static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
/**
* 反转链表（迭代实现）[1,2,3](@ref)
* @param head 链表头节点
* @return 反转后的链表头节点
*/
public static 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; // 最终prev指向新链表的头节点
}
/**
* 检测环形链表（快慢指针法）[9,10](@ref)
* @param head 链表头节点
* @return 是否存在环
*/
public static boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head; // 慢指针（每次移动1步）
ListNode fast = head.next; // 快指针（每次移动2步）
while (fast != null && fast.next != null) {
if (slow == fast) return true; // 相遇则存在环
slow = slow.next;
fast = fast.next.next;
}
return false;
}
/**
* 打印链表（用于测试验证）
*/
public static void printList(ListNode head) {
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + "->");
curr = curr.next;
}
System.out.println("null");
}
public static void main(String[] args) {
// 测试反转链表功能
System.out.println("===== 链表反转测试 =====");
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
System.out.print("原链表：");
printList(head);
ListNode reversedHead = reverseList(head);
System.out.print("反转后：");
printList(reversedHead);
// 测试环形链表检测功能
System.out.println("\n===== 环形链表检测测试 =====");
ListNode cycleHead = new ListNode(1);
cycleHead.next = new ListNode(2);
cycleHead.next.next = new ListNode(3);
cycleHead.next.next.next = cycleHead.next; // 构造环（3指向2）
System.out.println("是否存在环：" + hasCycle(cycleHead));
}
}- 树的相关问题（镜像二叉树、重建二叉树）
import java.util.HashMap;
import java.util.Map;
/***
* 二叉树操作类（包含镜像操作和重建功能）
*/
public class BinaryTreeOperations {
// 定义二叉树节点
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
//=============== 镜像二叉树 ===============//
/***
* 递归生成镜像二叉树（原地修改）
* 时间复杂度O(n)，空间复杂度O(n)（递归栈）
*/
public static void mirrorTree(TreeNode root) {
if (root == null) return;
// 交换左右子树
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 递归处理子树
mirrorTree(root.left);
mirrorTree(root.right);
}
//=============== 重建二叉树 ===============//
private static Map<Integer, Integer> inOrderMap = new HashMap<>();
/***
* 根据前序+中序遍历重建二叉树
* @param preOrder 前序遍历数组
* @param inOrder 中序遍历数组
* @return 重建后的二叉树根节点
*/
public static TreeNode buildTree(int[] preOrder, int[] inOrder) {
// 构建中序遍历的哈希映射（值 -> 索引）
for (int i = 0; i < inOrder.length; i++) {
inOrderMap.put(inOrder[i], i);
}
return build(preOrder, 0, preOrder.length-1, 0);
}
/***
* 递归构建子树
* @param pre 前序数组
* @param preStart 当前子树在前序数组的起始位置
* @param preEnd 当前子树在前序数组的结束位置
* @param inStart 当前子树在中序数组的起始位置
*/
private static TreeNode build(int[] pre, int preStart, int preEnd, int inStart) {
if (preStart > preEnd) return null;
// 前序第一个元素为根节点
TreeNode root = new TreeNode(pre[preStart]);
// 获取中序数组中根节点的索引
int rootIdx = inOrderMap.get(root.val);
// 计算左子树节点数量
int leftSize = rootIdx - inStart;
// 递归构建左右子树
root.left = build(pre, preStart+1, preStart+leftSize, inStart);
root.right = build(pre, preStart+leftSize+1, preEnd, rootIdx+1);
return root;
}
//=============== 辅助方法 ===============//
/***
* 前序遍历打印（用于验证结果）
*/
public static void preOrderPrint(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " ");
preOrderPrint(root.left);
preOrderPrint(root.right);
}
//=============== 测试代码 ===============//
public static void main(String[] args) {
// 测试重建二叉树
int[] pre = {1,2,4,7,3,5,6,8};
int[] in = {4,7,2,1,5,3,8,6};
TreeNode root = buildTree(pre, in);
System.out.println("原树前序遍历：");
preOrderPrint(root);
// 测试镜像操作
mirrorTree(root);
System.out.println("\n镜像后前序遍历：");
preOrderPrint(root);
}
}- 动态规划题目（剪绳子、股票买卖问题）
/***
* 动态规划经典问题解决方案合集
* 包含：剪绳子问题、股票买卖系列问题
*/
public class DynamicProgrammingSolutions {
//================= 剪绳子问题 =================//
/***
* 剪绳子-动态规划解法
* 时间复杂度 O(n²)，空间复杂度 O(n)
* @param n 绳子长度
* @return 最大乘积
*/
public static int cutRopeDP(int n) {
if (n < 2) return 0;
if (n == 2) return 1;
// dp[i]表示长度为i的绳子剪断后的最大乘积
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
// 两种选择：1.剪成j和i-j两段 2.j段保留，i-j段继续剪
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
/***
* 剪绳子-贪心解法（数学优化）
* 时间复杂度 O(1)，空间复杂度 O(1)
* 原理：当n≥5时，尽可能切出长度为3的段
*/
public static int cutRopeGreedy(int n) {
if (n < 2) return 0;
if (n == 2) return 1;
if (n == 3) return 2;
int timesOf3 = n / 3;
if (n - timesOf3 * 3 == 1) { // 剩余4时拆分成2+2
timesOf3--;
}
int timesOf2 = (n - timesOf3 * 3) / 2;
return (int)(Math.pow(3, timesOf3) * Math.pow(2, timesOf2));
}
//================= 股票买卖问题 =================//
/***
* 股票买卖问题I（一次交易）
* 时间复杂度 O(n)，空间复杂度 O(1)
* 核心思想：记录历史最低价，计算当前最大利润
*/
public static int maxProfitOneTransaction(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}
/***
* 股票买卖问题II（无限次交易-贪心）
* 时间复杂度 O(n)，空间复杂度 O(1)
* 策略：所有上升波段都进行交易
*/
public static int maxProfitMultiGreedy(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1]) {
profit += prices[i] - prices[i-1];
}
}
return profit;
}
/***
* 股票买卖问题III（最多两次交易）
* 时间复杂度 O(n)，空间复杂度 O(1)
* 状态机思想：维护四个状态变量
*/
public static int maxProfitTwoTransactions(int[] prices) {
int buy1 = Integer.MIN_VALUE, sell1 = 0;
int buy2 = Integer.MIN_VALUE, sell2 = 0;
for (int price : prices) {
buy1 = Math.max(buy1, -price); // 第一次买入最佳时机
sell1 = Math.max(sell1, buy1 + price); // 第一次卖出最佳时机
buy2 = Math.max(buy2, sell1 - price); // 第二次买入（用第一次的利润）
sell2 = Math.max(sell2, buy2 + price); // 第二次卖出
}
return sell2;
}
//================= 测试方法 =================//
public static void main(String[] args) {
System.out.println("===== 剪绳子测试 =====");
System.out.println("动态规划(8): " + cutRopeDP(8)); // 输出18
System.out.println("贪心算法(8): " + cutRopeGreedy(8)); // 输出18
System.out.println("\n===== 股票买卖测试 =====");
int[] prices = {3,3,5,0,0,3,1,4};
System.out.println("一次交易最大利润: " + maxProfitOneTransaction(prices)); // 5
System.out.println("无限次交易(贪心): " + maxProfitMultiGreedy(prices)); // 13
System.out.println("两次交易最大利润: " + maxProfitTwoTransactions(prices)); // 6
}
}- LeetCode高频题目
- 双指针技巧（两数之和、滑动窗口）
/***
* 双指针算法合集
* 包含：两数之和（有序数组）、滑动窗口（最小子数组/最长无重复子串）
*/
public class TwoPointerAlgorithms {
// ================= 两数之和（有序数组） =================
/***
* 在升序数组中寻找两数之和等于目标值
* 时间复杂度 O(n)，空间复杂度 O(1)
* @param numbers 升序数组
* @param target 目标值
* @return 两个数的索引（从1开始计数）
*/
public static int[] twoSumSorted(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}; // 题目要求索引从1开始
} else if (sum > target) {
right--; // 和太大，缩小右边界[3,6](@ref)
} else {
left++; // 和太小，扩大左边界
}
}
return new int[]{-1, -1}; // 未找到解
}
// ================= 滑动窗口算法 =================
/***
* 寻找长度最小的连续子数组（和≥target）
* 时间复杂度 O(n)，空间复杂度 O(1)
* @param target 目标和
* @param nums 输入数组
* @return 最小长度（若无解返回0）
*/
public static int minSubArrayLen(int target, int[] nums) {
int left = 0;
int minLen = Integer.MAX_VALUE;
int windowSum = 0;
for (int right = 0; right < nums.length; right++) {
windowSum += nums[right];
// 当窗口和满足条件时尝试缩小窗口
while (windowSum >= target) {
minLen = Math.min(minLen, right - left + 1);
windowSum -= nums[left++]; // 移动左指针缩小窗口[8,11](@ref)
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
/***
* 寻找最长无重复字符的子串长度
* 时间复杂度 O(n)，空间复杂度 O(字符集大小)
* @param s 输入字符串
* @return 最长子串长度
*/
public static int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int maxLen = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符已存在且位于窗口内，移动左指针
if (map.containsKey(c) && map.get(c) >= left) {
left = map.get(c) + 1; // 跳过重复字符[9,11](@ref)
}
map.put(c, right); // 更新字符最新位置
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// ================= 测试方法 =================
public static void main(String[] args) {
System.out.println("===== 两数之和测试 =====");
int[] nums = {2,7,11,15};
int[] result = twoSumSorted(nums, 9);
System.out.println("测试1（存在解）：" + Arrays.toString(result)); // [1,2]
int[] nums2 = {1,2,3,4};
System.out.println("测试2（无解）：" + Arrays.toString(twoSumSorted(nums2, 10))); // [-1,-1]
System.out.println("\n===== 滑动窗口测试 =====");
int[] arr = {2,3,1,2,4,3};
System.out.println("最小子数组长度：" + minSubArrayLen(7, arr)); // 2（[4,3]）
String s = "abcabcbb";
System.out.println("最长无重复子串：" + lengthOfLongestSubstring(s)); // 3（"abc"）
}
}- 深度优先搜索（岛屿数量、路径总和）
/***
* DFS算法解决岛屿数量与路径总和问题
*/
public class DfsSolutions {
//================= 岛屿数量问题 =================//
/***
* 计算二维网格中的岛屿数量（LeetCode 200）
* 时间复杂度 O(mn) 空间复杂度 O(mn)（递归栈深度）
*/
public static int numIslands(char[][] grid) {
if(grid == null || grid.length == 0) return 0;
int count = 0;
// 遍历每个网格单元
for(int i=0; i<grid.length; i++) {
for(int j=0; j<grid[0].length; j++) {
if(grid[i][j] == '1') {
dfsIsland(grid, i, j); // 发现新岛屿
count++; // 岛屿计数+1
}
}
}
return count;
}
/***
* DFS标记相连陆地（将访问过的'1'置为'0'）
* @param row 当前行索引
* @param col 当前列索引
*/
private static void dfsIsland(char[][] grid, int row, int col) {
// 边界检查与陆地判断
if(row <0 || col<0 || row>=grid.length || col>=grid[0].length
|| grid[row][col] == '0') return;
grid[row][col] = '0'; // 标记为已访问
// 四方向递归搜索
dfsIsland(grid, row-1, col); // 上
dfsIsland(grid, row+1, col); // 下
dfsIsland(grid, row, col-1); // 左
dfsIsland(grid, row, col+1); // 右
}
//================= 路径总和问题 =================//
// 定义二叉树节点结构
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
/***
* 判断是否存在根到叶子的路径和等于目标值（LeetCode 112）
* @param root 二叉树根节点
* @param sum 目标总和
*/
public static boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
// 到达叶子节点时判断剩余值
if(root.left == null && root.right == null) {
return sum == root.val;
}
// 递归左右子树（传递剩余值）
return hasPathSum(root.left, sum - root.val) ||
hasPathSum(root.right, sum - root.val);
}
//================= 测试方法 =================//
public static void main(String[] args) {
System.out.println("===== 岛屿数量测试 =====");
char[][] grid1 = {
{'1','1','1','1','0'},
{'1','1','0','1','0'},
{'1','1','0','0','0'},
{'0','0','0','0','0'}
};
System.out.println("测试1岛屿数：" + numIslands(grid1)); // 应输出1
char[][] grid2 = {
{'1','1','0','0','0'},
{'1','1','0','0','0'},
{'0','0','1','0','0'},
{'0','0','0','1','1'}
};
System.out.println("测试2岛屿数：" + numIslands(grid2)); // 应输出3
System.out.println("\n===== 路径总和测试 =====");
// 构建示例树：5 ->4->11->7,2
TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
System.out.println("存在路径22? " + hasPathSum(root, 22)); // 应输出true
System.out.println("存在路径20? " + hasPathSum(root, 20)); // 应输出false
}
}- 字符串处理（最长回文子串、KMP算法）
/***
* 字符串处理算法合集：包含最长回文子串（中心扩展法）和KMP字符串匹配算法
*/
public class StringAlgorithms {
//================= 最长回文子串 =================//
/***
* 中心扩展法寻找最长回文子串
* 时间复杂度O(n²)，空间复杂度O(1)
* @param s 输入字符串
* @return 最长回文子串
*/
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
// 处理奇数长度回文（中心为单个字符）
int len1 = expandAroundCenter(s, i, i);
// 处理偶数长度回文（中心为两个相同字符之间）
int len2 = expandAroundCenter(s, i, i + 1);
int maxLen = Math.max(len1, len2);
// 更新最大回文子串的起止位置[2,7](@ref)
if (maxLen > end - start) {
start = i - (maxLen - 1) / 2;
end = i + maxLen / 2;
}
}
return s.substring(start, end + 1);
}
/***
* 从指定中心向两侧扩展判断回文
* @param left 左扩展起始点
* @param right 右扩展起始点
* @return 当前中心的最长回文长度
*/
private static int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() &&
s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1; // 回文实际长度计算[7](@ref)
}
//================= KMP算法 =================//
/***
* KMP字符串匹配算法
* 时间复杂度O(n+m)，空间复杂度O(m)
* @param text 主文本
* @param pattern 模式串
* @return 匹配起始索引（未找到返回-1）
*/
public static int kmpSearch(String text, String pattern) {
int[] lps = computeLPSArray(pattern);
int i = 0, j = 0; // i-文本指针，j-模式串指针
while (i < text.length()) {
if (pattern.charAt(j) == text.charAt(i)) {
i++;
j++;
}
if (j == pattern.length()) {
return i - j; // 完全匹配成功[1,9](@ref)
} else if (i < text.length() &&
pattern.charAt(j) != text.charAt(i)) {
if (j != 0) j = lps[j - 1]; // 利用LPS数组跳过已匹配部分[5](@ref)
else i++;
}
}
return -1;
}
/***
* 构建最长前缀后缀数组（LPS数组）
* @param pattern 模式串
* @return LPS数组
*/
private static int[] computeLPSArray(String pattern) {
int[] lps = new int[pattern.length()];
int len = 0; // 当前最长前缀后缀长度
for (int i = 1; i < pattern.length();) {
if (pattern.charAt(i) == pattern.charAt(len)) {
lps[i++] = ++len;
} else {
if (len != 0) len = lps[len - 1]; // 回退处理[9](@ref)
else lps[i++] = 0;
}
}
return lps;
}
//================= 测试方法 =================//
public static void main(String[] args) {
// 测试最长回文子串
System.out.println("===== 最长回文子串测试 =====");
System.out.println("案例1: " + longestPalindrome("babad")); // 输出 bab 或 aba
System.out.println("案例2: " + longestPalindrome("cbbd")); // 输出 bb
// 测试KMP算法
System.out.println("\n===== KMP算法测试 =====");
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
int index = kmpSearch(text, pattern);
System.out.println("匹配位置: " + index); // 输出 10
}
}- 《程序员代码面试指南》进阶题
- 设计数据结构（LRU缓存、最小栈）
import java.util.*;
/**
* 数据结构实现类（包含LRU缓存和最小栈）
*/
public class DataStructureImplement {
//================= LRU缓存实现 =================//
/**
* LRU缓存结构（双向链表+哈希表）
* 时间复杂度：get/put操作均为O(1)
*/
static class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int _key, int _value) {
key = _key;
value = _value;
}
}
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
// 初始化虚拟头尾节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
/**
* 获取元素并更新到最新位置
*/
public int get(int key) {
if (!cache.containsKey(key)) return -1;
DLinkedNode node = cache.get(key);
moveToHead(node); // 移动到链表头部表示最近使用
return node.value;
}
/**
* 插入元素（包含新增和更新操作）
*/
public void put(int key, int value) {
if (cache.containsKey(key)) {
DLinkedNode node = cache.get(key);
node.value = value;
moveToHead(node);
} else {
if (cache.size() >= capacity) {
DLinkedNode removed = removeTail(); // 删除最久未使用
cache.remove(removed.key);
}
DLinkedNode newNode = new DLinkedNode(key, value);
cache.put(key, newNode);
addToHead(newNode);
}
}
// 将节点添加到链表头部
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
// 移动已有节点到头部
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
// 删除链表中的节点
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 移除尾部节点（最久未使用）
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
//================= 最小栈实现 =================//
/**
* 最小栈结构（双栈实现）
* 时间复杂度：所有操作O(1)
*/
static class MinStack {
private Deque<Integer> dataStack; // 主栈存储数据
private Deque<Integer> minStack; // 辅助栈存储最小值
public MinStack() {
dataStack = new LinkedList<>();
minStack = new LinkedList<>();
minStack.push(Integer.MAX_VALUE); // 初始化哨兵值
}
/**
* 压栈时同步更新最小值栈
*/
public void push(int val) {
dataStack.push(val);
minStack.push(Math.min(minStack.peek(), val));
}
/**
* 出栈时同步弹出最小值栈顶
*/
public void pop() {
dataStack.pop();
minStack.pop();
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
//================= 测试方法 =================//
public static void main(String[] args) {
System.out.println("===== LRU缓存测试 =====");
LRUCache lruCache = new LRUCache(2);
lruCache.put(1, 1); // 缓存 [1=1]
lruCache.put(2, 2); // 缓存 [1=1, 2=2]
System.out.println("get(1): " + lruCache.get(1)); // 返回 1
lruCache.put(3, 3); // 淘汰2，缓存 [1=1, 3=3]
System.out.println("get(2): " + lruCache.get(2)); // 返回 -1
System.out.println("get(3): " + lruCache.get(3)); // 返回 3
System.out.println("\n===== 最小栈测试 =====");
MinStack minStack = new MinStack();
minStack.push(-2); // 主栈:[-2] 最小栈:[-2]
minStack.push(0); // 主栈:[-2,0] 最小栈:[-2,-2]
minStack.push(-3); // 主栈:[-2,0,-3] 最小栈:[-2,-2,-3]
System.out.println("最小值: " + minStack.getMin()); // 返回-3
minStack.pop(); // 弹出-3，最小栈回退到-2
System.out.println("顶部元素: " + minStack.top()); // 返回0
System.out.println("当前最小值: " + minStack.getMin()); // 返回-2
}
}- 复杂场景下的算法优化（如数据流中位数）
import java.util.Collections;
import java.util.PriorityQueue;
/***
* 数据流中位数算法（双堆优化版）
* 时间复杂度：插入O(log n)，查询O(1)
*/
public class MedianFinder {
// 大顶堆存储较小的一半（堆顶是较小值的最大值）
private PriorityQueue<Integer> maxHeap;
// 小顶堆存储较大的一半（堆顶是较大值的最小值）
private PriorityQueue<Integer> minHeap;
public MedianFinder() {
maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 大顶堆构造
minHeap = new PriorityQueue<>(); // 默认小顶堆
}
/***
* 插入元素核心逻辑（自动平衡堆大小）
* @param num 新增元素
*/
public void addNum(int num) {
// 优先加入大顶堆（保证新元素能进入正确分区）
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.offer(num);
} else {
minHeap.offer(num);
}
// 平衡堆大小（关键操作）
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.offer(maxHeap.poll()); // 大顶堆超额则转移堆顶
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.offer(minHeap.poll()); // 小顶堆超额则转移堆顶
}
}
/***
* 获取当前中位数
* @return 中位数（double类型）
*/
public double findMedian() {
// 处理空数据流异常
if (maxHeap.isEmpty() && minHeap.isEmpty()) {
throw new IllegalStateException("No numbers available");
}
// 根据堆大小判断奇偶
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.0; // 偶数取平均
} else {
return maxHeap.peek(); // 奇数取大顶堆顶（因插入逻辑保证大顶堆可能多1）
}
}
//=============== 测试方法 ===============//
public static void main(String[] args) {
MedianFinder finder = new MedianFinder();
// 测试案例1：动态插入验证
int[] testData = {3, 1, 5, 4, 2, 6};
System.out.println("动态插入测试：");
for (int num : testData) {
finder.addNum(num);
System.out.printf("插入 %d 后中位数: %.1f%n", num, finder.findMedian());
}
// 测试案例2：完整数据流验证
finder = new MedianFinder();
int[] stream = {5, 3, 8, 2, 7, 4};
for (int num : stream) finder.addNum(num);
System.out.println("\n完整数据流中位数: " + finder.findMedian()); // 应输出4.5
}
}六、算法工具与资源
- Java算法库
java.util.Collections中的排序与查找工具
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* 演示Collections工具类的排序与查找操作
*/
public class CollectionsExample {
public static void main(String[] args) {
// 初始化测试数据
List<Integer> numbers = new ArrayList<>();
Collections.addAll(numbers, 5, 2, 8, 1, 9, 3, 7, 4, 6);
System.out.println("原始列表: " + numbers);
// -------------------- 排序操作 --------------------
// 1. 自然顺序排序（升序）
Collections.sort(numbers);
System.out.println("自然升序后: " + numbers); // [1,3](@ref)
// 2. 自定义比较器排序（降序）
Collections.sort(numbers, Collections.reverseOrder());
System.out.println("自定义降序后: " + numbers); // [1,5](@ref)
// 3. 随机打乱顺序
Collections.shuffle(numbers);
System.out.println("随机打乱后: " + numbers); // [1,3](@ref)
// -------------------- 查找操作 --------------------
// 重新排序以便二分查找
Collections.sort(numbers); // 先恢复升序
System.out.println("\n二分查找前需排序: " + numbers);
// 1. 二分查找元素
int target = 7;
int index = Collections.binarySearch(numbers, target); // [1,2](@ref)
if (index >= 0) {
System.out.println("元素 " + target + " 的索引: " + index);
} else {
System.out.println("元素 " + target + " 未找到");
}
// 2. 查找最大值/最小值
System.out.println("最大值: " + Collections.max(numbers)); // [1,3](@ref)
System.out.println("最小值: " + Collections.min(numbers));
// -------------------- 复杂对象排序示例 --------------------
List<String> words = new ArrayList<>();
Collections.addAll(words, "apple", "banana", "cherry", "date");
System.out.println("\n原始字符串列表: " + words);
// 按字符串长度降序排序（自定义比较器）
Collections.sort(words, new Comparator<String>() { // [2,5](@ref)
@Override
public int compare(String s1, String s2) {
return Integer.compare(s2.length(), s1.length());
}
});
System.out.println("按长度降序: " + words);
}
}PriorityQueue与TreeMap的实现原理
import java.util.*;
/**
* 演示 PriorityQueue（优先级队列）与 TreeMap（红黑树映射）的实现原理及对比
*/
public class DataStructureDemo {
public static void main(String[] args) {
testPriorityQueue();
testTreeMap();
}
/**
* 测试 PriorityQueue 实现原理（基于最小堆）
*/
private static void testPriorityQueue() {
// 1. 初始化优先级队列（默认最小堆）
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 2. 添加元素（模拟无序插入）
priorityQueue.offer(5);
priorityQueue.offer(2);
priorityQueue.offer(8);
priorityQueue.offer(1);
System.out.println("PriorityQueue 元素插入顺序: 5, 2, 8, 1");
System.out.println("按优先级取出元素（小顶堆）:");
// 3. 按优先级取出元素
while (!priorityQueue.isEmpty()) {
System.out.print(priorityQueue.poll() + " ");
}
System.out.println("\n");
}
/**
* 测试 TreeMap 实现原理（基于红黑树）
*/
private static void testTreeMap() {
// 1. 初始化 TreeMap（默认按键自然顺序排序）
TreeMap<String, Integer> treeMap = new TreeMap<>();
// 2. 添加键值对（模拟无序插入）
treeMap.put("D", 4);
treeMap.put("B", 2);
treeMap.put("A", 1);
treeMap.put("C", 3);
System.out.println("TreeMap 插入顺序: D(4), B(2), A(1), C(3)");
System.out.println("按键顺序遍历（红黑树中序遍历）:");
// 3. 遍历键值对（按键升序）
for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
System.out.println(entry.getKey() + " -> " + entry.getValue());
}
}
}- 学习资源推荐
- 书籍：《算法（第四版）》（Java实现）[经典必读]14
- 在线平台：LeetCode、牛客网（Java题解专区）
- 开源项目：CodingInterviews（《剑指Offer》Java实现）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
相关文章
暂无评论...
