1 介绍
1.1 概念
01.算法定义
a.什么是算法
算法是操作数据、解决程序问题的一组明确的、有限的、可执行的指令序列。
b.算法的五大特性
a.有穷性
算法必须在有限步骤内结束，不能无限循环。
b.确定性
算法的每一步都有明确的定义，不会产生二义性。
c.可行性
算法的每一步都必须是可执行的，能在有限时间内完成。
d.输入
算法有零个或多个输入数据。
e.输出
算法至少有一个或多个输出结果。
02.算法衡量标准
a.时间复杂度
a.定义
程序所消耗的时间，一个算法中的语句执行次数称为语句频度或时间频度。
用大O表示法描述算法执行时间随数据规模增长的变化趋势。
b.常见时间复杂度
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
c.Java实现示例
---
public class TimeComplexityDemo {
// O(1) - 常数时间：无论数据规模多大，执行时间固定
public int constant(int[] arr) {
return arr[0]; // 只执行一次访问操作
}
// 📊 执行示例：
// 输入：arr = [1, 2, 3, 4, 5]，长度n=5
// 操作次数：1次（固定）
// 输入：arr = [1...1000]，长度n=1000
// 操作次数：1次（固定）
// O(log n) - 对数时间：每次操作将问题规模减半
public int logarithmic(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) { // 每次循环将搜索范围减半
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// 📊 执行示例：
// 输入：arr = [1,2,3,4,5,6,7,8]，target=6，n=8
// 第1次：搜索范围[1,8]，mid=4，arr[4]=5 < 6，范围变为[5,8]
// 第2次：搜索范围[5,8]，mid=6，arr[6]=7 > 6，范围变为[5,6]
// 第3次：搜索范围[5,6]，mid=5，arr[5]=6，找到！
// 操作次数：3次 = log₂(8)
// O(n) - 线性时间：需要遍历所有元素一次
public int linear(int[] arr) {
int sum = 0;
for (int num : arr) { // 遍历n个元素
sum += num;
}
return sum;
}
// 📊 执行示例：
// 输入：arr = [1, 2, 3, 4, 5]，n=5
// 操作次数：5次（遍历5个元素）
// 输入：arr = [1...1000]，n=1000
// 操作次数：1000次（遍历1000个元素）
// O(n log n) - 线性对数时间：高效排序算法的时间复杂度
public void nLogN(int[] arr) {
mergeSort(arr, 0, arr.length - 1); // 归并排序
}
// 📊 执行示例：
// 输入：arr = [5,2,8,1,9]，n=5
// 分治层数：log₂(5) ≈ 3层
// 每层合并操作：n次
// 总操作次数：n * log n ≈ 5 * 3 = 15次
// O(n²) - 平方时间：双层循环遍历
public void quadratic(int[] arr) {
for (int i = 0; i < arr.length; i++) { // 外层循环n次
for (int j = 0; j < arr.length; j++) { // 内层循环n次
System.out.println(arr[i] + "," + arr[j]);
}
}
}
// 📊 执行示例：
// 输入：arr = [1, 2, 3]，n=3
// 外层循环3次，每次内层循环3次
// 总操作次数：3 * 3 = 9次 = n²
// 输入：arr = [1...100]，n=100
// 总操作次数：100 * 100 = 10000次 = n²
// O(2ⁿ) - 指数时间：递归求解所有子集
public int exponential(int n) {
if (n <= 1) return 1;
return exponential(n - 1) + exponential(n - 1); // 每次分裂成2个子问题
}
// 📊 执行示例：
// 输入：n=4
// 递归树深度：4层
// 每层节点数：1, 2, 4, 8
// 总操作次数：1+2+4+8 = 15次 ≈ 2⁴-1
}
---
d.Go实现示例
---
package main
// O(1) - 常数时间
func constant(arr []int) int {
return arr[0]
}
// O(log n) - 对数时间：二分查找
func logarithmic(arr []int, target int) int {
left, right := 0, len(arr)-1
for left <= right {
mid := left + (right-left)/2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
// O(n) - 线性时间
func linear(arr []int) int {
sum := 0
for _, num := range arr {
sum += num
}
return sum
}
// O(n²) - 平方时间
func quadratic(arr []int) {
n := len(arr)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
println(arr[i], arr[j])
}
}
}
// O(2ⁿ) - 指数时间
func exponential(n int) int {
if n <= 1 {
return 1
}
return exponential(n-1) + exponential(n-1)
}
---
b.空间复杂度
a.定义
程序所占用的内存空间，在规模为n的情况下额外消耗的存储空间。
不包括输入数据本身占用的空间，只计算算法执行过程中临时占用的空间。
b.常见空间复杂度
a.O(1) - 常数空间
只使用固定数量的额外变量，如原地排序算法。
b.O(log n) - 对数空间
递归调用栈的深度，如二分查找的递归实现。
c.O(n) - 线性空间
需要额外的数组或列表存储中间结果，如归并排序。
d.O(n²) - 平方空间
需要二维数组存储数据，如邻接矩阵表示图。
c.代码示例
---
// Java实现
public class SpaceComplexityDemo {
// O(1) - 常数空间：只使用固定变量
public void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 只使用一个临时变量temp
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 空间分析：只使用了n、i、j、temp四个变量，空间复杂度O(1)
// O(n) - 线性空间：需要额外数组
public void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1]; // 需要O(n)额外空间
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
// 空间分析：需要O(n)的temp数组 + O(log n)的递归栈 = O(n)
}
// Go实现
func bubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n; i++ {
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j] // Go的交换语法
}
}
}
}
// 空间复杂度：O(1)
---
c.平均时间复杂度
a.定义
考虑所有可能输入情况下的平均性能表现，更贴近实际使用场景。
b.计算方法
平均时间复杂度 = Σ(每种情况的概率 × 该情况的时间复杂度)
c.示例：快速排序
最好情况：O(n log n) - 每次分区都平分数组
最坏情况：O(n²) - 每次分区都极度不平衡
平均情况：O(n log n) - 大多数情况下性能良好
03.图解说明
📌 时间复杂度增长趋势可视化：
数据规模n与操作次数的关系（假设n=10）：
O(1) : ★ (1次)
O(log n) : ★★★ (3次)
O(n) : ★★★★★★★★★★ (10次)
O(n log n): ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ (30次)
O(n²) : ★★★★...★ (100次，太多无法显示)
O(2ⁿ) : ★★★★...★ (1024次，指数爆炸)
📌 递归调用栈的空间消耗（斐波那契数列）：
fib(4) 的递归树：
fib(4)
/ \
fib(3) fib(2)
/ \ / \
fib(2) fib(1) fib(1) fib(0)
/ \
fib(1) fib(0)
最大栈深度：4层
空间复杂度：O(n)
04.常见错误与陷阱
⚠️ 时间复杂度分析常见错误：
1. 忽略常数项
错误：认为O(2n)和O(n)不同
正确：O(2n) = O(n)，大O表示法忽略常数系数
2. 忽略低阶项
错误：认为O(n² + n)不能简化
正确：O(n² + n) = O(n²)，只保留最高阶项
3. 循环嵌套判断错误
错误：认为所有嵌套循环都是O(n²)
示例：
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) { // 内层循环次数递减
// ...
}
}
正确：总次数 = n + (n-1) + ... + 1 = n(n+1)/2 = O(n²)
⚠️ 空间复杂度分析常见错误：
1. 混淆输入空间和额外空间
错误：认为输入数组也算在空间复杂度内
正确：只计算算法额外使用的空间
2. 忽略递归栈空间
错误：认为递归算法空间复杂度为O(1)
正确：递归深度为n时，栈空间为O(n)
3. 原地算法判断错误
错误：认为使用了临时变量就不是原地算法
正确：只要额外空间是O(1)就是原地算法
05.实战应用
a.如何选择合适的算法
a.数据规模小（n < 100）
可以使用O(n²)的简单算法，如冒泡排序、选择排序。
b.数据规模中等（100 < n < 10000）
应使用O(n log n)的高效算法，如快速排序、归并排序。
c.数据规模大（n > 10000）
必须使用O(n)或O(log n)的算法，避免使用O(n²)及以上。
b.空间换时间的权衡
a.内存充足时
可以使用哈希表（O(n)空间）实现O(1)查找。
b.内存受限时
使用原地算法（O(1)空间），接受较高的时间复杂度。
1.2 线性结构
01.一维数组（Array）
a.定义与特点
a.内存连续分配
数组元素在内存中连续存储，通过下标从0开始进行访问。
b.长度固定
数组创建后长度固定，一般不可动态扩容（原生数组）。
c.随机访问
支持O(1)时间复杂度的随机访问，通过索引直接定位元素。
b.Java实现
---
// 原生数组
int[] arr = new int[5]; // 固定长度为5
arr[0] = 10; // O(1)访问
// 动态数组ArrayList（基于数组实现）
ArrayList<Integer> list = new ArrayList<>();
list.add(10); // 尾部添加O(1)
list.add(0, 5); // 头部添加O(n)，需要移动元素
list.get(2); // 随机访问O(1)
list.remove(0); // 删除O(n)，需要移动元素
// 📊 执行示例：
// ArrayList初始容量：10
// 添加第11个元素时：扩容为15（1.5倍）
// 扩容过程：创建新数组 -> 复制元素 -> 替换引用
---
c.Go实现
---
// 固定数组
var arr [5]int // 固定长度为5
arr[0] = 10 // O(1)访问
// 动态切片（类似ArrayList）
slice := make([]int, 0, 10) // 长度0，容量10
slice = append(slice, 10) // 尾部添加O(1)
slice = append([]int{5}, slice...) // 头部添加O(n)
val := slice[2] // 随机访问O(1)
slice = append(slice[:0], slice[1:]...) // 删除首元素O(n)
// 📊 执行示例：
// 切片初始容量：10
// 添加第11个元素时：扩容为20（2倍）
// 扩容过程：创建新数组 -> 复制元素 -> 替换引用
---
d.常见工具类对比
a.ArrayList vs Vector
ArrayList：非线程安全，性能高，适合单线程环境
Vector：线程安全（方法同步synchronized），性能较低
b.CopyOnWriteArrayList
写时复制策略，线程安全，读操作无锁，适合读多写少场景
写操作：复制整个数组 -> 修改副本 -> 替换引用
e.图解说明
📌 数组内存布局：
内存地址： 1000 1004 1008 1012 1016
数组元素： [10] [20] [30] [40] [50]
索引： 0 1 2 3 4
随机访问：arr[2] = 基地址 + 2 * 元素大小 = 1000 + 2*4 = 1008
📌 ArrayList扩容过程：
原数组（容量10，已满）：
[1][2][3][4][5][6][7][8][9][10]
添加第11个元素，触发扩容：
新数组（容量15）：
[1][2][3][4][5][6][7][8][9][10][11][ ][ ][ ][ ]
↑ 复制原数据 ↑新元素 ↑预留空间
02.栈（Stack）
a.定义与特点
a.LIFO原则
后进先出（Last In First Out），只允许在栈顶进行操作。
b.受限的线性表
只能在一端（栈顶）进行插入（push）和删除（pop）操作。
c.栈底不可操作
栈底元素固定，无法直接访问或删除。
b.Java实现
---
// 使用Stack类（基于Vector，线程安全但性能较低）
Stack<Integer> stack = new Stack<>();
stack.push(1); // 入栈：1
stack.push(2); // 入栈：2
stack.push(3); // 入栈：3
int top = stack.pop(); // 出栈：3，栈变为[1,2]
int peek = stack.peek(); // 查看栈顶：2，不出栈
// 📊 执行示例：
// 初始：[]
// push(1)：[1]
// push(2)：[1,2]
// push(3)：[1,2,3]
// pop()：返回3，栈变为[1,2]
// peek()：返回2，栈不变[1,2]
// 推荐使用Deque实现栈（性能更好）
Deque<Integer> stack2 = new ArrayDeque<>();
stack2.push(1); // 入栈
stack2.pop(); // 出栈
---
c.Go实现
---
// Go没有内置栈，使用切片实现
type Stack struct {
items []int
}
func (s *Stack) Push(val int) {
s.items = append(s.items, val) // 入栈O(1)
}
func (s *Stack) Pop() int {
if len(s.items) == 0 {
panic("stack is empty")
}
top := s.items[len(s.items)-1] // 获取栈顶
s.items = s.items[:len(s.items)-1] // 移除栈顶
return top
}
func (s *Stack) Peek() int {
if len(s.items) == 0 {
panic("stack is empty")
}
return s.items[len(s.items)-1] // 查看栈顶，不移除
}
// 使用示例
stack := &Stack{}
stack.Push(1)
stack.Push(2)
stack.Push(3)
val := stack.Pop() // 返回3
---
d.图解说明
📌 栈的操作过程：
初始状态：
栈顶 → [空]
push(1)：
栈顶 → [1]
push(2)：
栈顶 → [2]
[1]
push(3)：
栈顶 → [3]
[2]
[1]
pop()：返回3
栈顶 → [2]
[1]
e.应用场景
a.函数调用栈
程序运行时的函数调用和返回。
b.表达式求值
中缀表达式转后缀表达式，括号匹配。
c.浏览器历史
前进后退功能。
d.撤销操作
编辑器的undo功能。
03.链表（Linked List）
a.定义与特点
a.指针连接
通过节点的指针地址实现，节点包含数据域和指针域。
b.非连续内存
节点在内存中不连续存储，通过指针链接。
c.动态长度
长度可以动态变化，无需预分配空间。
d.顺序访问
必须从头节点开始遍历，不支持随机访问。
b.链表类型
a.单链表
每个节点只有一个next指针，指向下一个节点。
b.双向链表
每个节点有prev和next两个指针，可双向遍历。
c.循环链表
尾节点的next指向头节点，形成环。
c.Java实现
---
// 单链表节点定义
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
// 单链表基本操作
public class LinkedListDemo {
private ListNode head;
// 头部插入O(1)
public void addFirst(int val) {
ListNode node = new ListNode(val);
node.next = head;
head = node;
}
// 尾部插入O(n)
public void addLast(int val) {
ListNode node = new ListNode(val);
if (head == null) {
head = node;
return;
}
ListNode curr = head;
while (curr.next != null) { // 遍历到尾节点
curr = curr.next;
}
curr.next = node;
}
// 删除节点O(n)
public void remove(int val) {
if (head == null) return;
if (head.val == val) {
head = head.next;
return;
}
ListNode curr = head;
while (curr.next != null && curr.next.val != val) {
curr = curr.next;
}
if (curr.next != null) {
curr.next = curr.next.next;
}
}
}
// 使用LinkedList类
LinkedList<Integer> list = new LinkedList<>();
list.addFirst(1); // 头部插入O(1)
list.addLast(2); // 尾部插入O(1)，LinkedList维护了tail指针
list.remove(0); // 删除指定位置O(n)
---
d.Go实现
---
// 单链表节点定义
type ListNode struct {
Val int
Next *ListNode
}
// 单链表结构
type LinkedList struct {
head *ListNode
}
// 头部插入O(1)
func (l *LinkedList) AddFirst(val int) {
node := &ListNode{Val: val}
node.Next = l.head
l.head = node
}
// 尾部插入O(n)
func (l *LinkedList) AddLast(val int) {
node := &ListNode{Val: val}
if l.head == nil {
l.head = node
return
}
curr := l.head
for curr.Next != nil {
curr = curr.Next
}
curr.Next = node
}
// 删除节点O(n)
func (l *LinkedList) Remove(val int) {
if l.head == nil {
return
}
if l.head.Val == val {
l.head = l.head.Next
return
}
curr := l.head
for curr.Next != nil && curr.Next.Val != val {
curr = curr.Next
}
if curr.Next != nil {
curr.Next = curr.Next.Next
}
}
---
e.图解说明
📌 单链表结构：
head
↓
[1|·] → [2|·] → [3|·] → null
数据 指针
📌 头部插入过程（插入0）：
步骤1：创建新节点
[0|·]
步骤2：新节点指向原头节点
[0|·] → [1|·] → [2|·] → [3|·] → null
步骤3：更新head指针
head
↓
[0|·] → [1|·] → [2|·] → [3|·] → null
f.常见工具类
java.util.LinkedList：双向链表实现，维护head和tail指针
04.队列（Queue）
a.定义与特点
a.FIFO原则
先进先出（First In First Out），在队尾插入，在队头删除。
b.受限的线性表
只能在队尾入队（enqueue），在队头出队（dequeue）。
b.Java实现
---
// 使用LinkedList实现队列
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 入队：1
queue.offer(2); // 入队：2
queue.offer(3); // 入队：3
int front = queue.poll(); // 出队：1，队列变为[2,3]
int peek = queue.peek(); // 查看队头：2，不出队
// 📊 执行示例：
// 初始：[]
// offer(1)：[1]
// offer(2)：[1,2]
// offer(3)：[1,2,3]
// poll()：返回1，队列变为[2,3]
// peek()：返回2，队列不变[2,3]
---
c.Go实现
---
// 使用切片实现队列
type Queue struct {
items []int
}
func (q *Queue) Enqueue(val int) {
q.items = append(q.items, val) // 队尾入队O(1)
}
func (q *Queue) Dequeue() int {
if len(q.items) == 0 {
panic("queue is empty")
}
front := q.items[0] // 获取队头
q.items = q.items[1:] // 移除队头O(n)
return front
}
func (q *Queue) Peek() int {
if len(q.items) == 0 {
panic("queue is empty")
}
return q.items[0] // 查看队头，不移除
}
---
d.图解说明
📌 队列的操作过程：
初始状态：
队头 → [空] ← 队尾
enqueue(1)：
队头 → [1] ← 队尾
enqueue(2)：
队头 → [1][2] ← 队尾
enqueue(3)：
队头 → [1][2][3] ← 队尾
dequeue()：返回1
队头 → [2][3] ← 队尾
e.应用场景
a.线程池
任务队列，等待执行的任务按顺序排队。
b.消息队列
RabbitMQ、Kafka等消息中间件。
c.连接池
数据库连接池，连接按顺序分配。
d.BFS算法
广度优先搜索使用队列存储待访问节点。
05.串（String）
a.定义与特点
a.字符序列
由N个字符组成的有限序列。
b.不可变性
Java中String是不可变的（immutable），修改会创建新对象。
b.Java实现
---
// String底层是char[]数组（JDK 9+改为byte[]）
String str = "Hello";
char[] chars = str.toCharArray(); // 转换为字符数组
// String不可变性示例
String s1 = "Hello";
String s2 = s1.concat(" World"); // 创建新对象，s1不变
// s1仍然是"Hello"
// s2是"Hello World"
// StringBuilder可变字符串（非线程安全）
StringBuilder sb = new StringBuilder();
sb.append("Hello"); // 追加
sb.append(" World");
String result = sb.toString(); // "Hello World"
// StringBuffer可变字符串（线程安全）
StringBuffer sbf = new StringBuffer();
sbf.append("Hello");
---
c.Go实现
---
// Go中string是不可变的
str := "Hello"
// str[0] = 'h' // 编译错误，不能修改
// 使用[]byte或[]rune修改
bytes := []byte(str)
bytes[0] = 'h'
newStr := string(bytes) // "hello"
// 使用strings.Builder高效拼接
var builder strings.Builder
builder.WriteString("Hello")
builder.WriteString(" World")
result := builder.String() // "Hello World"
---
d.图解说明
📌 String不可变性：
String s1 = "Hello";
内存：[H][e][l][l][o]
↑
s1
s1 = s1 + " World";
内存：[H][e][l][l][o] [H][e][l][l][o][ ][W][o][r][l][d]
↑
s1（指向新对象）
原字符串"Hello"成为垃圾，等待GC回收
e.常见操作
a.字符串拼接
使用StringBuilder/StringBuffer避免频繁创建对象。
b.字符串查找
indexOf、contains、startsWith、endsWith。
c.字符串分割
split方法，返回字符串数组。
1.3 非线性结构
01.多维数组（Multi-dimensional Array）
a.定义与特点
a.二维数组
数组的数组，可以理解为矩阵或表格结构。
b.内存布局
在内存中仍然是连续存储，按行优先或列优先排列。
c.随机访问
通过两个索引[i][j]可以O(1)访问任意元素。
b.Java实现
---
// 二维数组创建
int[][] matrix = new int[3][4]; // 3行4列
matrix[0][0] = 1; // 访问第1行第1列
// 直接初始化
int[][] arr = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// 遍历二维数组
for (int i = 0; i < arr.length; i++) { // 遍历行
for (int j = 0; j < arr[i].length; j++) { // 遍历列
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
// 📊 执行示例：
// 输出：
// 1 2 3
// 4 5 6
// 7 8 9
---
c.Go实现
---
// 二维数组创建
var matrix [3][4]int // 3行4列
matrix[0][0] = 1 // 访问第1行第1列
// 直接初始化
arr := [][]int{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
}
// 遍历二维数组
for i := 0; i < len(arr); i++ {
for j := 0; j < len(arr[i]); j++ {
fmt.Printf("%d ", arr[i][j])
}
fmt.Println()
}
// 使用range遍历
for i, row := range arr {
for j, val := range row {
fmt.Printf("arr[%d][%d] = %d\n", i, j, val)
}
}
---
d.图解说明
📌 二维数组内存布局（3×3矩阵）：
逻辑视图：
[1][2][3]
[4][5][6]
[7][8][9]
内存布局（行优先）：
[1][2][3][4][5][6][7][8][9]
↑ 第0行 ↑ 第1行 ↑ 第2行
访问arr[1][2]：
地址 = 基地址 + (1 * 列数 + 2) * 元素大小
= 基地址 + (1 * 3 + 2) * 4
= 基地址 + 20
e.应用场景
a.矩阵运算
数学计算、图像处理。
b.动态规划
DP表格存储中间状态。
c.游戏地图
二维网格表示地图。
02.集合（Set）
a.定义与特点
a.元素唯一性
集合中不允许有重复元素。
b.无序性
元素没有固定的顺序（HashSet）。
c.快速查找
基于哈希表实现，查找效率O(1)。
b.Java实现
---
// HashSet - 基于哈希表，无序
Set<Integer> set = new HashSet<>();
set.add(1); // 添加元素
set.add(2);
set.add(1); // 重复元素，不会添加
set.contains(1); // 查找O(1)，返回true
set.remove(1); // 删除O(1)
// 📊 执行示例：
// add(1)：set = {1}
// add(2)：set = {1, 2}
// add(1)：set = {1, 2}（重复，不添加）
// size = 2
// TreeSet - 基于红黑树，有序
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(1);
treeSet.add(2);
// 输出：[1, 2, 3]（自动排序）
// LinkedHashSet - 保持插入顺序
Set<Integer> linkedSet = new LinkedHashSet<>();
linkedSet.add(3);
linkedSet.add(1);
linkedSet.add(2);
// 输出：[3, 1, 2]（插入顺序）
---
c.Go实现
---
// Go没有内置Set，使用map模拟
set := make(map[int]bool)
// 添加元素
set[1] = true
set[2] = true
set[1] = true // 重复，覆盖原值
// 查找元素
if set[1] {
fmt.Println("1 exists")
}
// 删除元素
delete(set, 1)
// 遍历集合
for key := range set {
fmt.Println(key)
}
// 📊 执行示例：
// set[1] = true：map[1:true]
// set[2] = true：map[1:true 2:true]
// set[1] = true：map[1:true 2:true]（覆盖）
// len(set) = 2
---
d.集合运算
---
// Java集合运算
Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3));
Set<Integer> b = new HashSet<>(Arrays.asList(2, 3, 4));
// 并集
Set<Integer> union = new HashSet<>(a);
union.addAll(b); // {1, 2, 3, 4}
// 交集
Set<Integer> intersection = new HashSet<>(a);
intersection.retainAll(b); // {2, 3}
// 差集
Set<Integer> difference = new HashSet<>(a);
difference.removeAll(b); // {1}
---
e.应用场景
a.去重
数据去重、统计唯一元素。
b.快速查找
判断元素是否存在。
c.集合运算
并集、交集、差集。
03.树（Tree）
a.定义与特点
a.层次结构
由根节点和子树组成，具有明显的层次关系。
b.节点关系
每个节点最多有一个父节点，可以有多个子节点。
c.无环性
树中不存在环路。
b.树的分类
a.二叉树
每个节点最多有两个子节点（左子节点和右子节点）。
b.完全二叉树
除最后一层外，其他层节点数达到最大，最后一层节点靠左排列。
c.满二叉树
所有层的节点数都达到最大值。
d.二叉搜索树（BST）
左子树所有节点 < 根节点 < 右子树所有节点。
c.Java实现
---
// 二叉树节点定义
class TreeNode {
int val;
TreeNode left; // 左子节点
TreeNode right; // 右子节点
TreeNode(int val) { this.val = val; }
}
// 二叉树基本操作
public class BinaryTree {
private TreeNode root;
// 前序遍历：根 -> 左 -> 右
public void preorder(TreeNode node) {
if (node == null) return;
System.out.print(node.val + " "); // 访问根
preorder(node.left); // 遍历左子树
preorder(node.right); // 遍历右子树
}
// 中序遍历：左 -> 根 -> 右
public void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left); // 遍历左子树
System.out.print(node.val + " "); // 访问根
inorder(node.right); // 遍历右子树
}
// 后序遍历：左 -> 右 -> 根
public void postorder(TreeNode node) {
if (node == null) return;
postorder(node.left); // 遍历左子树
postorder(node.right); // 遍历右子树
System.out.print(node.val + " "); // 访问根
}
}
// 📊 执行示例：
// 树结构：
// 1
// / \
// 2 3
// / \
// 4 5
// 前序遍历：1 2 4 5 3
// 中序遍历：4 2 5 1 3
// 后序遍历：4 5 2 3 1
---
d.Go实现
---
// 二叉树节点定义
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// 前序遍历
func preorder(node *TreeNode) {
if node == nil {
return
}
fmt.Printf("%d ", node.Val) // 访问根
preorder(node.Left) // 遍历左子树
preorder(node.Right) // 遍历右子树
}
// 中序遍历
func inorder(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left) // 遍历左子树
fmt.Printf("%d ", node.Val) // 访问根
inorder(node.Right) // 遍历右子树
}
// 后序遍历
func postorder(node *TreeNode) {
if node == nil {
return
}
postorder(node.Left) // 遍历左子树
postorder(node.Right) // 遍历右子树
fmt.Printf("%d ", node.Val) // 访问根
}
---
e.图解说明
📌 二叉树结构：
1 (根节点)
/ \
2 3
/ \
4 5
📌 三种遍历方式：
前序遍历（根-左-右）：
1 → 2 → 4 → 5 → 3
中序遍历（左-根-右）：
4 → 2 → 5 → 1 → 3
后序遍历（左-右-根）：
4 → 5 → 2 → 3 → 1
f.应用场景
a.文件系统
目录树结构。
b.表达式树
数学表达式的树形表示。
c.数据库索引
B+树、B树索引。
04.图（Graph）
a.定义与特点
a.节点和边
由节点的有穷集合V和边的集合E组成，G = (V, E)。
b.任意连接
节点之间可以有任意的连接关系。
c.有向图和无向图
有向图：边有方向；无向图：边无方向。
b.图的表示方法
a.邻接矩阵
使用二维数组表示，matrix[i][j] = 1表示i到j有边。
b.邻接表
使用链表数组表示，每个节点维护一个邻居列表。
c.Java实现
---
// 邻接表表示（使用ArrayList）
public class Graph {
private int V; // 节点数
private List<List<Integer>> adj; // 邻接表
public Graph(int v) {
V = v;
adj = new ArrayList<>();
for (int i = 0; i < v; i++) {
adj.add(new ArrayList<>());
}
}
// 添加边（无向图）
public void addEdge(int u, int v) {
adj.get(u).add(v); // u -> v
adj.get(v).add(u); // v -> u
}
// BFS广度优先遍历
public void bfs(int start) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
// DFS深度优先遍历
public void dfs(int node, boolean[] visited) {
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, visited);
}
}
}
}
// 📊 执行示例：
// 图结构：
// 0 --- 1
// | |
// 2 --- 3
// BFS从0开始：0 1 2 3
// DFS从0开始：0 1 3 2
---
d.Go实现
---
// 邻接表表示
type Graph struct {
V int // 节点数
adj [][]int // 邻接表
}
func NewGraph(v int) *Graph {
return &Graph{
V: v,
adj: make([][]int, v),
}
}
// 添加边（无向图）
func (g *Graph) AddEdge(u, v int) {
g.adj[u] = append(g.adj[u], v) // u -> v
g.adj[v] = append(g.adj[v], u) // v -> u
}
// BFS广度优先遍历
func (g *Graph) BFS(start int) {
visited := make([]bool, g.V)
queue := []int{start}
visited[start] = true
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
fmt.Printf("%d ", node)
for _, neighbor := range g.adj[node] {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
}
// DFS深度优先遍历
func (g *Graph) DFS(node int, visited []bool) {
visited[node] = true
fmt.Printf("%d ", node)
for _, neighbor := range g.adj[node] {
if !visited[neighbor] {
g.DFS(neighbor, visited)
}
}
}
---
e.图解说明
📌 图的两种表示方法：
图结构：
0 --- 1
| |
2 --- 3
邻接矩阵：
0 1 2 3
0 [ 0 1 1 0 ]
1 [ 1 0 0 1 ]
2 [ 1 0 0 1 ]
3 [ 0 1 1 0 ]
邻接表：
0 -> [1, 2]
1 -> [0, 3]
2 -> [0, 3]
3 -> [1, 2]
f.应用场景
a.社交网络
用户关系图。
b.地图导航
最短路径算法。
c.网络拓扑
计算机网络结构。
05.散列表（Hash Table）
a.定义与特点
a.键值对存储
根据关键码（key）和值（value）直接进行访问的数据结构。
b.哈希函数
通过哈希函数计算key的存储位置。
c.快速访问
理想情况下，查找、插入、删除都是O(1)。
b.哈希冲突解决
a.链地址法
冲突的元素存储在链表中。
b.开放地址法
线性探测、二次探测、双重哈希。
c.Java实现
---
// HashMap使用
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1); // 插入O(1)
map.put("banana", 2);
map.get("apple"); // 查找O(1)，返回1
map.remove("apple"); // 删除O(1)
map.containsKey("apple"); // 判断key存在O(1)
// 📊 执行示例：
// put("apple", 1)：{"apple": 1}
// put("banana", 2)：{"apple": 1, "banana": 2}
// get("apple")：返回1
// remove("apple")：{"banana": 2}
// 遍历HashMap
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
---
d.Go实现
---
// Go的map（内置哈希表）
m := make(map[string]int)
m["apple"] = 1 // 插入O(1)
m["banana"] = 2
val := m["apple"] // 查找O(1)，返回1
delete(m, "apple") // 删除O(1)
// 检查key是否存在
if val, ok := m["apple"]; ok {
fmt.Println("apple:", val)
} else {
fmt.Println("apple not found")
}
// 遍历map
for key, value := range m {
fmt.Printf("%s: %d\n", key, value)
}
---
e.hashCode原理
a.Java中的hashCode
所有class都是Object的子类，继承了hashCode()方法。
b.默认实现
native方法，通过对象的内存地址和对象的值，使用哈希散列算法计算出int数字。
c.重写hashCode
如果重写了equals()，必须重写hashCode()，保证相等的对象有相同的哈希值。
f.图解说明
📌 哈希表结构（链地址法）：
哈希函数：hash(key) % 10
索引 链表
0 -> null
1 -> ["apple", 1] -> ["grape", 5]
2 -> ["banana", 2]
3 -> null
4 -> ["cherry", 3]
5 -> null
...
插入"apple"：
1. hash("apple") = 31
2. 31 % 10 = 1
3. 在索引1处插入
g.应用场景
a.缓存
LRU缓存、Redis。
b.数据库索引
哈希索引。
c.去重
快速判断元素是否存在。
1.4 附：8种数据结构
01.顺序表（数组）
a.介绍
顺序表是以数组为基础的数据结构，具有随机访问的特点，支持增删改查等基本操作。
b.算法技巧详解
a.线性枚举
逐一列举数组中的元素，常用于简单的查找或统计问题。
---
// Java实现：查找数组中的最大值
public int findMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 时间复杂度：O(n)
// Go实现
func findMax(arr []int) int {
max := arr[0]
for i := 1; i < len(arr); i++ {
if arr[i] > max {
max = arr[i]
}
}
return max
}
---
b.前缀和
用来快速计算某段连续子数组的和，预处理O(n)，查询O(1)。
---
// Java实现：区间求和
public class PrefixSum {
private int[] prefix;
public PrefixSum(int[] arr) {
prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}
}
// 查询区间[left, right]的和
public int rangeSum(int left, int right) {
return prefix[right + 1] - prefix[left];
}
}
// 📊 执行示例：
// arr = [1, 2, 3, 4, 5]
// prefix = [0, 1, 3, 6, 10, 15]
// rangeSum(1, 3) = prefix[4] - prefix[1] = 10 - 1 = 9 (即2+3+4)
// Go实现
type PrefixSum struct {
prefix []int
}
func NewPrefixSum(arr []int) *PrefixSum {
prefix := make([]int, len(arr)+1)
for i := 0; i < len(arr); i++ {
prefix[i+1] = prefix[i] + arr[i]
}
return &PrefixSum{prefix: prefix}
}
func (p *PrefixSum) RangeSum(left, right int) int {
return p.prefix[right+1] - p.prefix[left]
}
---
c.双指针
在数组上使用两个指针以不同的步伐进行移动，常用于滑动窗口、区间查找等。
---
// Java实现：两数之和（有序数组）
public int[] twoSum(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
return new int[]{left, right};
} else if (sum < target) {
left++; // 和太小，左指针右移
} else {
right--; // 和太大，右指针左移
}
}
return new int[]{-1, -1};
}
// 📊 执行示例：
// arr = [1, 2, 3, 4, 5], target = 7
// left=0, right=4: 1+5=6 < 7, left++
// left=1, right=4: 2+5=7, 找到！
// Go实现
func twoSum(arr []int, target int) []int {
left, right := 0, len(arr)-1
for left < right {
sum := arr[left] + arr[right]
if sum == target {
return []int{left, right}
} else if sum < target {
left++
} else {
right--
}
}
return []int{-1, -1}
}
---
d.二分查找
在有序数组中查找元素，时间复杂度为O(log n)。
---
// Java实现
public int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
---
e.离散化
将数据映射到较小范围的整数，用于降低复杂度。
---
// Java实现：坐标压缩
public int[] discretize(int[] arr) {
int[] sorted = arr.clone();
Arrays.sort(sorted);
Map<Integer, Integer> map = new HashMap<>();
int idx = 0;
for (int num : sorted) {
if (!map.containsKey(num)) {
map.put(num, idx++);
}
}
int[] result = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
result[i] = map.get(arr[i]);
}
return result;
}
// 📊 执行示例：
// arr = [100, 5, 1000, 5, 50]
// 离散化后 = [1, 0, 2, 0, 1]
// 映射：5->0, 50->1, 100->2, 1000->3
---
c.排序算法对比
算法名称 最好 平均 最坏 空间 稳定性
冒泡排序 O(n) O(n²) O(n²) O(1) 稳定
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定
插入排序 O(n) O(n²) O(n²) O(1) 稳定
希尔排序 O(n) O(n^1.3) O(n²) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n²) O(logn) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
计数排序 O(n+k) O(n+k) O(n+k) O(k) 稳定
基数排序 O(n*k) O(n*k) O(n*k) O(n+k) 稳定
d.常用思想
a.模拟
直接按照题意逐步实现，适合逻辑清晰的问题。
b.贪心
每一步选择局部最优解，求全局最优，需要证明贪心策略的正确性。
02.链表
a.介绍
链表是一种动态数据结构，适合频繁插入和删除操作。
b.类型与实现
a.单向链表
只有一个方向的指针，节点包含数据域和next指针。
---
// Java实现：反转链表
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // 保存下一个节点
curr.next = prev; // 反转指针
prev = curr; // prev前进
curr = next; // curr前进
}
return prev;
}
// 📊 执行示例：
// 原链表：1 -> 2 -> 3 -> null
// 反转后：3 -> 2 -> 1 -> null
// Go实现
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
curr := head
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}
---
b.双向链表
每个节点有prev和next两个指针，便于双向遍历。
---
// Java实现：双向链表节点
class DoublyListNode {
int val;
DoublyListNode prev;
DoublyListNode next;
DoublyListNode(int val) { this.val = val; }
}
// 删除节点（已知节点引用）
public void deleteNode(DoublyListNode node) {
if (node.prev != null) {
node.prev.next = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
}
}
// 时间复杂度：O(1)，无需遍历
---
c.经典问题
a.环形链表检测
使用快慢指针（Floyd判圈算法）。
b.链表中点
快指针走2步，慢指针走1步。
c.合并K个有序链表
使用最小堆（优先队列）。
03.栈
a.介绍
栈是一种LIFO（后进先出）的数据结构。
b.类型与应用
a.普通栈
用于函数调用、括号匹配等。
---
// Java实现：括号匹配
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
Map<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
for (char c : s.toCharArray()) {
if (map.containsKey(c)) {
// 右括号
if (stack.isEmpty() || stack.pop() != map.get(c)) {
return false;
}
} else {
// 左括号
stack.push(c);
}
}
return stack.isEmpty();
}
// 📊 执行示例：
// 输入："({[]})"
// 过程：push( push{ push[ pop[ pop{ pop} pop(
// 结果：true（匹配成功）
// Go实现
func isValid(s string) bool {
stack := []rune{}
pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
for _, c := range s {
if open, ok := pairs[c]; ok {
if len(stack) == 0 || stack[len(stack)-1] != open {
return false
}
stack = stack[:len(stack)-1]
} else {
stack = append(stack, c)
}
}
return len(stack) == 0
}
---
b.单调栈
栈内元素单调递增或递减，用于解决区间最值问题。
---
// Java实现：下一个更大元素
public int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>(); // 存储索引
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}
// 📊 执行示例：
// nums = [2, 1, 2, 4, 3]
// result = [4, 2, 4, -1, -1]
// 解释：2的下一个更大是4，1的下一个更大是2...
---
04.队列
a.介绍
队列是一种FIFO（先进先出）的数据结构。
b.类型与应用
a.普通队列
常用于广度优先搜索（BFS）。
---
// Java实现：二叉树层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
// 📊 执行示例：
// 树结构： 1
// / \
// 2 3
// / \
// 4 5
// 结果：[[1], [2,3], [4,5]]
---
b.双端队列
可从两端插入和删除元素，Java使用Deque接口。
---
// Java实现
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1); // 头部插入
deque.addLast(2); // 尾部插入
deque.removeFirst(); // 头部删除
deque.removeLast(); // 尾部删除
---
c.单调队列
队列中的元素保持单调性，适用于滑动窗口问题。
---
// Java实现：滑动窗口最大值
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new ArrayDeque<>(); // 存储索引
int[] result = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
// 移除窗口外的元素
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// 维护单调递减队列
while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
// 记录窗口最大值
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
// 📊 执行示例：
// nums = [1,3,-1,-3,5,3,6,7], k = 3
// 窗口 [1,3,-1]，最大值3
// 窗口 [3,-1,-3]，最大值3
// 窗口 [-1,-3,5]，最大值5
// ...
// result = [3,3,5,5,6,7]
---
05.字符串
a.介绍
字符串问题常见的有模式匹配、前缀树等。
b.经典算法实现
a.KMP算法
用于字符串模式匹配，时间复杂度O(n+m)。
---
// Java实现：KMP模式匹配
public int kmp(String text, String pattern) {
int n = text.length(), m = pattern.length();
int[] next = buildNext(pattern);
int i = 0, j = 0;
while (i < n) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
if (j == m) return i - m; // 匹配成功
} else if (j > 0) {
j = next[j - 1]; // 利用next数组跳过已匹配部分
} else {
i++;
}
}
return -1;
}
private int[] buildNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
// 📊 执行示例：
// text = "ababcababa", pattern = "ababa"
// 返回：5（从索引5开始匹配）
---
b.字典树（Trie）
用于词频统计、单词查找，前缀匹配。
---
// Java实现
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd = false;
}
class Trie {
private TrieNode root = new TrieNode();
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
}
node.isEnd = true;
}
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) return false;
node = node.children[idx];
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) return false;
node = node.children[idx];
}
return true;
}
}
// 📊 执行示例：
// insert("apple"), insert("app")
// search("app") -> true
// search("appl") -> false
// startsWith("app") -> true
---
c.其他算法
马拉车算法：求最长回文子串，时间复杂度O(n)。
AC自动机：多模式串匹配，结合字典树和KMP。
后缀数组：字符串后缀排序，求最长重复子串。
BM算法：长文本中快速定位模式串。
06.树
a.介绍
树是分层结构的数据结构，广泛用于存储有层次关系的数据。
b.常见树类型
a.二叉搜索树（BST）
左子树 < 根 < 右子树，支持O(log n)查找。
---
// Java实现：BST插入
public TreeNode insert(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) {
root.left = insert(root.left, val);
} else if (val > root.val) {
root.right = insert(root.right, val);
}
return root;
}
// BST查找
public TreeNode search(TreeNode root, int val) {
if (root == null || root.val == val) return root;
if (val < root.val) return search(root.left, val);
return search(root.right, val);
}
// 📊 执行示例：
// 插入序列：5, 3, 7, 1, 9
// 树结构： 5
// / \
// 3 7
// / \
// 1 9
---
b.堆（Heap）
完全二叉树，常用于优先队列，父节点 >= 子节点（最大堆）。
---
// Java实现：使用PriorityQueue
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(3);
minHeap.offer(7);
int min = minHeap.poll(); // 返回3（最小值）
// 最大堆
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(5);
maxHeap.offer(3);
maxHeap.offer(7);
int max = maxHeap.poll(); // 返回7（最大值）
---
c.其他树类型
AVL树：自平衡二叉搜索树，保证高度平衡。
红黑树：平衡二叉树，Java的TreeMap/TreeSet底层实现。
线段树：动态维护区间和、区间最值。
B+树：多路搜索树，数据库索引（MySQL InnoDB）。
字典树：见字符串部分。
07.图
a.介绍
图是一种复杂的结构，表示节点间的关系，G = (V, E)。
b.核心算法实现
a.最短路算法
Dijkstra算法：单源最短路，不能有负权边。
---
// Java实现：Dijkstra算法
public int[] dijkstra(int[][] graph, int start) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[0], d = curr[1];
if (d > dist[u]) continue;
for (int v = 0; v < n; v++) {
if (graph[u][v] > 0) {
int newDist = dist[u] + graph[u][v];
if (newDist < dist[v]) {
dist[v] = newDist;
pq.offer(new int[]{v, newDist});
}
}
}
}
return dist;
}
// 📊 执行示例：
// 图：0 --2--> 1 --3--> 2
// | |
// 4 1
// ↓ ↓
// 3 --1--> 2
// 从0到各点最短距离：[0, 2, 3, 4]
---
b.最小生成树
Kruskal算法：基于边的贪心算法，使用并查集。
---
// Java实现：Kruskal算法
class Edge implements Comparable<Edge> {
int u, v, weight;
Edge(int u, int v, int w) {
this.u = u; this.v = v; this.weight = w;
}
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}
public int kruskal(int n, List<Edge> edges) {
Collections.sort(edges); // 按权重排序
UnionFind uf = new UnionFind(n);
int mstWeight = 0;
for (Edge e : edges) {
if (uf.union(e.u, e.v)) { // 不形成环
mstWeight += e.weight;
}
}
return mstWeight;
}
---
c.并查集
用于动态连通性问题，支持合并和查找操作。
---
// Java实现：并查集
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
public boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false;
// 按秩合并
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}
---
d.其他算法
拓扑排序：有向无环图的线性排序。
强连通分量：Tarjan算法、Kosaraju算法。
二分图判定：DFS染色法。
最大流：Ford-Fulkerson、Dinic算法。
08.动态规划
a.介绍
动态规划是分治思想的延伸，常用于求解最优子结构问题。
b.经典问题实现
a.背包问题
0-1背包：每个物品只能选一次。
---
// Java实现：0-1背包
public int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
// 选或不选第i个物品
dp[i][w] = Math.max(
dp[i - 1][w], // 不选
dp[i - 1][w - weights[i - 1]] + values[i - 1] // 选
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
// 📊 执行示例：
// weights = [2, 3, 4], values = [3, 4, 5], capacity = 5
// 最优方案：选物品0和1，总价值7
// Go实现
func knapsack(weights, values []int, capacity int) int {
n := len(weights)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, capacity+1)
}
for i := 1; i <= n; i++ {
for w := 0; w <= capacity; w++ {
if weights[i-1] <= w {
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w-weights[i-1]]+values[i-1],
)
} else {
dp[i][w] = dp[i-1][w]
}
}
}
return dp[n][capacity]
}
---
b.最长公共子序列（LCS）
---
// Java实现
public int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// 📊 执行示例：
// s1 = "abcde", s2 = "ace"
// LCS = "ace"，长度3
---
c.其他DP类型
线性DP：最长递增子序列（LIS）。
区间DP：矩阵连乘、石子合并。
树形DP：树的直径、树上背包。
状态压缩DP：旅行商问题（TSP）。
数位DP：统计特定数字范围内满足条件的数。
1.5 附：算法优化内容
00.汇总
a.阶段一：核心基础（01.core.md）
a.目标
掌握基本数据结构
b.内容
数组、链表、栈、队列、树、图、哈希表
c.时长
2-3周
d.适合
零基础学习者
b.阶段二：基础算法（02.basic.md）
a.目标
掌握常用算法
b.内容
排序、查找、双指针、前缀和、差分、位运算
c.时长
3-4周
d.适合
有数据结构基础
c.阶段三：高级技巧（03.tech.md）
a.目标
掌握进阶算法
b.内容
动态规划、搜索、图论、高级数据结构
c.时长
4-6周
d.适合
有算法基础
d.阶段四：竞赛专家（04.expert.md）
a.目标
竞赛级别算法
b.内容
网络流、计算几何、数论、字符串算法
c.时长
6-8周
d.适合
参加竞赛
e.阶段五：实战练习（05.practice.md）
a.目标
面试和考试准备
b.内容
真题解析、面试高频题、综合训练
c.时长
持续练习
d.适合
求职准备
01.图解说明
a.算法执行过程的可视化描述
a.快速排序的分区过程
展示pivot选择、元素交换、分区结果。每一步的数组状态变化。递归调用的层次结构。
b.二叉树的遍历路径
前序、中序、后序的访问顺序。节点访问的先后关系。递归调用栈的变化。
c.动态规划的状态转移图
状态空间的表格展示。状态转移的箭头指向。最优子结构的体现。
b.数据结构的内部结构图
a.链表的节点连接
节点的数据域和指针域。单链表、双链表、循环链表的区别。头节点、尾节点的特殊处理。
b.堆的树形结构
完全二叉树的层次结构。父节点与子节点的关系。数组表示与树形表示的对应。
c.图的邻接表表示
顶点数组和边链表。有向图和无向图的区别。权重的存储方式。
02.代码详细解读
a.逐行代码注释
a.关键变量的含义
变量命名的意义。变量的作用域和生命周期。变量之间的关系。
b.循环和递归的逻辑
循环不变式的维护。递归的终止条件。递归的状态转移。
c.边界条件的处理
空数组、空链表的处理。单元素的特殊情况。索引越界的预防。
b.代码执行示例
a.输入样例
基本测试用例。边界测试用例。特殊测试用例。
b.中间过程
每一步的变量值。关键判断的结果。循环和递归的执行轨迹。
c.输出结果
最终返回值。副作用如数组修改。时间和空间消耗。
c.常见错误和陷阱
a.边界条件遗漏
未检查空指针。未处理空集合。索引计算错误。
b.整数溢出
int类型的范围限制。使用long类型的时机。取模运算的注意事项。
c.空指针异常
链表操作中的null检查。数组访问前的判断。Optional的使用。
03.算法推导过程
a.状态转移方程推导
a.从问题到子问题的分解
识别问题的最优子结构。定义子问题的边界。建立子问题之间的关系。
b.状态定义的思考过程
状态需要包含哪些信息。状态的维度选择。状态的初始化。
c.转移方程的建立
从子问题到原问题的推导。状态转移的数学表达。转移方程的优化。
b.复杂度分析详解
a.时间复杂度的数学推导
基本操作的识别。循环次数的计算。递归树的分析。
b.空间复杂度的计算
辅助空间的使用。递归栈的深度。原地算法的判断。
c.最好最坏平均情况分析
不同输入下的表现。期望时间复杂度。摊还分析。
04.实战题目详解
a.完整的题目解析
a.题目理解和分析
题目要求的核心。输入输出的格式。数据范围的限制。
b.解题思路的演化
暴力解法的思路。优化的切入点。最优解法的推导。
c.多种解法对比
时间复杂度对比。空间复杂度对比。代码简洁度对比。
b.测试用例
a.基本用例
题目给出的样例。简单的正常情况。功能验证。
b.边界用例
空输入。单元素。最大最小值。
c.压力测试用例
大数据量。极端情况。性能测试。
05.Go语言实现补充
a.完整的Go代码
a.目前很多part文件只有Java代码
需要补充对应的Go实现。保持与Java代码的功能一致。体现Go的语言特性。
b.需要补充对应的Go实现
使用Go的标准库。遵循Go的命名规范。利用Go的并发特性。
c.Go特有的语法和惯用法
切片的使用。defer的应用。goroutine和channel。接口的实现。错误处理方式。
06.应用场景扩展
a.实际应用案例
a.工程中的使用场景
Web开发中的应用。数据处理中的应用。系统设计中的应用。
b.系统设计中的应用
缓存策略如LRU和LFU。限流算法如令牌桶和漏桶。负载均衡算法。
c.性能优化实例
算法选择的优化。数据结构的优化。空间换时间的权衡。
b.变形题目
a.同一算法的不同应用
二分查找的变形。双指针的变形。动态规划的变形。
b.组合使用多种算法
贪心加优先队列。DP加单调栈。图论加并查集。
07.对比总结
a.算法对比表格
a.时间空间复杂度对比
各种排序算法对比。各种查找算法对比。各种图算法对比。
b.适用场景对比
数据规模的影响。数据特征的影响。实时性要求的影响。
c.优缺点对比
稳定性。原地性。实现难度。
b.数据结构选择指南
a.什么情况用什么数据结构
频繁查找用哈希表。有序数据用平衡树。FIFO用队列。LIFO用栈。
b.决策树流程图
根据操作频率选择。根据数据特征选择。根据性能要求选择。
08.补充优先级
a.高优先级
a.代码详细解读
让初学者能看懂每行代码。提供完整的执行示例。标注常见错误。
b.图解说明
可视化帮助理解抽象概念。展示算法执行过程。展示数据结构内部结构。
c.Go语言实现
补全双语言承诺。提供完整可运行的代码。体现Go的特性。
b.中优先级
a.实战题目详解
提升实战能力。提供多种解法。包含测试用例。
b.算法推导过程
深入理解原理。掌握推导方法。培养算法思维。
c.应用场景扩展
连接理论与实践。拓展知识面。提升工程能力。
c.低优先级
a.对比总结
系统性总结。便于查阅。辅助决策。
09.实施计划
a.第一阶段评估现有内容
a.随机抽查10到20个part文件
检查内容的详细程度。评估代码的完整性。确认图解的需求。
b.评估内容的详细程度
是否有足够的注释。是否有执行示例。是否有常见错误说明。
c.找出最需要补充的部分
优先补充基础算法。优先补充常用数据结构。优先补充高频面试题。
b.第二阶段制定补充计划
a.确定哪些part文件需要补充图解
排序算法需要图解。树的遍历需要图解。动态规划需要图解。
b.确定哪些part文件需要补充Go代码
所有只有Java代码的part文件。优先补充基础部分。保证代码质量。
c.确定哪些part文件需要补充详细解读
复杂算法需要详细解读。易错算法需要详细解读。高频题目需要详细解读。
c.第三阶段分批补充内容
a.优先补充基础篇01和02的详细内容
数据结构基础。基础算法。常见题目。
b.然后补充进阶篇03
动态规划。搜索算法。图论算法。
c.最后补充竞赛篇04和实战篇05
高级算法。竞赛技巧。面试题目。
d.第四阶段质量检查
a.确保每个part文件都有足够的深度
理论加代码加图解。Java加Go双语言。基础加进阶加实战。
b.确保代码可以直接运行
完整的import语句。完整的测试用例。清晰的输出说明。
c.确保图解清晰易懂
使用文字描述可视化过程。标注关键步骤。展示状态变化。
2 字符串
2.1 反转字符串
01.问题描述
给定一个字符串，返回反转后的字符串。
示例：输入"Hello World"，输出"dlroW olleH"
02.解法分析
a.方法一：StringBuilder的reverse方法
a.思路
利用StringBuilder内置的reverse方法，最简单直接。
b.时间复杂度
O(n)，StringBuilder内部使用字符数组实现。
c.空间复杂度
O(n)，需要创建StringBuilder对象。
d.优点
代码简洁，一行搞定。
e.缺点
创建额外对象，不是原地操作。
b.方法二：字符数组双指针
a.思路
将字符串转为字符数组，使用双指针从两端向中间交换。
b.时间复杂度
O(n)，遍历一半的字符。
c.空间复杂度
O(n)，需要字符数组（Java字符串不可变）。
d.优点
经典算法，面试常考。
e.缺点
Java中String不可变，必须创建新数组。
c.方法三：递归
a.思路
递归地将首字符移到末尾，逐步缩小范围。
b.时间复杂度
O(n²)，每次substring创建新字符串。
c.空间复杂度
O(n²)，递归栈O(n) + 每层创建字符串O(n)。
d.优点
代码简洁，体现递归思想。
e.缺点
效率低，不推荐实际使用。
03.代码实现
a.Java实现
---
public class ReverseString {
// 方法一：使用StringBuilder（推荐）
// 时间复杂度：O(n)，空间复杂度：O(n)
public static String reverseWithStringBuilder(String str) {
return new StringBuilder(str).reverse().toString();
}
// 📊 执行示例：
// 输入："Hello"
// StringBuilder内部：['H','e','l','l','o'] -> ['o','l','l','e','H']
// 输出："olleH"
// 方法二：使用字符数组和双指针（面试推荐）
// 时间复杂度：O(n)，空间复杂度：O(n)
public static String reverseWithArray(String str) {
char[] chars = str.toCharArray(); // 转为字符数组
int left = 0, right = chars.length - 1;
while (left < right) {
// 交换左右字符
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++; // 左指针右移
right--; // 右指针左移
}
return new String(chars);
}
// 📊 执行示例：
// 输入："Hello"
// chars = ['H','e','l','l','o']
// 第1次交换：left=0, right=4, ['o','e','l','l','H']
// 第2次交换：left=1, right=3, ['o','l','l','e','H']
// left=2, right=2, 停止
// 输出："olleH"
// 方法三：使用递归（不推荐，效率低）
// 时间复杂度：O(n²)，空间复杂度：O(n²)
public static String reverseWithRecursion(String str) {
if (str.length() <= 1) {
return str; // 递归终止条件
}
// 递归：首字符移到末尾
return reverseWithRecursion(str.substring(1)) + str.charAt(0);
}
// 📊 执行示例：
// 输入："abc"
// reverse("abc") = reverse("bc") + 'a'
// = (reverse("c") + 'b') + 'a'
// = (("c") + 'b') + 'a'
// = "cba"
public static void main(String[] args) {
String str = "Hello World";
System.out.println("原字符串: " + str);
System.out.println("方法一: " + reverseWithStringBuilder(str));
System.out.println("方法二: " + reverseWithArray(str));
System.out.println("方法三: " + reverseWithRecursion(str));
// 输出: dlroW olleH
}
}
---
b.Go实现
---
package main
import "fmt"
// 方法一：使用rune切片和双指针
// Go的string是不可变的，需要转为rune切片
func reverseString(s string) string {
runes := []rune(s) // 转为rune切片（支持Unicode）
left, right := 0, len(runes)-1
for left < right {
// 交换
runes[left], runes[right] = runes[right], runes[left]
left++
right--
}
return string(runes)
}
// 📊 执行示例：
// 输入："Hello"
// runes = ['H','e','l','l','o']
// 交换后：['o','l','l','e','H']
// 输出："olleH"
// 方法二：使用递归
func reverseStringRecursive(s string) string {
if len(s) <= 1 {
return s
}
return reverseStringRecursive(s[1:]) + string(s[0])
}
// 方法三：原地反转字节切片（仅适用于ASCII）
func reverseBytes(s string) string {
bytes := []byte(s)
left, right := 0, len(bytes)-1
for left < right {
bytes[left], bytes[right] = bytes[right], bytes[left]
left++
right--
}
return string(bytes)
}
func main() {
str := "Hello World"
fmt.Println("原字符串:", str)
fmt.Println("方法一:", reverseString(str))
fmt.Println("方法二:", reverseStringRecursive(str))
fmt.Println("方法三:", reverseBytes(str))
// 输出: dlroW olleH
}
---
04.图解说明
📌 双指针反转过程（以"ABCDE"为例）：
初始状态：
left right
↓ ↓
[A] [B] [C] [D] [E]
第1次交换：
left right
↓ ↓
[E] [B] [C] [D] [A]
第2次交换：
left right
↓ ↓
[E] [D] [C] [B] [A]
left和right相遇，停止
最终结果：[E] [D] [C] [B] [A]
05.常见错误与陷阱
⚠️ 常见错误：
1. 忘记处理空字符串
错误：直接访问chars[0]
正确：先检查str.isEmpty()或length == 0
2. Unicode字符处理错误
错误：使用byte[]处理包含中文的字符串
正确：使用char[]（Java）或rune[]（Go）
示例："你好" -> byte[]会乱码，应该用char[]
3. 递归栈溢出
错误：对超长字符串使用递归
后果：StackOverflowError
正确：使用迭代方法
4. 字符串不可变性
错误：尝试修改原字符串str[0] = 'x'
正确：Java和Go的字符串都是不可变的，必须创建新字符串
06.性能对比
方法 时间复杂度 空间复杂度 推荐度
StringBuilder O(n) O(n) ⭐⭐⭐⭐⭐
双指针 O(n) O(n) ⭐⭐⭐⭐⭐
递归 O(n²) O(n²) ⭐⭐
07.应用场景
a.回文判断
判断字符串是否为回文，反转后与原字符串比较。
b.字符串处理
某些算法需要从后向前处理字符串。
c.面试题目
LeetCode 344: Reverse String（原地反转字符数组）
2.2 最长公共前缀
01.问题描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串""。
示例1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
02.解法分析
a.方法一：水平扫描法
a.思路
以第一个字符串为基准，依次与后续字符串比较，逐步缩短公共前缀。
b.时间复杂度
O(S)，S是所有字符串的字符总数。
c.空间复杂度
O(1)，只使用常数额外空间。
d.优点
实现简单，易于理解。
e.缺点
如果第一个字符串很长但公共前缀很短，会做很多无用比较。
b.方法二：垂直扫描法
a.思路
逐列比较所有字符串的字符，从第一列开始，直到发现不匹配。
b.时间复杂度
O(S)，但在最坏情况下可以提前终止。
c.空间复杂度
O(1)。
d.优点
可以提前终止，避免不必要的比较。
e.缺点
需要多次访问字符串。
c.方法三：分治法
a.思路
将字符串数组分成两部分，递归求解左右两部分的最长公共前缀，然后合并。
b.时间复杂度
O(S)，但有递归开销。
c.空间复杂度
O(m log n)，m是字符串平均长度，n是字符串数量（递归栈）。
d.优点
体现分治思想，适合并行处理。
e.缺点
实现复杂，递归开销大。
03.代码实现
a.Java实现
---
public class LongestCommonPrefix {
// 方法一：水平扫描法（推荐）
// 时间复杂度：O(S)，空间复杂度：O(1)
public static String longestCommonPrefixHorizontal(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String prefix = strs[0]; // 以第一个字符串为基准
for (int i = 1; i < strs.length; i++) {
// 不断缩短prefix，直到strs[i]以prefix开头
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) {
return "";
}
}
}
return prefix;
}
// 📊 执行示例：
// 输入：["flower", "flow", "flight"]
// prefix = "flower"
// 比较"flow"：indexOf("flower") != 0，缩短为"flowe"
// 继续缩短："flow"、"flo"、"fl"，indexOf("fl") == 0，匹配！
// 比较"flight"："fl"匹配
// 输出："fl"
// 方法二：垂直扫描法
// 时间复杂度：O(S)，空间复杂度：O(1)
public static String longestCommonPrefixVertical(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
// 逐列比较
for (int i = 0; i < strs[0].length(); i++) {
char c = strs[0].charAt(i); // 第i列的字符
// 检查所有字符串的第i个字符
for (int j = 1; j < strs.length; j++) {
if (i == strs[j].length() || strs[j].charAt(i) != c) {
return strs[0].substring(0, i);
}
}
}
return strs[0]; // 第一个字符串就是公共前缀
}
// 📊 执行示例：
// 输入：["flower", "flow", "flight"]
// i=0: 所有字符串第0个字符都是'f'，继续
// i=1: 所有字符串第1个字符都是'l'，继续
// i=2: flower[2]='o', flow[2]='o', flight[2]='i'，不匹配！
// 返回strs[0].substring(0, 2) = "fl"
// 方法三：分治法
// 时间复杂度：O(S)，空间复杂度：O(m log n)
public static String longestCommonPrefixDivide(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
return divideAndConquer(strs, 0, strs.length - 1);
}
private static String divideAndConquer(String[] strs, int left, int right) {
if (left == right) {
return strs[left]; // 只有一个字符串
}
int mid = (left + right) / 2;
String lcpLeft = divideAndConquer(strs, left, mid);
String lcpRight = divideAndConquer(strs, mid + 1, right);
return commonPrefix(lcpLeft, lcpRight);
}
private static String commonPrefix(String left, String right) {
int minLen = Math.min(left.length(), right.length());
for (int i = 0; i < minLen; i++) {
if (left.charAt(i) != right.charAt(i)) {
return left.substring(0, i);
}
}
return left.substring(0, minLen);
}
// 📊 执行示例：
// 输入：["flower", "flow", "flight", "fly"]
// 分治过程：
// ["flower","flow","flight","fly"]
// / \
// ["flower","flow"] ["flight","fly"]
// / \ / \
// "flower" "flow" "flight" "fly"
// \ / \ /
// "flow" "fl"
// \ /
// "fl"
public static void main(String[] args) {
String[] strs1 = {"flower", "flow", "flight"};
String[] strs2 = {"dog", "racecar", "car"};
System.out.println("最长公共前缀: " + longestCommonPrefixHorizontal(strs1));
System.out.println("最长公共前缀: " + longestCommonPrefixVertical(strs2));
// 输出: fl
// 输出: (空字符串)
}
}
---
b.Go实现
---
package main
import "fmt"
// 方法一：水平扫描法
func longestCommonPrefixHorizontal(strs []string) string {
if len(strs) == 0 {
return ""
}
prefix := strs[0]
for i := 1; i < len(strs); i++ {
for len(prefix) > 0 && !hasPrefix(strs[i], prefix) {
prefix = prefix[:len(prefix)-1]
}
if prefix == "" {
return ""
}
}
return prefix
}
func hasPrefix(s, prefix string) bool {
if len(s) < len(prefix) {
return false
}
return s[:len(prefix)] == prefix
}
// 方法二：垂直扫描法
func longestCommonPrefixVertical(strs []string) string {
if len(strs) == 0 {
return ""
}
for i := 0; i < len(strs[0]); i++ {
c := strs[0][i]
for j := 1; j < len(strs); j++ {
if i == len(strs[j]) || strs[j][i] != c {
return strs[0][:i]
}
}
}
return strs[0]
}
func main() {
strs1 := []string{"flower", "flow", "flight"}
strs2 := []string{"dog", "racecar", "car"}
fmt.Println("最长公共前缀:", longestCommonPrefixHorizontal(strs1))
fmt.Println("最长公共前缀:", longestCommonPrefixVertical(strs2))
// 输出: fl
// 输出: (空字符串)
}
---
04.图解说明
📌 水平扫描法过程（以["flower","flow","flight"]为例）：
初始状态：
prefix = "flower"
比较"flow"：
"flower" vs "flow"
↓ 不匹配，缩短
"flowe" vs "flow"
↓ 不匹配，缩短
"flow" vs "flow"
✓ 匹配！prefix = "flow"
比较"flight"：
"flow" vs "flight"
↓ 不匹配，缩短
"flo" vs "flight"
↓ 不匹配，缩短
"fl" vs "flight"
✓ 匹配！prefix = "fl"
最终结果："fl"
📌 垂直扫描法过程：
字符串数组：
f l o w e r
f l o w
f l i g h t
↓ ↓ ↓
列0: f=f=f ✓
列1: l=l=l ✓
列2: o=o≠i ✗ 停止
返回前2个字符："fl"
05.常见错误与陷阱
⚠️ 常见错误：
1. 空数组处理
错误：未检查strs == null或strs.length == 0
后果：NullPointerException或ArrayIndexOutOfBoundsException
正确：先检查边界条件
2. 字符串长度不一致
错误：未检查i >= strs[j].length()
后果：StringIndexOutOfBoundsException
正确：垂直扫描时要检查字符串长度
3. indexOf使用错误
错误：认为indexOf返回-1表示不匹配
正确：indexOf返回0表示从开头匹配，返回-1或>0都表示不匹配
4. 空字符串处理
错误：未考虑数组中有空字符串的情况
正确：如果有空字符串，公共前缀必然是空字符串
06.性能对比
方法 时间复杂度 空间复杂度 推荐度
水平扫描 O(S) O(1) ⭐⭐⭐⭐⭐
垂直扫描 O(S) O(1) ⭐⭐⭐⭐
分治法 O(S) O(m log n) ⭐⭐⭐
注：S为所有字符串的字符总数，m为字符串平均长度，n为字符串数量
07.应用场景
a.文件路径处理
查找多个文件路径的公共目录前缀。
b.URL处理
查找多个URL的公共域名部分。
c.字符串匹配
在搜索引擎中，查找多个搜索词的公共前缀进行提示。
d.面试题目
LeetCode 14: Longest Common Prefix
2.3 字符串转整数（atoi）
01.问题描述
实现atoi函数，将字符串转换为32位有符号整数（类似C/C++的atoi函数）。
算法步骤：
1. 读入字符串并丢弃无用的前导空格
2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）
3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾
4. 将前面步骤读入的数字转换为整数
5. 如果整数超过32位有符号整数范围[−2³¹, 2³¹−1]，需要截断
示例：
输入："42" → 输出：42
输入：" -42" → 输出：-42
输入："4193 with words" → 输出：4193
输入："words and 987" → 输出：0
输入："-91283472332" → 输出：-2147483648（溢出）
02.解法分析
a.状态机方法
a.思路
使用有限状态机处理不同状态的转换。
b.时间复杂度
O(n)，遍历一次字符串。
c.空间复杂度
O(1)，只使用常数额外空间。
d.关键点
1. 处理前导空格
2. 处理正负号（只能有一个）
3. 处理数字字符
4. 处理溢出（在乘10之前检查）
03.代码实现
a.Java实现
---
public class StringToInteger {
// 时间复杂度：O(n)，空间复杂度：O(1)
public static int myAtoi(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int index = 0;
int n = s.length();
// 步骤1：去除前导空格
while (index < n && s.charAt(index) == ' ') {
index++;
}
// 全是空格的情况
if (index == n) {
return 0;
}
// 步骤2：处理正负号
int sign = 1;
if (s.charAt(index) == '+' || s.charAt(index) == '-') {
sign = s.charAt(index) == '+' ? 1 : -1;
index++;
}
// 步骤3：转换数字
int result = 0;
while (index < n && Character.isDigit(s.charAt(index))) {
int digit = s.charAt(index) - '0';
// 步骤4：检查溢出（在乘10之前检查）
// result > MAX/10：下一步result*10必定溢出
// result == MAX/10 && digit > MAX%10：下一步result*10+digit会溢出
if (result > Integer.MAX_VALUE / 10 ||
(result == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
result = result * 10 + digit;
index++;
}
return result * sign;
}
// 📊 执行示例：
// 输入：" -42"
// index=0: ' ' -> 跳过
// index=1: ' ' -> 跳过
// index=2: ' ' -> 跳过
// index=3: '-' -> sign=-1, index=4
// index=4: '4' -> result=0*10+4=4
// index=5: '2' -> result=4*10+2=42
// 返回：42 * (-1) = -42
// 📊 溢出示例：
// 输入："2147483648"（MAX_VALUE+1）
// 处理到最后一位'8'时：
// result=214748364, digit=8
// result == MAX/10 (214748364) 且 digit(8) > MAX%10 (7)
// 返回：Integer.MAX_VALUE = 2147483647
public static void main(String[] args) {
System.out.println(myAtoi("42")); // 42
System.out.println(myAtoi(" -42")); // -42
System.out.println(myAtoi("4193 with words")); // 4193
System.out.println(myAtoi("words and 987")); // 0
System.out.println(myAtoi("-91283472332")); // -2147483648
System.out.println(myAtoi("2147483648")); // 2147483647
}
}
---
b.Go实现
---
package main
import (
"fmt"
"math"
)
func myAtoi(s string) int {
if len(s) == 0 {
return 0
}
index := 0
n := len(s)
// 步骤1：去除前导空格
for index < n && s[index] == ' ' {
index++
}
if index == n {
return 0
}
// 步骤2：处理正负号
sign := 1
if s[index] == '+' || s[index] == '-' {
if s[index] == '-' {
sign = -1
}
index++
}
// 步骤3：转换数字
result := 0
for index < n && s[index] >= '0' && s[index] <= '9' {
digit := int(s[index] - '0')
// 步骤4：检查溢出
if result > math.MaxInt32/10 ||
(result == math.MaxInt32/10 && digit > math.MaxInt32%10) {
if sign == 1 {
return math.MaxInt32
}
return math.MinInt32
}
result = result*10 + digit
index++
}
return result * sign
}
func main() {
fmt.Println(myAtoi("42")) // 42
fmt.Println(myAtoi(" -42")) // -42
fmt.Println(myAtoi("4193 with words")) // 4193
fmt.Println(myAtoi("words and 987")) // 0
fmt.Println(myAtoi("-91283472332")) // -2147483648
}
---
04.图解说明
📌 处理流程（以" -42"为例）：
字符串：" -42"
索引： 0123456
步骤1：跳过前导空格
index: 0 → 1 → 2 → 3
遇到'-'停止
步骤2：处理符号
s[3] = '-' → sign = -1
index = 4
步骤3：处理数字
s[4] = '4' → result = 0*10 + 4 = 4
s[5] = '2' → result = 4*10 + 2 = 42
s[6] 不是数字，停止
步骤4：返回结果
result * sign = 42 * (-1) = -42
📌 溢出检查原理：
Integer.MAX_VALUE = 2147483647
Integer.MAX_VALUE / 10 = 214748364
Integer.MAX_VALUE % 10 = 7
当前result = 214748364，下一位digit = 8
检查：result == MAX/10 且 digit > MAX%10
即：214748364 == 214748364 且 8 > 7
结论：下一步 result*10+digit 会溢出
返回：Integer.MAX_VALUE
05.常见错误与陷阱
⚠️ 常见错误：
1. 溢出检查时机错误
错误：先计算result = result*10+digit，再检查溢出
后果：已经溢出了，检查无意义
正确：在乘10之前检查是否会溢出
2. 符号处理错误
错误：允许多个符号如"+-2"
正确：只能有一个符号，且必须在数字之前
3. 空格处理不完整
错误：只处理前导空格，不处理中间空格
正确：遇到非数字字符（包括空格）就停止
示例："42 123" → 应返回42，不是42123
4. 边界值处理
错误：未考虑Integer.MIN_VALUE的特殊性
注意：MIN_VALUE = -2147483648，绝对值比MAX_VALUE大1
5. 字符判断错误
错误：使用s.charAt(index).isDigit()（不存在此方法）
正确：使用Character.isDigit(s.charAt(index))
06.复杂度分析
时间复杂度：O(n)，n为字符串长度，最多遍历一次
空间复杂度：O(1)，只使用常数个变量
07.应用场景
a.字符串解析
解析配置文件、命令行参数中的数字。
b.数据转换
将用户输入的字符串转换为整数进行计算。
c.面试题目
LeetCode 8: String to Integer (atoi)
2.4 统计字符出现次数
01.问题描述
给定一个字符串，统计每个字符出现的次数。
示例：
输入："aabccddeea"
输出：a=3, b=1, c=2, d=2, e=2
02.解法分析
a.方法一：HashMap
适用于任何字符集，灵活性最高。
时间复杂度：O(n)，空间复杂度：O(k)，k为不同字符数
b.方法二：数组计数
适用于ASCII或小写字母，空间固定，效率最高。
时间复杂度：O(n)，空间复杂度：O(1)或O(256)
c.方法三：TreeMap
自动按字符排序，适合需要有序输出的场景。
时间复杂度：O(n log k)，空间复杂度：O(k)
d.方法四：Stream API
Java 8+的函数式编程风格，代码简洁。
时间复杂度：O(n)，空间复杂度：O(k)
03.代码实现
a.Java实现
---
import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
public class CharacterCount {
// 方法一：使用HashMap（推荐，通用性强）
public static Map<Character, Integer> countUsingHashMap(String str) {
Map<Character, Integer> map = new HashMap<>();
for (char c : str.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
return map;
}
// 📊 执行示例：
// 输入："aabcc"
// 遍历'a'：map = {a=1}
// 遍历'a'：map = {a=2}
// 遍历'b'：map = {a=2, b=1}
// 遍历'c'：map = {a=2, b=1, c=1}
// 遍历'c'：map = {a=2, b=1, c=2}
// 方法二：使用数组（仅适用于ASCII字符，效率最高）
public static int[] countUsingArray(String str) {
int[] count = new int[256]; // ASCII字符集
for (char c : str.toCharArray()) {
count[c]++; // 字符的ASCII值作为索引
}
return count;
}
// 📊 执行示例：
// 输入："abc"
// count['a'] = count[97]++ -> count[97] = 1
// count['b'] = count[98]++ -> count[98] = 1
// count['c'] = count[99]++ -> count[99] = 1
// 方法三：使用TreeMap（自动排序）
public static Map<Character, Integer> countUsingTreeMap(String str) {
Map<Character, Integer> map = new TreeMap<>();
for (char c : str.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
return map;
}
// 方法四：使用Stream API（Java 8+）
public static Map<Character, Long> countUsingStream(String str) {
return str.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.groupingBy(
Function.identity(),
Collectors.counting()
));
}
public static void main(String[] args) {
String input = "aabccddeea";
System.out.println("HashMap: " + countUsingHashMap(input));
System.out.println("TreeMap: " + countUsingTreeMap(input));
System.out.println("Stream: " + countUsingStream(input));
}
}
---
b.Go实现
---
package main
import "fmt"
// 方法一：使用map
func countUsingMap(s string) map[rune]int {
count := make(map[rune]int)
for _, c := range s {
count[c]++
}
return count
}
// 方法二：使用数组（仅适用于小写字母）
func countUsingArray(s string) [26]int {
var count [26]int
for _, c := range s {
if c >= 'a' && c <= 'z' {
count[c-'a']++
}
}
return count
}
func main() {
str := "aabccddeea"
// 使用map
mapCount := countUsingMap(str)
fmt.Println("Map:", mapCount)
// 使用数组
arrCount := countUsingArray(str)
for i, cnt := range arrCount {
if cnt > 0 {
fmt.Printf("%c: %d\n", 'a'+i, cnt)
}
}
}
---
04.图解说明
📌 HashMap统计过程（以"aab"为例）：
初始：map = {}
遍历'a'：
map.getOrDefault('a', 0) = 0
map.put('a', 1)
map = {a=1}
遍历'a'：
map.getOrDefault('a', 0) = 1
map.put('a', 2)
map = {a=2}
遍历'b'：
map.getOrDefault('b', 0) = 0
map.put('b', 1)
map = {a=2, b=1}
📌 数组计数过程：
字符串："abc"
数组索引：0-25对应'a'-'z'
count['a'-'a'] = count[0]++ -> count[0] = 1
count['b'-'a'] = count[1]++ -> count[1] = 1
count['c'-'a'] = count[2]++ -> count[2] = 1
05.常见错误与陷阱
⚠️ 常见错误：
1. 字符集范围错误
错误：使用int[26]处理包含大写字母或特殊字符的字符串
正确：ASCII用int[256]，Unicode用HashMap
2. getOrDefault使用错误
错误：map.get(c) + 1（可能NullPointerException）
正确：map.getOrDefault(c, 0) + 1
3. 数组索引越界
错误：count[c]++（c可能超出数组范围）
正确：先检查c的范围，或使用HashMap
4. 重复计数
错误：遍历字符串时重复统计同一字符
正确：使用Set去重或直接用HashMap
06.性能对比
方法 时间复杂度 空间复杂度 适用场景
HashMap O(n) O(k) 任何字符集
数组 O(n) O(1) ASCII/小写字母
TreeMap O(n log k) O(k) 需要排序输出
Stream O(n) O(k) 函数式编程
07.应用场景
a.字符串分析
分析文本中各字符的频率分布。
b.数据压缩
霍夫曼编码需要统计字符频率。
c.异位词检测
比较两个字符串的字符频率是否相同。
d.面试题目
LeetCode 387: First Unique Character in a String
2.5 判断是否是回文字符串
01.问题描述
给定一个字符串，判断它是否是回文串。
回文串：正着读和反着读都一样的字符串。
示例：
输入："madam" → 输出：true
输入："hello" → 输出：false
输入："A man, a plan, a canal: Panama" → 输出：true（忽略大小写和非字母数字）
02.解法分析
a.方法一：反转字符串比较
思路：反转字符串，与原字符串比较是否相等。
时间复杂度：O(n)，空间复杂度：O(n)
优点：代码简洁，一行搞定
缺点：需要额外空间存储反转后的字符串
b.方法二：双指针法（推荐）
思路：左右指针从两端向中间移动，逐个比较字符。
时间复杂度：O(n)，空间复杂度：O(1)
优点：空间效率高，只需常数空间
缺点：需要手动实现比较逻辑
c.方法三：递归法
思路：递归比较首尾字符，逐步缩小范围。
时间复杂度：O(n)，空间复杂度：O(n)（递归栈）
优点：代码简洁，体现递归思想
缺点：递归栈开销大，不推荐实际使用
d.方法四：忽略大小写和非字母数字
思路：先清理字符串，只保留字母和数字，转小写后判断。
时间复杂度：O(n)，空间复杂度：O(n)
优点：符合实际应用场景
缺点：需要额外的字符串处理
03.代码实现
a.Java实现
---
public class Palindrome {
// 方法一：反转字符串比较
// 时间复杂度：O(n)，空间复杂度：O(n)
public static boolean isPalindromeByReverse(String str) {
if (str == null || str.length() <= 1) {
return true;
}
String reversed = new StringBuilder(str).reverse().toString();
return str.equals(reversed);
}
// 📊 执行示例：
// 输入："madam"
// reversed = "madam"
// "madam".equals("madam") = true
// 方法二：双指针法（推荐）
// 时间复杂度：O(n)，空间复杂度：O(1)
public static boolean isPalindromeByTwoPointers(String str) {
if (str == null || str.length() <= 1) {
return true;
}
int left = 0, right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// 📊 执行示例：
// 输入："madam"
// left=0, right=4: 'm' == 'm' ✓
// left=1, right=3: 'a' == 'a' ✓
// left=2, right=2: 停止
// 返回：true
// 方法三：递归法
// 时间复杂度：O(n)，空间复杂度：O(n)
public static boolean isPalindromeByRecursion(String str) {
if (str == null || str.length() <= 1) {
return true;
}
if (str.charAt(0) != str.charAt(str.length() - 1)) {
return false;
}
return isPalindromeByRecursion(str.substring(1, str.length() - 1));
}
// 📊 执行示例：
// 输入："aba"
// isPalindrome("aba") -> 'a' == 'a' ✓
// -> isPalindrome("b") -> true
// 返回：true
// 方法四：忽略大小写和非字母数字字符
// 时间复杂度：O(n)，空间复杂度：O(n)
public static boolean isPalindromeIgnoreCaseAndSymbols(String str) {
if (str == null || str.length() <= 1) {
return true;
}
// 只保留字母和数字，转小写
String cleaned = str.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
int left = 0, right = cleaned.length() - 1;
while (left < right) {
if (cleaned.charAt(left) != cleaned.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// 📊 执行示例：
// 输入："A man, a plan, a canal: Panama"
// cleaned = "amanaplanacanalpanama"
// 双指针比较：全部匹配
// 返回：true
public static void main(String[] args) {
String s1 = "madam";
String s2 = "hello";
String s3 = "A man, a plan, a canal: Panama";
System.out.println("\"" + s1 + "\" 是回文: " + isPalindromeByReverse(s1));
System.out.println("\"" + s2 + "\" 是回文: " + isPalindromeByTwoPointers(s2));
System.out.println("\"" + s3 + "\" 是回文: " + isPalindromeIgnoreCaseAndSymbols(s3));
}
}
---
b.Go实现
---
package main
import (
"fmt"
"strings"
"unicode"
)
// 方法一：反转字符串比较
func isPalindromeByReverse(s string) bool {
runes := []rune(s)
n := len(runes)
reversed := make([]rune, n)
for i := 0; i < n; i++ {
reversed[i] = runes[n-1-i]
}
return string(runes) == string(reversed)
}
// 方法二：双指针法（推荐）
func isPalindromeByTwoPointers(s string) bool {
runes := []rune(s)
left, right := 0, len(runes)-1
for left < right {
if runes[left] != runes[right] {
return false
}
left++
right--
}
return true
}
// 方法三：忽略大小写和非字母数字
func isPalindromeIgnoreCase(s string) bool {
// 清理字符串
var cleaned []rune
for _, c := range s {
if unicode.IsLetter(c) || unicode.IsDigit(c) {
cleaned = append(cleaned, unicode.ToLower(c))
}
}
// 双指针比较
left, right := 0, len(cleaned)-1
for left < right {
if cleaned[left] != cleaned[right] {
return false
}
left++
right--
}
return true
}
func main() {
s1 := "madam"
s2 := "hello"
s3 := "A man, a plan, a canal: Panama"
fmt.Printf("\"%s\" 是回文: %v\n", s1, isPalindromeByReverse(s1))
fmt.Printf("\"%s\" 是回文: %v\n", s2, isPalindromeByTwoPointers(s2))
fmt.Printf("\"%s\" 是回文: %v\n", s3, isPalindromeIgnoreCase(s3))
}
---
04.图解说明
📌 双指针判断过程（以"madam"为例）：
初始状态：
left right
↓ ↓
[m] [a] [d] [a] [m]
第1次比较：
'm' == 'm' ✓
left right
↓ ↓
[m] [a] [d] [a] [m]
第2次比较：
'a' == 'a' ✓
left right
↓ ↓
[m] [a] [d] [a] [m]
left >= right，停止
结论：是回文
📌 非回文示例（以"hello"为例）：
left right
↓ ↓
[h] [e] [l] [l] [o]
第1次比较：
'h' != 'o' ✗
立即返回false
05.常见错误与陷阱
⚠️ 常见错误：
1. 空字符串处理
错误：未检查null或空字符串
正确：空字符串和单字符都是回文
2. Unicode字符处理
错误：使用byte[]处理包含中文的字符串
正确：使用char[]（Java）或rune[]（Go）
示例："上海自来水来自海上" 是回文
3. 大小写敏感
错误："Aa"判断为非回文
正确：根据需求决定是否忽略大小写
4. 递归栈溢出
错误：对超长字符串使用递归
正确：使用迭代方法（双指针）
5. substring性能问题
错误：递归中频繁使用substring创建新字符串
正确：使用索引而不是substring
06.性能对比
方法 时间复杂度 空间复杂度 推荐度
反转比较 O(n) O(n) ⭐⭐⭐
双指针 O(n) O(1) ⭐⭐⭐⭐⭐
递归 O(n) O(n) ⭐⭐
忽略大小写 O(n) O(n) ⭐⭐⭐⭐
07.应用场景
a.数据验证
验证用户输入是否为回文（如身份证号、车牌号）。
b.字符串处理
文本分析、密码学中的回文检测。
c.算法题目
回文子串、最长回文子串等问题的基础。
d.面试题目
LeetCode 125: Valid Palindrome
LeetCode 680: Valid Palindrome II
2.6 字符串中的第一个唯一字符
01.问题描述
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回-1。
示例：
输入："leetcode" → 输出：0（字符'l'）
输入："loveleetcode" → 输出：2（字符'v'）
输入："aabb" → 输出：-1
02.解法分析
a.方法一：HashMap两次遍历（推荐）
思路：第一次遍历统计频率，第二次遍历找第一个频率为1的字符。
时间复杂度：O(n)，空间复杂度：O(k)，k为不同字符数
优点：思路清晰，适用于任何字符集
b.方法二：数组计数法
思路：使用固定大小数组统计，适用于小写字母。
时间复杂度：O(n)，空间复杂度：O(1)
优点：空间固定，效率最高
03.代码实现
a.Java实现
---
import java.util.*;
public class FirstUniqueChar {
// 方法一：使用HashMap（推荐）
public static int firstUniqCharHashMap(String s) {
Map<Character, Integer> count = new HashMap<>();
// 第一次遍历：统计每个字符出现次数
for (char c : s.toCharArray()) {
count.put(c, count.getOrDefault(c, 0) + 1);
}
// 第二次遍历：找第一个出现次数为1的字符
for (int i = 0; i < s.length(); i++) {
if (count.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
// 📊 执行示例：
// 输入："leetcode"
// 第一次遍历：{l=1, e=3, t=1, c=1, o=1, d=1}
// 第二次遍历：s[0]='l', count['l']=1，返回0
// 方法二：使用数组（仅适用于小写字母）
public static int firstUniqCharArray(String s) {
int[] count = new int[26];
// 统计每个字符出现次数
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
// 找第一个出现次数为1的字符
for (int i = 0; i < s.length(); i++) {
if (count[s.charAt(i) - 'a'] == 1) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(firstUniqCharHashMap("leetcode")); // 0
System.out.println(firstUniqCharArray("loveleetcode")); // 2
System.out.println(firstUniqCharHashMap("aabb")); // -1
}
}
---
b.Go实现
---
package main
import "fmt"
func firstUniqChar(s string) int {
count := make(map[rune]int)
// 统计频率
for _, c := range s {
count[c]++
}
// 找第一个唯一字符
for i, c := range s {
if count[c] == 1 {
return i
}
}
return -1
}
func main() {
fmt.Println(firstUniqChar("leetcode")) // 0
fmt.Println(firstUniqChar("loveleetcode")) // 2
fmt.Println(firstUniqChar("aabb")) // -1
}
---
04.图解说明
📌 处理过程（以"leetcode"为例）：
第一次遍历（统计频率）：
l → count = {l:1}
e → count = {l:1, e:1}
e → count = {l:1, e:2}
t → count = {l:1, e:2, t:1}
c → count = {l:1, e:2, t:1, c:1}
o → count = {l:1, e:2, t:1, c:1, o:1}
d → count = {l:1, e:2, t:1, c:1, o:1, d:1}
e → count = {l:1, e:3, t:1, c:1, o:1, d:1}
第二次遍历（查找）：
索引0: 'l', count['l']=1 ✓ 返回0
05.应用场景
LeetCode 387: First Unique Character in a String
2.7 验证字符串是否为有效括号
01.问题描述
给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合
2. 左括号必须以正确的顺序闭合
示例：
输入："()" → 输出：true
输入："()[]{}" → 输出：true
输入："(]" → 输出：false
输入："([)]" → 输出：false
输入："{[]}" → 输出：true
02.解法分析
a.栈方法（标准解法）
思路：遇到左括号入栈，遇到右括号检查栈顶是否匹配。
时间复杂度：O(n)，空间复杂度：O(n)
优点：思路清晰，易于理解
03.代码实现
a.Java实现
---
import java.util.*;
public class ValidParentheses {
// 方法一：使用栈
public static boolean isValidWithStack(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c); // 左括号入栈
} else {
if (stack.isEmpty()) {
return false; // 没有左括号匹配
}
char top = stack.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false; // 括号类型不匹配
}
}
}
return stack.isEmpty(); // 栈必须为空
}
// 📊 执行示例：
// 输入："({[]})"
// '(' → stack: ['(']
// '{' → stack: ['(', '{']
// '[' → stack: ['(', '{', '[']
// ']' → pop '[', 匹配 ✓, stack: ['(', '{']
// '}' → pop '{', 匹配 ✓, stack: ['(']
// ')' → pop '(', 匹配 ✓, stack: []
// 栈为空，返回true
// 方法二：使用HashMap优化
public static boolean isValidWithMap(String s) {
Stack<Character> stack = new Stack<>();
Map<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
for (char c : s.toCharArray()) {
if (map.containsKey(c)) { // 右括号
char top = stack.isEmpty() ? '#' : stack.pop();
if (top != map.get(c)) {
return false;
}
} else { // 左括号
stack.push(c);
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValidWithStack("()")); // true
System.out.println(isValidWithMap("()[]{}")); // true
System.out.println(isValidWithStack("(]")); // false
System.out.println(isValidWithMap("([)]")); // false
System.out.println(isValidWithStack("{[]}")); // true
}
}
---
b.Go实现
---
package main
import "fmt"
func isValid(s string) bool {
stack := []rune{}
pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
for _, c := range s {
if open, ok := pairs[c]; ok { // 右括号
if len(stack) == 0 || stack[len(stack)-1] != open {
return false
}
stack = stack[:len(stack)-1] // 出栈
} else { // 左括号
stack = append(stack, c) // 入栈
}
}
return len(stack) == 0
}
func main() {
fmt.Println(isValid("()")) // true
fmt.Println(isValid("()[]{}")) // true
fmt.Println(isValid("(]")) // false
fmt.Println(isValid("([)]")) // false
fmt.Println(isValid("{[]}")) // true
}
---
04.图解说明
📌 栈处理过程（以"{[]}"为例）：
初始：stack = []
'{' → 左括号，入栈
stack = ['{']
'[' → 左括号，入栈
stack = ['{', '[']
']' → 右括号，检查栈顶
栈顶='[', 匹配 ✓, 出栈
stack = ['{']
'}' → 右括号，检查栈顶
栈顶='{', 匹配 ✓, 出栈
stack = []
栈为空，返回true
05.常见错误
⚠️ 1. 忘记检查栈是否为空
⚠️ 2. 最后未检查栈是否为空（如"((("）
⚠️ 3. 括号类型匹配错误
06.应用场景
LeetCode 20: Valid Parentheses
2.8 判断两个字符串是否为字母异位词
01.问题描述
给定两个字符串s和t，判断它们是否是字母异位词。
字母异位词：两个字符串包含的字符相同，但排列顺序不同。
示例：
输入：s = "anagram", t = "nagaram" → 输出：true
输入：s = "rat", t = "car" → 输出：false
02.解法分析
a.方法一：排序法
思路：将两个字符串排序后比较是否相等。
时间复杂度：O(n log n)，空间复杂度：O(1)
优点：代码简洁
缺点：排序开销大
b.方法二：哈希表法
思路：统计每个字符出现次数，比较频率是否相同。
时间复杂度：O(n)，空间复杂度：O(k)
优点：效率高
c.方法三：数组计数法
思路：使用数组记录字符频率差异。
时间复杂度：O(n)，空间复杂度：O(1)
优点：空间固定，效率最高
03.代码实现
a.Java实现
---
import java.util.*;
public class Anagram {
// 方法一：排序法
public static boolean isAnagramBySorting(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
Arrays.sort(sChars);
Arrays.sort(tChars);
return Arrays.equals(sChars, tChars);
}
// 📊 执行示例：
// s = "anagram", t = "nagaram"
// 排序后：s = "aaagmnr", t = "aaagmnr"
// 相等，返回true
// 方法二：哈希表法
public static boolean isAnagramByHashMap(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
for (char c : t.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) - 1);
if (map.get(c) < 0) {
return false;
}
}
return true;
}
// 方法三：数组计数法（推荐，仅适用于小写字母）
public static boolean isAnagramByArray(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) {
return false;
}
}
return true;
}
// 📊 执行示例：
// s = "anagram", t = "nagaram"
// 同时遍历，s中字符+1，t中字符-1
// 最终count数组全为0，返回true
public static void main(String[] args) {
System.out.println(isAnagramBySorting("anagram", "nagaram")); // true
System.out.println(isAnagramByHashMap("rat", "car")); // false
System.out.println(isAnagramByArray("anagram", "nagaram")); // true
}
}
---
b.Go实现
---
package main
import (
"fmt"
"sort"
"strings"
)
// 方法一：排序法
func isAnagramBySorting(s, t string) bool {
if len(s) != len(t) {
return false
}
sRunes := []rune(s)
tRunes := []rune(t)
sort.Slice(sRunes, func(i, j int) bool { return sRunes[i] < sRunes[j] })
sort.Slice(tRunes, func(i, j int) bool { return tRunes[i] < tRunes[j] })
return string(sRunes) == string(tRunes)
}
// 方法二：数组计数法
func isAnagramByArray(s, t string) bool {
if len(s) != len(t) {
return false
}
var count [26]int
for i := 0; i < len(s); i++ {
count[s[i]-'a']++
count[t[i]-'a']--
}
for _, c := range count {
if c != 0 {
return false
}
}
return true
}
func main() {
fmt.Println(isAnagramBySorting("anagram", "nagaram")) // true
fmt.Println(isAnagramByArray("rat", "car")) // false
}
---
04.图解说明
📌 数组计数法过程（以"abc"和"bca"为例）：
初始：count = [0,0,0,...,0]（26个0）
同时遍历s和t：
i=0: s[0]='a', t[0]='b'
count[0]++, count[1]--
count = [1,-1,0,...,0]
i=1: s[1]='b', t[1]='c'
count[1]++, count[2]--
count = [1,0,-1,...,0]
i=2: s[2]='c', t[2]='a'
count[2]++, count[0]--
count = [0,0,0,...,0]
所有元素为0，返回true
05.性能对比
方法 时间复杂度 空间复杂度 推荐度
排序法 O(n log n) O(1) ⭐⭐⭐
哈希表 O(n) O(k) ⭐⭐⭐⭐
数组计数 O(n) O(1) ⭐⭐⭐⭐⭐
06.应用场景
LeetCode 242: Valid Anagram
LeetCode 49: Group Anagrams
3 八大排序算法
3.1 冒泡排序（Bubble Sort）
01.算法描述
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，
如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，
也就是说该数列已经排序完成。
核心思想：
- 比较相邻的元素，如果第一个比第二个大，就交换它们
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
- 这步做完后，最后的元素会是最大的数
- 针对所有的元素重复以上的步骤，除了最后一个
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
02.复杂度分析
a.时间复杂度
最好情况：O(n) - 数组已排序，优化版只需遍历一次
最坏情况：O(n²) - 数组完全逆序
平均情况：O(n²)
b.空间复杂度
O(1) - 原地排序，只需常数个辅助空间
c.稳定性
稳定排序 - 相等元素的相对位置不会改变
d.适用场景
✓ 小规模数据（n < 50）
✓ 基本有序的数据
✓ 教学演示
✗ 大规模数据（效率低）
02.Java代码
import java.util.Arrays;
public class BubbleSort {
// 方法一：基础冒泡排序
// 时间复杂度：O(n²)，空间复杂度：O(1)
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环：控制排序轮数，需要n-1轮
for (int i = 0; i < n - 1; i++) {
// 内层循环：每轮比较相邻元素
// n-1-i：因为每轮后最大的元素已经在末尾，无需再比较
for (int j = 0; j < n - 1 - i; j++) {
// 如果前一个元素大于后一个元素，交换它们
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 📊 执行示例：
// 输入：[5, 3, 8, 4, 2]
// 第1轮：[3, 5, 4, 2, 8] - 8冒泡到末尾
// 第2轮：[3, 4, 2, 5, 8] - 5冒泡到倒数第二
// 第3轮：[3, 2, 4, 5, 8] - 4冒泡到倒数第三
// 第4轮：[2, 3, 4, 5, 8] - 完成排序
// 方法二：优化版冒泡排序（提前终止）
// 时间复杂度：最好O(n)，最坏O(n²)，空间复杂度：O(1)
public static void bubbleSortOptimized(int[] arr) {
int n = arr.length;
boolean swapped; // 标记本轮是否发生交换
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; // 发生了交换
}
}
// 如果本轮没有交换，说明数组已经有序，提前终止
if (!swapped) {
System.out.println("第" + (i + 1) + "轮后已排序，提前终止");
break;
}
}
}
// 📊 执行示例：
// 输入：[2, 3, 5, 4, 8]（基本有序）
// 第1轮：[2, 3, 4, 5, 8] - swapped=true
// 第2轮：无交换 - swapped=false，提前终止
// 只需2轮而不是4轮！
public static void main(String[] args) {
int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
System.out.println("排序前: " + Arrays.toString(arr1));
bubbleSort(arr1);
System.out.println("排序后: " + Arrays.toString(arr1));
// 输出: 排序后: [11, 12, 22, 25, 34, 64, 90]
System.out.println("\n优化版示例：");
int[] arr2 = {2, 3, 5, 4, 8};
System.out.println("排序前: " + Arrays.toString(arr2));
bubbleSortOptimized(arr2);
System.out.println("排序后: " + Arrays.toString(arr2));
}
}
03.Go代码
package main
import "fmt"
// 方法一：基础冒泡排序
// 时间复杂度：O(n²)，空间复杂度：O(1)
func bubbleSort(arr []int) {
n := len(arr)
// 外层循环：控制排序轮数
for i := 0; i < n-1; i++ {
// 内层循环：每轮比较相邻元素
// n-1-i：每轮后最大元素已在末尾
for j := 0; j < n-1-i; j++ {
// 如果前一个元素大于后一个，交换
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
// 📊 执行示例：
// 输入：[5, 3, 8, 4, 2]
// 第1轮：[3, 5, 4, 2, 8]
// 第2轮：[3, 4, 2, 5, 8]
// 第3轮：[3, 2, 4, 5, 8]
// 第4轮：[2, 3, 4, 5, 8]
// 方法二：优化版冒泡排序（提前终止）
// 时间复杂度：最好O(n)，最坏O(n²)，空间复杂度：O(1)
func bubbleSortOptimized(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
swapped := false // 标记本轮是否交换
for j := 0; j < n-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = true
}
}
// 如果本轮没有交换，提前终止
if !swapped {
fmt.Printf("第%d轮后已排序，提前终止\n", i+1)
break
}
}
}
// 📊 执行示例：
// 输入：[2, 3, 5, 4, 8]
// 第1轮：[2, 3, 4, 5, 8] - swapped=true
// 第2轮：无交换 - 提前终止
func main() {
arr1 := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("排序前:", arr1)
bubbleSort(arr1)
fmt.Println("排序后:", arr1)
// 输出: 排序后: [11 12 22 25 34 64 90]
fmt.Println("\n优化版示例：")
arr2 := []int{2, 3, 5, 4, 8}
fmt.Println("排序前:", arr2)
bubbleSortOptimized(arr2)
fmt.Println("排序后:", arr2)
}
04.图解说明
📌 冒泡排序过程（以[5, 3, 8, 4, 2]为例）：
初始数组：[5, 3, 8, 4, 2]
第1轮（i=0）：将最大值冒泡到末尾
[5, 3, 8, 4, 2] 比较5和3，交换
[3, 5, 8, 4, 2] 比较5和8，不交换
[3, 5, 8, 4, 2] 比较8和4，交换
[3, 5, 4, 8, 2] 比较8和2，交换
[3, 5, 4, 2, 8] ← 8已就位
第2轮（i=1）：将次大值冒泡到倒数第二位
[3, 5, 4, 2, 8] 比较3和5，不交换
[3, 5, 4, 2, 8] 比较5和4，交换
[3, 4, 5, 2, 8] 比较5和2，交换
[3, 4, 2, 5, 8] ← 5已就位
第3轮（i=2）：
[3, 4, 2, 5, 8] 比较3和4，不交换
[3, 4, 2, 5, 8] 比较4和2，交换
[3, 2, 4, 5, 8] ← 4已就位
第4轮（i=3）：
[3, 2, 4, 5, 8] 比较3和2，交换
[2, 3, 4, 5, 8] ← 3已就位
排序完成：[2, 3, 4, 5, 8]
📌 优化版提前终止示例（数组已基本有序）：
初始：[2, 3, 5, 4, 8]
第1轮：
[2, 3, 5, 4, 8] → [2, 3, 4, 5, 8] swapped=true
第2轮：
[2, 3, 4, 5, 8] 遍历一遍，无交换 swapped=false
提前终止！总共只需2轮
05.执行示例
📊 详细执行过程：
输入：arr = [64, 34, 25, 12, 22]
第1轮（i=0）：
比较arr[0]和arr[1]: 64 > 34，交换 → [34, 64, 25, 12, 22]
比较arr[1]和arr[2]: 64 > 25，交换 → [34, 25, 64, 12, 22]
比较arr[2]和arr[3]: 64 > 12，交换 → [34, 25, 12, 64, 22]
比较arr[3]和arr[4]: 64 > 22，交换 → [34, 25, 12, 22, 64]
第2轮（i=1）：
比较arr[0]和arr[1]: 34 > 25，交换 → [25, 34, 12, 22, 64]
比较arr[1]和arr[2]: 34 > 12，交换 → [25, 12, 34, 22, 64]
比较arr[2]和arr[3]: 34 > 22，交换 → [25, 12, 22, 34, 64]
第3轮（i=2）：
比较arr[0]和arr[1]: 25 > 12，交换 → [12, 25, 22, 34, 64]
比较arr[1]和arr[2]: 25 > 22，交换 → [12, 22, 25, 34, 64]
第4轮（i=3）：
比较arr[0]和arr[1]: 12 < 22，不交换 → [12, 22, 25, 34, 64]
最终结果：[12, 22, 25, 34, 64]
06.常见错误与陷阱
⚠️ 常见错误：
1. 循环边界错误
错误：for (int j = 0; j < n; j++)
后果：数组越界（访问arr[j+1]时）
正确：for (int j = 0; j < n - 1 - i; j++)
2. 忘记优化
错误：即使数组已排序，仍继续所有轮次
优化：使用swapped标志提前终止
3. 交换逻辑错误
错误：arr[j] = arr[j+1]; arr[j+1] = arr[j];
后果：两个值都变成arr[j+1]
正确：使用临时变量或元组交换
4. 稳定性破坏
错误：使用 >= 比较（arr[j] >= arr[j+1]）
后果：破坏稳定性
正确：只使用 > 比较
07.性能优化技巧
a.提前终止
如果某轮没有发生交换，说明已排序，可以提前终止。
b.记录最后交换位置
记录最后一次交换的位置，下一轮只需遍历到该位置。
c.双向冒泡（鸡尾酒排序）
交替从两端向中间冒泡，可以稍微提高效率。
08.应用场景
a.教学用途
冒泡排序是最简单的排序算法，适合教学演示。
b.小规模数据
数据量很小时（n < 10），冒泡排序简单高效。
c.基本有序
数据基本有序时，优化版冒泡排序接近O(n)。
d.面试题目
理解冒泡排序的原理和优化是面试基础。
3.2 选择排序（Selection Sort）
01.说明
a.算法原理
每次从未排序部分选择最小元素
将其放到已排序部分的末尾
重复直到所有元素排序完成
b.时间复杂度
最好情况：O(n²)
最坏情况：O(n²)
平均情况：O(n²)
c.空间复杂度
O(1) - 原地排序
d.稳定性
不稳定排序
e.适用场景
小规模数据
交换次数要求少的场景
02.Java代码
import java.util.Arrays;
public class SelectionSort {
// 选择排序
// 时间复杂度：O(n²)，空间复杂度：O(1)
public static void selectionSort(int[] arr) {
int n = arr.length;
// 外层循环：控制已排序部分的边界
for (int i = 0; i < n - 1; i++) {
// 假设当前位置i就是最小值的位置
int minIndex = i;
// 内层循环：在未排序部分[i+1, n)中找最小值
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 更新最小值索引
}
}
// 将找到的最小值交换到已排序部分的末尾（位置i）
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
// 📊 执行示例：
// 输入：[64, 25, 12, 22, 11]
// 第1轮：找到最小值11(索引4)，与位置0交换 → [11, 25, 12, 22, 64]
// 第2轮：找到最小值12(索引2)，与位置1交换 → [11, 12, 25, 22, 64]
// 第3轮：找到最小值22(索引3)，与位置2交换 → [11, 12, 22, 25, 64]
// 第4轮：找到最小值25(索引3)，已在正确位置 → [11, 12, 22, 25, 64]
// 完成排序！
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("排序前: " + Arrays.toString(arr));
selectionSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
// 输出: 排序后: [11, 12, 22, 25, 64]
}
}
03.Go代码
package main
import "fmt"
// 选择排序
// 时间复杂度：O(n²)，空间复杂度：O(1)
func selectionSort(arr []int) {
n := len(arr)
// 外层循环：控制已排序部分的边界
for i := 0; i < n-1; i++ {
// 假设当前位置i就是最小值的位置
minIndex := i
// 内层循环：在未排序部分找最小值
for j := i + 1; j < n; j++ {
if arr[j] < arr[minIndex] {
minIndex = j // 更新最小值索引
}
}
// 将最小值交换到位置i
if minIndex != i {
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
}
}
// 📊 执行示例：
// 输入：[64, 25, 12, 22, 11]
// 第1轮：最小值11 → [11, 25, 12, 22, 64]
// 第2轮：最小值12 → [11, 12, 25, 22, 64]
// 第3轮：最小值22 → [11, 12, 22, 25, 64]
// 第4轮：最小值25 → [11, 12, 22, 25, 64]
func main() {
arr := []int{64, 25, 12, 22, 11}
fmt.Println("排序前:", arr)
selectionSort(arr)
fmt.Println("排序后:", arr)
// 输出: 排序后: [11 12 22 25 64]
}
04.图解说明
📌 选择排序过程（以[64, 25, 12, 22, 11]为例）：
初始：[64, 25, 12, 22, 11]
↑ i=0，找最小值
第1轮：找到最小值11（索引4），与位置0交换
[11, 25, 12, 22, 64]
✓ ↑ i=1，找最小值
第2轮：找到最小值12（索引2），与位置1交换
[11, 12, 25, 22, 64]
✓ ✓ ↑ i=2，找最小值
第3轮：找到最小值22（索引3），与位置2交换
[11, 12, 22, 25, 64]
✓ ✓ ✓ ↑ i=3，找最小值
第4轮：找到最小值25（索引3），已在正确位置
[11, 12, 22, 25, 64]
✓ ✓ ✓ ✓ ✓
排序完成！
特点：
- 交换次数最少：最多n-1次交换
- 比较次数固定：总是n(n-1)/2次比较
- 不稳定：如[5, 8, 5, 2]排序后变[2, 5, 8, 5]，两个5的顺序改变
05.应用场景
✓ 交换代价高的场景（如大对象排序）
✓ 小规模数据
✗ 需要稳定排序的场景
3.3 插入排序（Insertion Sort）
01.说明
a.算法原理
将数组分为已排序和未排序两部分
每次从未排序部分取一个元素插入到已排序部分的正确位置
类似于整理扑克牌
b.时间复杂度
最好情况：O(n) - 数组已排序
最坏情况：O(n²) - 数组逆序
平均情况：O(n²)
c.空间复杂度
O(1) - 原地排序
d.稳定性
稳定排序
e.适用场景
小规模数据
基本有序的数据
在线排序（边输入边排序）
02.Java代码
import java.util.Arrays;
public class InsertionSort {
// 插入排序
// 时间复杂度：最好O(n)，最坏O(n²)，空间复杂度：O(1)
public static void insertionSort(int[] arr) {
int n = arr.length;
// 从第2个元素开始（索引1），认为第1个元素已排序
for (int i = 1; i < n; i++) {
int key = arr[i]; // 当前要插入的元素
int j = i - 1; // 已排序部分的最后一个索引
// 将已排序部分中大于key的元素向后移动一位
// 为key腾出插入位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 元素后移
j--; // 继续向前比较
}
// 将key插入到正确位置（j+1）
arr[j + 1] = key;
}
}
// 📊 执行示例：
// 输入：[12, 11, 13, 5, 6]
// i=1, key=11: [12, 12, 13, 5, 6] → [11, 12, 13, 5, 6]
// i=2, key=13: 13≥12，无需移动 → [11, 12, 13, 5, 6]
// i=3, key=5: [11, 12, 13, 13, 6] → [11, 12, 12, 13, 6]
// → [11, 11, 12, 13, 6] → [5, 11, 12, 13, 6]
// i=4, key=6: [5, 11, 12, 13, 13] → [5, 11, 12, 12, 13]
// → [5, 11, 11, 12, 13] → [5, 6, 11, 12, 13]
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
System.out.println("排序前: " + Arrays.toString(arr));
insertionSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
// 输出: 排序后: [5, 6, 11, 12, 13]
}
}
03.Go代码
package main
import "fmt"
// 插入排序
// 时间复杂度：最好O(n)，最坏O(n²)，空间复杂度：O(1)
func insertionSort(arr []int) {
n := len(arr)
// 从第2个元素开始
for i := 1; i < n; i++ {
key := arr[i] // 当前要插入的元素
j := i - 1 // 已排序部分的最后索引
// 将大于key的元素向后移动
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j] // 元素后移
j-- // 继续向前
}
// 插入key到正确位置
arr[j+1] = key
}
}
// 📊 执行示例：
// 输入：[12, 11, 13, 5, 6]
// i=1, key=11: 插入到位置0 → [11, 12, 13, 5, 6]
// i=2, key=13: 已在正确位置 → [11, 12, 13, 5, 6]
// i=3, key=5: 插入到位置0 → [5, 11, 12, 13, 6]
// i=4, key=6: 插入到位置1 → [5, 6, 11, 12, 13]
func main() {
arr := []int{12, 11, 13, 5, 6}
fmt.Println("排序前:", arr)
insertionSort(arr)
fmt.Println("排序后:", arr)
// 输出: 排序后: [5 6 11 12 13]
}
04.图解说明
📌 插入排序过程（以[12, 11, 13, 5, 6]为例）：
初始：[12, 11, 13, 5, 6]
✓ ↑ key=11，插入到已排序部分
第1轮：将11插入到正确位置
[12, 12, 13, 5, 6] 12后移
[11, 12, 13, 5, 6] 11插入
✓ ✓ ↑ key=13
第2轮：13已在正确位置
[11, 12, 13, 5, 6]
✓ ✓ ✓ ↑ key=5
第3轮：将5插入到正确位置
[11, 12, 13, 13, 6] 13后移
[11, 12, 12, 13, 6] 12后移
[11, 11, 12, 13, 6] 11后移
[5, 11, 12, 13, 6] 5插入
✓ ✓ ✓ ✓ ↑ key=6
第4轮：将6插入到正确位置
[5, 11, 12, 13, 13] 13后移
[5, 11, 12, 12, 13] 12后移
[5, 11, 11, 12, 13] 11后移
[5, 6, 11, 12, 13] 6插入
排序完成！
类比：像整理扑克牌，每次拿一张牌插入到手中已排序的牌中
05.应用场景
✓ 小规模数据（n < 50）
✓ 基本有序的数据（接近O(n)）
✓ 在线排序（边输入边排序）
✓ 链表排序（不需要随机访问）
3.4 希尔排序（Shell Sort）
01.说明
a.算法原理
插入排序的改进版
通过设置间隔gap对数组进行分组
对每组进行插入排序，逐步缩小gap
b.时间复杂度
最好情况：O(n log n)
最坏情况：O(n²)
平均情况：O(n^1.3)
c.空间复杂度
O(1) - 原地排序
d.稳定性
不稳定排序
e.适用场景
中等规模数据
对插入排序的优化
02.Java代码
import java.util.Arrays;
public class ShellSort {
// 希尔排序
// 时间复杂度：O(n^1.3)，空间复杂度：O(1)
public static void shellSort(int[] arr) {
int n = arr.length;
// 外层循环：控制gap（间隔），从n/2开始，每次减半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个分组进行插入排序
// 从gap位置开始，对间隔为gap的元素进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i]; // 当前要插入的元素
int j = i;
// 在gap间隔内进行插入排序
// 将大于temp的元素向后移动gap个位置
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
// 插入temp到正确位置
arr[j] = temp;
}
}
}
// 📊 执行示例：
// 输入：[12, 34, 54, 2, 3]
// gap=2: 分组[12,54,3]和[34,2]，排序后 → [3, 2, 12, 34, 54]
// gap=1: 整体插入排序 → [2, 3, 12, 34, 54]
public static void main(String[] args) {
int[] arr = {12, 34, 54, 2, 3};
System.out.println("排序前: " + Arrays.toString(arr));
shellSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
// 输出: 排序后: [2, 3, 12, 34, 54]
}
}
03.Go代码
package main
import "fmt"
// 希尔排序
// 时间复杂度：O(n^1.3)，空间复杂度：O(1)
func shellSort(arr []int) {
n := len(arr)
// 外层循环：控制gap，从n/2开始递减
for gap := n / 2; gap > 0; gap /= 2 {
// 对每个分组进行插入排序
for i := gap; i < n; i++ {
temp := arr[i] // 当前要插入的元素
j := i
// 在gap间隔内进行插入排序
for j >= gap && arr[j-gap] > temp {
arr[j] = arr[j-gap] // 元素后移gap位
j -= gap
}
// 插入到正确位置
arr[j] = temp
}
}
}
// 📊 执行示例：
// 输入：[12, 34, 54, 2, 3]
// gap=2: [3, 2, 12, 34, 54]
// gap=1: [2, 3, 12, 34, 54]
func main() {
arr := []int{12, 34, 54, 2, 3}
fmt.Println("排序前:", arr)
shellSort(arr)
fmt.Println("排序后:", arr)
// 输出: 排序后: [2 3 12 34 54]
}
04.图解说明
📌 希尔排序过程（以[12, 34, 54, 2, 3]为例）：
初始：[12, 34, 54, 2, 3] n=5
gap=2（n/2）：将数组分为2组
组1：[12, 54, 3] 索引：0, 2, 4
组2：[34, 2] 索引：1, 3
对组1插入排序：
[12, 34, 54, 2, 3] → [3, 34, 12, 2, 54]
对组2插入排序：
[3, 34, 12, 2, 54] → [3, 2, 12, 34, 54]
gap=1（gap/2）：普通插入排序
[3, 2, 12, 34, 54]
↑ key=2，插入到正确位置
[2, 3, 12, 34, 54]
排序完成！
核心思想：
- 先用大gap进行粗调，让元素快速接近最终位置
- 逐步减小gap，进行细调
- 最后gap=1时，就是普通插入排序，但数组已基本有序
05.应用场景
✓ 中等规模数据（比插入排序快）
✓ 对插入排序的优化
✗ 需要稳定排序
3.5 堆排序（Heap Sort）
01.说明
a.算法原理
将数组构建成最大堆
将堆顶元素与末尾元素交换
重新调整堆，重复上述步骤
b.时间复杂度
最好情况：O(n log n)
最坏情况：O(n log n)
平均情况：O(n log n)
c.空间复杂度
O(1) - 原地排序
d.稳定性
不稳定排序
e.适用场景
需要稳定O(n log n)性能
内存受限环境
Top K问题
02.Java代码
import java.util.Arrays;
public class HeapSort {
// 堆排序
// 时间复杂度：O(n log n)，空间复杂度：O(1)
public static void heapSort(int[] arr) {
int n = arr.length;
// 步骤1：构建最大堆
// 从n/2-1开始向前遍历，调整每个非叶子节点
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 步骤2：一个个从堆中取出元素
for (int i = n - 1; i > 0; i--) {
// 将堆顶（最大值）与末尾元素交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重新调整剩余元素为最大堆
heapify(arr, i, 0);
}
}
// 📊 执行示例：
// 输入：[12, 11, 13, 5, 6, 7]
// 构建堆：[13, 11, 12, 5, 6, 7]
// 第1轮：交换13和7 → [7, 11, 12, 5, 6, 13] → 调整 → [12, 11, 7, 5, 6, 13]
// 第2轮：交换12和6 → [6, 11, 7, 5, 12, 13] → 调整 → [11, 6, 7, 5, 12, 13]
// ...最终：[5, 6, 7, 11, 12, 13]
// 调整堆：保证以i为根的子树是最大堆
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大值为根节点
int left = 2 * i + 1; // 左子节点索引
int right = 2 * i + 2; // 右子节点索引
// 如果左子节点存在且大于根节点
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点存在且大于当前最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点，交换并递归调整
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 递归调整受影响的子树
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("排序前: " + Arrays.toString(arr));
heapSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
// 输出: 排序后: [5, 6, 7, 11, 12, 13]
}
}
03.Go代码
package main
import "fmt"
// 堆排序
// 时间复杂度：O(n log n)，空间复杂度：O(1)
func heapSort(arr []int) {
n := len(arr)
// 步骤1：构建最大堆
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
// 步骤2：一个个从堆中取出元素
for i := n - 1; i > 0; i-- {
// 将堆顶（最大值）与末尾元素交换
arr[0], arr[i] = arr[i], arr[0]
// 重新调整剩余元素为最大堆
heapify(arr, i, 0)
}
}
// 📊 执行示例：
// 输入：[12, 11, 13, 5, 6, 7]
// 构建堆：[13, 11, 12, 5, 6, 7]
// 排序过程：逐步将最大值移到末尾
// 最终：[5, 6, 7, 11, 12, 13]
// 调整堆
func heapify(arr []int, n, i int) {
largest := i // 初始化最大值为根节点
left := 2*i + 1 // 左子节点
right := 2*i + 2 // 右子节点
// 如果左子节点大于根节点
if left < n && arr[left] > arr[largest] {
largest = left
}
// 如果右子节点大于当前最大值
if right < n && arr[right] > arr[largest] {
largest = right
}
// 如果最大值不是根节点，交换并递归调整
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
func main() {
arr := []int{12, 11, 13, 5, 6, 7}
fmt.Println("排序前:", arr)
heapSort(arr)
fmt.Println("排序后:", arr)
// 输出: 排序后: [5 6 7 11 12 13]
}
04.图解说明
📌 堆排序过程（以[4, 10, 3, 5, 1]为例）：
步骤1：构建最大堆
初始数组：[4, 10, 3, 5, 1]
数组表示的完全二叉树：
4
/ \
10 3
/ \
5 1
从最后一个非叶子节点开始调整（i = n/2-1 = 1）：
调整节点10（索引1）：
10的子节点：5(索引3), 1(索引4)
10 > 5 且 10 > 1，无需调整
调整节点4（索引0）：
4的子节点：10(索引1), 3(索引2)
10 > 4，交换
10
/ \
4 3
/ \
5 1
继续调整索引1的节点4：
4的子节点：5(索引3), 1(索引4)
5 > 4，交换
10
/ \
5 3
/ \
4 1
最大堆构建完成：[10, 5, 3, 4, 1]
步骤2：排序过程
第1轮：
交换堆顶10和末尾1：[1, 5, 3, 4, 10]
✓
调整堆（范围0-3）：
5
/ \
4 3
/
1
结果：[5, 4, 3, 1, 10]
第2轮：
交换堆顶5和末尾1：[1, 4, 3, 5, 10]
✓ ✓
调整堆（范围0-2）：
4
/ \
1 3
结果：[4, 1, 3, 5, 10]
第3轮：
交换堆顶4和末尾3：[3, 1, 4, 5, 10]
✓ ✓ ✓
调整堆（范围0-1）：
3
/
1
结果：[3, 1, 4, 5, 10]
第4轮：
交换堆顶3和末尾1：[1, 3, 4, 5, 10]
✓ ✓ ✓ ✓
排序完成：[1, 3, 4, 5, 10]
📌 堆的性质：
- 最大堆：父节点 ≥ 子节点
- 数组索引关系：
父节点i的左子节点：2*i + 1
父节点i的右子节点：2*i + 2
子节点i的父节点：(i-1) / 2
05.执行示例
📊 详细heapify过程（调整堆）：
输入：arr = [4, 10, 3, 5, 1], n = 5, i = 0
largest = 0 (初始假设根节点最大)
left = 2*0 + 1 = 1
right = 2*0 + 2 = 2
比较arr[1]=10 > arr[0]=4：largest = 1
比较arr[2]=3 < arr[1]=10：largest保持为1
largest != i，需要交换：
交换arr[0]和arr[1]：[10, 4, 3, 5, 1]
递归调整索引1：
largest = 1
left = 2*1 + 1 = 3
right = 2*1 + 2 = 4
比较arr[3]=5 > arr[1]=4：largest = 3
比较arr[4]=1 < arr[3]=5：largest保持为3
交换arr[1]和arr[3]：[10, 5, 3, 4, 1]
递归调整索引3：
left = 7 > 5，超出范围，停止
06.常见错误与陷阱
⚠️ 常见错误：
1. 索引计算错误
错误：左子节点 = 2*i（应该是2*i+1）
后果：访问错误的节点
2. 堆调整范围错误
错误：每次都调整整个数组
正确：排序时逐步缩小堆的范围
3. 构建堆的起始位置错误
错误：从索引0开始构建
正确：从n/2-1开始（最后一个非叶子节点）
4. 忘记递归调整
错误：交换后不继续向下调整
后果：破坏堆的性质
07.性能优化
a.原地排序
不需要额外数组，空间复杂度O(1)
b.时间复杂度稳定
无论什么情况都是O(n log n)
c.适合Top K问题
只需要维护k大小的堆
08.应用场景
✓ 需要稳定O(n log n)性能
✓ 内存受限环境（原地排序）
✓ Top K问题（最大/最小的K个元素）
✓ 优先队列实现
✗ 需要稳定排序（堆排序不稳定）
3.6 快速排序（Quick Sort）
01.说明
a.算法原理
选择基准元素pivot
将小于pivot的放左边，大于pivot的放右边
递归排序左右两部分
b.时间复杂度
最好情况：O(n log n)
最坏情况：O(n²)
平均情况：O(n log n)
c.空间复杂度
O(log n) - 递归栈
d.稳定性
不稳定排序
e.适用场景
大规模数据
平均性能要求高
02.Java代码
import java.util.Arrays;
public class QuickSort {
// 快速排序
// 时间复杂度：平均O(n log n)，最坏O(n²)，空间复杂度：O(log n)
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
// 分区，获取基准元素的最终位置
int pivotIndex = partition(arr, left, right);
// 递归排序左半部分
quickSort(arr, left, pivotIndex - 1);
// 递归排序右半部分
quickSort(arr, pivotIndex + 1, right);
}
}
// 📊 执行示例：
// 输入：[10, 7, 8, 9, 1, 5]
// 第1次分区（pivot=5）：[1, 5, 8, 9, 10, 7] → pivot在索引1
// 左部[1]：已排序
// 右部[8, 9, 10, 7]：继续分区...
// 最终：[1, 5, 7, 8, 9, 10]
// 分区函数：将数组分为小于pivot和大于pivot两部分
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 选择最右边的元素为基准
int i = left - 1; // i指向小于pivot的区域的最后一个元素
// 遍历数组，将小于等于pivot的元素移到左边
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
// 交换arr[i]和arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将pivot放到正确的位置（i+1）
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i + 1; // 返回pivot的最终位置
}
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));
// 输出: 排序后: [1, 5, 7, 8, 9, 10]
}
}
03.Go代码
package main
import "fmt"
// 快速排序
// 时间复杂度：平均O(n log n)，空间复杂度：O(log n)
func quickSort(arr []int, left, right int) {
if left < right {
// 分区并获取pivot位置
pivotIndex := partition(arr, left, right)
// 递归排序左右两部分
quickSort(arr, left, pivotIndex-1)
quickSort(arr, pivotIndex+1, right)
}
}
// 📊 执行示例：
// 输入：[10, 7, 8, 9, 1, 5]
// 分区（pivot=5）：[1, 5, 8, 9, 10, 7]
// 递归排序左右两部分
// 最终：[1, 5, 7, 8, 9, 10]
// 分区函数
func partition(arr []int, left, right int) int {
pivot := arr[right] // 选择最右元素为基准
i := left - 1 // 小于pivot区域的最后一个元素
// 将小于等于pivot的元素移到左边
for j := left; j < right; j++ {
if arr[j] <= pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
// 将pivot放到正确位置
arr[i+1], arr[right] = arr[right], arr[i+1]
return i + 1
}
func main() {
arr := []int{10, 7, 8, 9, 1, 5}
fmt.Println("排序前:", arr)
quickSort(arr, 0, len(arr)-1)
fmt.Println("排序后:", arr)
// 输出: 排序后: [1 5 7 8 9 10]
}
04.图解说明
📌 快速排序过程（以[10, 7, 8, 9, 1, 5]为例）：
初始：[10, 7, 8, 9, 1, 5]
选择pivot=5（最后一个元素）
第1次分区：
i=-1, pivot=5
遍历：10>5, 7>5, 8>5, 9>5, 1≤5
交换1和10：[1, 7, 8, 9, 10, 5]
i=0
将pivot放到正确位置：[1, 5, 8, 9, 10, 7]
↑ ↑ ↑
左边 pivot 右边
递归左边[1]：已排序
递归右边[8, 9, 10, 7]：
pivot=7
分区后：[7, 9, 10, 8]
递归左边：已排序
递归右边[9, 10, 8]：
pivot=8
分区后：[8, 10, 9]
...
最终：[1, 5, 7, 8, 9, 10]
分治思想：
- 分：选择pivot，将数组分为两部分
- 治：递归排序两部分
- 合：无需合并，已经有序
05.优化技巧
a.三数取中法：选择首、中、尾三个元素的中位数作为pivot
b.随机选择pivot：避免最坏情况
c.小数组用插入排序：当子数组很小时切换到插入排序
06.应用场景
✓ 大规模数据排序（最常用）
✓ 平均性能要求高
✓ 内存充足（需要递归栈）
✗ 需要稳定排序
3.7 归并排序（Merge Sort）
01.说明
a.算法原理
分治思想，将数组分成两半
递归排序两半
合并两个已排序的子数组
b.时间复杂度
最好情况：O(n log n)
最坏情况：O(n log n)
平均情况：O(n log n)
c.空间复杂度
O(n) - 需要额外数组
d.稳定性
稳定排序
e.适用场景
需要稳定排序
外部排序
链表排序
02.Java代码
import java.util.Arrays;
public class MergeSort {
// 归并排序
// 时间复杂度：O(n log n)，空间复杂度：O(n)
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// 找到中间点，分成两半
int mid = left + (right - left) / 2;
// 递归排序左半部分
mergeSort(arr, left, mid);
// 递归排序右半部分
mergeSort(arr, mid + 1, right);
// 合并两个已排序的子数组
merge(arr, left, mid, right);
}
}
// 📊 执行示例：
// 输入：[12, 11, 13, 5, 6, 7]
// 分解：[12,11,13] 和 [5,6,7]
// 继续分：[12,11] [13] 和 [5,6] [7]
// 合并：[11,12] [13] 和 [5,6] [7]
// 最终合并：[5, 6, 7, 11, 12, 13]
// 合并两个已排序的子数组
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1; // 左子数组长度
int n2 = right - mid; // 右子数组长度
// 创建临时数组
int[] L = new int[n1];
int[] R = new int[n2];
// 复制数据到临时数组
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
// 合并临时数组回原数组
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++]; // 选择较小的元素
} else {
arr[k++] = R[j++];
}
}
// 复制剩余元素
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("排序前: " + Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
System.out.println("排序后: " + Arrays.toString(arr));
// 输出: 排序后: [5, 6, 7, 11, 12, 13]
}
}
03.Go代码
package main
import "fmt"
func mergeSort(arr []int, left, right int) {
if left < right {
mid := left + (right-left)/2
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right)
}
}
func merge(arr []int, left, mid, right int) {
n1 := mid - left + 1
n2 := right - mid
L := make([]int, n1)
R := make([]int, n2)
for i := 0; i < n1; i++ {
L[i] = arr[left+i]
}
for j := 0; j < n2; j++ {
R[j] = arr[mid+1+j]
}
i, j, k := 0, 0, left
for i < n1 && j < n2 {
if L[i] <= R[j] {
arr[k] = L[i]
i++
} else {
arr[k] = R[j]
j++
}
k++
}
for i < n1 {
arr[k] = L[i]
i++
k++
}
for j < n2 {
arr[k] = R[j]
j++
k++
}
}
func main() {
arr := []int{12, 11, 13, 5, 6, 7}
fmt.Println("排序前:", arr)
mergeSort(arr, 0, len(arr)-1)
fmt.Println("排序后:", arr)
// 输出: 排序后: [5 6 7 11 12 13]
}
04.图解说明
📌 归并排序过程（以[38, 27, 43, 3, 9, 82, 10]为例）：
分治思想：分解 → 递归排序 → 合并
步骤1：分解（Divide）
[38, 27, 43, 3, 9, 82, 10]
↓ 分成两半
/ \
[38, 27, 43, 3] [9, 82, 10]
↓ ↓
/ \ / \
[38, 27] [43, 3] [9, 82] [10]
↓ ↓ ↓
/ \ / \ / \
[38][27] [43][3] [9][82]
步骤2：合并（Merge）
第1层合并（单个元素合并）：
[38]和[27]合并 → [27, 38]
[43]和[3]合并 → [3, 43]
[9]和[82]合并 → [9, 82]
[10]保持 → [10]
第2层合并：
[27, 38]和[3, 43]合并 → [3, 27, 38, 43]
[9, 82]和[10]合并 → [9, 10, 82]
第3层合并：
[3, 27, 38, 43]和[9, 10, 82]合并 → [3, 9, 10, 27, 38, 43, 82]
排序完成！
📌 详细合并过程（以[27, 38]和[3, 43]为例）：
L = [27, 38] R = [3, 43]
i=0, j=0, k=0
比较L[0]=27 vs R[0]=3：
3 < 27，arr[0] = 3，j++
[3, _, _, _]
比较L[0]=27 vs R[1]=43：
27 < 43，arr[1] = 27，i++
[3, 27, _, _]
比较L[1]=38 vs R[1]=43：
38 < 43，arr[2] = 38，i++
[3, 27, 38, _]
L数组已用完，复制R剩余元素：
arr[3] = 43
[3, 27, 38, 43]
05.执行示例
📊 完整执行过程：
输入：arr = [5, 2, 4, 1]
mergeSort(arr, 0, 3)：
mid = 0 + (3-0)/2 = 1
mergeSort(arr, 0, 1)：
mid = 0
mergeSort(arr, 0, 0)：返回（只有一个元素）
mergeSort(arr, 1, 1)：返回（只有一个元素）
merge(arr, 0, 0, 1)：
L=[5], R=[2]
合并后：[2, 5, 4, 1]
mergeSort(arr, 2, 3)：
mid = 2
mergeSort(arr, 2, 2)：返回
mergeSort(arr, 3, 3)：返回
merge(arr, 2, 2, 3)：
L=[4], R=[1]
合并后：[2, 5, 1, 4]
merge(arr, 0, 1, 3)：
L=[2, 5], R=[1, 4]
合并过程：
比较2 vs 1：1 < 2，arr[0]=1
比较2 vs 4：2 < 4，arr[1]=2
比较5 vs 4：4 < 5，arr[2]=4
L剩余5：arr[3]=5
最终：[1, 2, 4, 5]
06.常见错误与陷阱
⚠️ 常见错误：
1. mid计算溢出
错误：mid = (left + right) / 2
问题：left + right可能溢出
正确：mid = left + (right - left) / 2
2. 数组边界错误
错误：n1 = mid - left（少了1）
正确：n1 = mid - left + 1
3. 合并时索引错误
错误：忘记更新k索引
后果：覆盖错误的位置
4. 忘记复制剩余元素
错误：只处理了两个数组都有元素的情况
正确：必须复制L或R的剩余元素
5. 空间分配错误
错误：L和R数组大小计算错误
后果：数组越界
07.性能分析
a.时间复杂度
分解：O(log n)层
每层合并：O(n)
总时间：O(n log n)，所有情况都一样
b.空间复杂度
需要O(n)额外空间存储临时数组
递归栈空间：O(log n)
总空间：O(n)
c.稳定性
稳定排序（相等元素保持原有顺序）
关键：合并时使用<=而不是<
08.优化技巧
a.小数组优化
当子数组很小时（如n<10），切换到插入排序
b.原地归并
使用更复杂的算法减少空间使用
c.自然归并
利用数组中已有的有序序列
09.应用场景
✓ 需要稳定排序
✓ 外部排序（处理大文件，分块排序后合并）
✓ 链表排序（不需要随机访问）
✓ 并行排序（分治特性适合并行）
✗ 空间受限环境（需要O(n)额外空间）
3.8 基数排序（Radix Sort）
01.说明
a.算法原理
按位数分配，从低位到高位
每一位使用计数排序
适用于整数排序
b.时间复杂度
O(d * (n + k)) - d是位数，k是基数
c.空间复杂度
O(n + k)
d.稳定性
稳定排序
e.适用场景
整数排序
字符串排序
数据范围不大
02.Java代码
import java.util.Arrays;
public class RadixSort {
// 基数排序
// 时间复杂度：O(d*(n+k))，空间复杂度：O(n+k)
public static void radixSort(int[] arr) {
// 找到最大值，确定有多少位
int max = Arrays.stream(arr).max().getAsInt();
// 从个位开始，对每一位进行计数排序
// exp表示当前位：1(个位), 10(十位), 100(百位)...
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
// 📊 执行示例：
// 输入：[170, 45, 75, 90, 802, 24, 2, 66]
// 按个位排：[170, 90, 802, 2, 24, 45, 75, 66]
// 按十位排：[802, 2, 24, 45, 66, 170, 75, 90]
// 按百位排：[2, 24, 45, 66, 75, 90, 170, 802]
// 按指定位进行计数排序
private static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n]; // 输出数组
int[] count = new int[10]; // 0-9的计数数组
// 统计每个数字出现的次数
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// 计算累计次数（确定位置）
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 从后向前填充输出数组（保证稳定性）
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// 复制回原数组
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("排序前: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
// 输出: 排序后: [2, 24, 45, 66, 75, 90, 170, 802]
}
}
03.Go代码
package main
import "fmt"
func radixSort(arr []int) {
// 找到最大值
max := arr[0]
for _, v := range arr {
if v > max {
max = v
}
}
// 从个位开始，对每一位进行计数排序
for exp := 1; max/exp > 0; exp *= 10 {
countingSort(arr, exp)
}
}
func countingSort(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
// 统计每个数字出现的次数
for i := 0; i < n; i++ {
count[(arr[i]/exp)%10]++
}
// 计算累计次数
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
// 从后向前填充输出数组
for i := n - 1; i >= 0; i-- {
digit := (arr[i] / exp) % 10
output[count[digit]-1] = arr[i]
count[digit]--
}
// 复制回原数组
for i := 0; i < n; i++ {
arr[i] = output[i]
}
}
func main() {
arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
fmt.Println("排序前:", arr)
radixSort(arr)
fmt.Println("排序后:", arr)
// 输出: 排序后: [2 24 45 66 75 90 170 802]
}
04.图解说明
📌 基数排序过程（以[170, 45, 75, 90, 802, 24, 2, 66]为例）：
核心思想：从低位到高位，依次对每一位进行计数排序
初始数组：[170, 45, 75, 90, 802, 24, 2, 66]
最大值：802（3位数）
第1轮：按个位排序（exp=1）
个位数字：
170 → 0
45 → 5
75 → 5
90 → 0
802 → 2
24 → 4
2 → 2
66 → 6
按个位分桶：
桶0: [170, 90]
桶2: [802, 2]
桶4: [24]
桶5: [45, 75]
桶6: [66]
收集结果：[170, 90, 802, 2, 24, 45, 75, 66]
第2轮：按十位排序（exp=10）
十位数字：
170 → 7
90 → 9
802 → 0
2 → 0
24 → 2
45 → 4
75 → 7
66 → 6
按十位分桶：
桶0: [802, 2]
桶2: [24]
桶4: [45]
桶6: [66]
桶7: [170, 75]
桶9: [90]
收集结果：[802, 2, 24, 45, 66, 170, 75, 90]
第3轮：按百位排序（exp=100）
百位数字：
802 → 8
2 → 0
24 → 0
45 → 0
66 → 0
170 → 1
75 → 0
90 → 0
按百位分桶：
桶0: [2, 24, 45, 66, 75, 90]
桶1: [170]
桶8: [802]
收集结果：[2, 24, 45, 66, 75, 90, 170, 802]
排序完成！
05.执行示例
📊 详细计数排序过程（第1轮，exp=1）：
输入：arr = [170, 45, 75, 90, 802, 24, 2, 66]
步骤1：统计每个数字出现的次数
count数组初始化：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
遍历数组，统计个位数字：
170 % 10 = 0：count[0]++
45 % 10 = 5：count[5]++
75 % 10 = 5：count[5]++
90 % 10 = 0：count[0]++
802 % 10 = 2：count[2]++
24 % 10 = 4：count[4]++
2 % 10 = 2：count[2]++
66 % 10 = 6：count[6]++
count = [2, 0, 2, 0, 1, 2, 1, 0, 0, 0]
步骤2：计算累计次数（确定位置）
count[1] = count[1] + count[0] = 0 + 2 = 2
count[2] = count[2] + count[1] = 2 + 2 = 4
count[3] = count[3] + count[2] = 0 + 4 = 4
count[4] = count[4] + count[3] = 1 + 4 = 5
count[5] = count[5] + count[4] = 2 + 5 = 7
count[6] = count[6] + count[5] = 1 + 7 = 8
...
count = [2, 2, 4, 4, 5, 7, 8, 8, 8, 8]
步骤3：从后向前填充输出数组
66的个位是6，count[6]=8，放在output[7]，count[6]--
2的个位是2，count[2]=4，放在output[3]，count[2]--
24的个位是4，count[4]=5，放在output[4]，count[4]--
802的个位是2，count[2]=3，放在output[2]，count[2]--
90的个位是0，count[0]=2，放在output[1]，count[0]--
75的个位是5，count[5]=7，放在output[6]，count[5]--
45的个位是5，count[5]=6，放在output[5]，count[5]--
170的个位是0，count[0]=1，放在output[0]，count[0]--
output = [170, 90, 802, 2, 24, 45, 75, 66]
06.常见错误与陷阱
⚠️ 常见错误：
1. 只适用于非负整数
错误：直接对负数使用基数排序
正确：需要特殊处理负数（分开排序或偏移）
2. 基数选择错误
错误：总是使用10作为基数
优化：可以使用2、16等其他基数
3. 位数计算错误
错误：未正确计算最大值的位数
后果：排序不完整
4. 稳定性破坏
错误：从前向后填充输出数组
正确：必须从后向前填充以保持稳定性
5. 溢出问题
错误：处理超大整数时exp溢出
正确：使用long或特殊处理
07.性能分析
a.时间复杂度
d：最大数的位数
n：数组长度
k：基数（通常是10）
每轮计数排序：O(n + k)
总共d轮：O(d * (n + k))
当d是常数时：O(n)
当d很大时：可能不如O(n log n)的算法
b.空间复杂度
O(n + k)
output数组：O(n)
count数组：O(k)
c.稳定性
稳定排序（从后向前填充保证稳定性）
08.优化技巧
a.基数选择
使用更大的基数（如256）可以减少轮数
但会增加空间消耗
b.负数处理
方法1：分别排序正负数，再合并
方法2：所有数加上偏移量，变为非负数
c.混合排序
当数据范围很大时，切换到快速排序
09.应用场景
✓ 整数排序（数据范围不大）
✓ 字符串排序（按字典序）
✓ 日期排序（年月日分别排序）
✓ IP地址排序
✗ 浮点数排序
✗ 数据范围很大（位数d很大）
10.与其他排序算法对比
算法 时间复杂度 空间复杂度 稳定性 适用场景
基数排序 O(d*(n+k)) O(n+k) 稳定 整数、字符串
快速排序 O(n log n) O(log n) 不稳定 通用
归并排序 O(n log n) O(n) 稳定 通用
计数排序 O(n+k) O(k) 稳定 范围小的整数
4 十大经典算法
4.1 快速排序（Quick Sort）
01.说明
a.算法原理
选择一个基准元素（pivot），将数组分为两部分
左边部分的元素都小于基准，右边部分的元素都大于基准
递归地对左右两部分进行快速排序
b.时间复杂度
最好情况：O(n log n) - 每次都平分数组
最坏情况：O(n²) - 数组已排序或逆序
平均情况：O(n log n)
c.空间复杂度
O(log n) - 递归调用栈的深度
d.稳定性
不稳定排序
e.适用场景
大规模数据排序
平均性能要求高的场景
不要求稳定性的排序
02.Java代码
import java.util.Arrays;
public class QuickSort {
// 快速排序
// 时间复杂度：平均O(n log n)，最坏O(n²)，空间复杂度：O(log n)
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
// 分区，获取基准元素的最终位置
int pivotIndex = partition(arr, left, right);
// 递归排序左右两部分
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
// 📊 执行示例：
// 输入：[64, 34, 25, 12, 22, 11, 90]
// 分区（pivot=90）：[64, 34, 25, 12, 22, 11, 90]
// 递归排序左右部分...
// 最终：[11, 12, 22, 25, 34, 64, 90]
// 分区函数：将数组分为小于pivot和大于pivot两部分
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 选择最右元素为基准
int i = left - 1; // i指向小于pivot区域的最后一个元素
// 将小于等于pivot的元素移到左边
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
// 将pivot放到正确位置
swap(arr, i + 1, right);
return i + 1; // 返回pivot的最终位置
}
// 交换数组中的两个元素
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("排序前: " + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后: " + Arrays.toString(arr));
// 输出: 排序后: [11, 12, 22, 25, 34, 64, 90]
}
}
03.Go代码
package main
import "fmt"
// 快速排序主方法
func quickSort(arr []int, left, right int) {
if left < right {
// 获取分区点
pivotIndex := partition(arr, left, right)
// 递归排序左右两部分
quickSort(arr, left, pivotIndex-1)
quickSort(arr, pivotIndex+1, right)
}
}
// 分区方法
func partition(arr []int, left, right int) int {
// 选择最右边的元素作为基准
pivot := arr[right]
i := left - 1
// 遍历数组，将小于基准的元素移到左边
for j := left; j < right; j++ {
if arr[j] <= pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
// 将基准元素放到正确位置
arr[i+1], arr[right] = arr[right], arr[i+1]
return i + 1
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("排序前:", arr)
quickSort(arr, 0, len(arr)-1)
fmt.Println("排序后:", arr)
// 输出: 排序后: [11 12 22 25 34 64 90]
}
04.图解说明
📌 快速排序过程（以[10, 7, 8, 9, 1, 5]为例）：
初始：[10, 7, 8, 9, 1, 5]
选择pivot=5（最后一个元素）
第1次分区：
i=-1, pivot=5
遍历：10>5, 7>5, 8>5, 9>5, 1≤5
交换1和10：[1, 7, 8, 9, 10, 5]
i=0
将pivot放到正确位置：[1, 5, 8, 9, 10, 7]
↑ ↑ ↑
左边 pivot 右边
递归左边[1]：已排序
递归右边[8, 9, 10, 7]：
pivot=7
分区后：[7, 9, 10, 8]
递归左边：已排序
递归右边[9, 10, 8]：
pivot=8
分区后：[8, 10, 9]
...
最终：[1, 5, 7, 8, 9, 10]
分治思想：
- 分：选择pivot，将数组分为两部分
- 治：递归排序两部分
- 合：无需合并，已经有序
05.优化技巧
a.三数取中法
选择首、中、尾三个元素的中位数作为pivot
避免最坏情况
b.随机选择pivot
随机选择pivot，避免最坏情况
c.小数组用插入排序
当子数组很小时（如n<10），切换到插入排序
06.应用场景
✓ 大规模数据排序（最常用）
✓ 平均性能要求高
✓ 内存充足（需要递归栈）
✗ 需要稳定排序
LeetCode题目：
- 215. Kth Largest Element in an Array
- 912. Sort an Array
4.2 堆排序（Heap Sort）
01.说明
a.算法原理
将数组构建成最大堆（或最小堆）
将堆顶元素（最大值）与末尾元素交换
重新调整堆，重复上述步骤
b.时间复杂度
最好情况：O(n log n)
最坏情况：O(n log n)
平均情况：O(n log n)
c.空间复杂度
O(1) - 原地排序
d.稳定性
不稳定排序
e.适用场景
需要稳定O(n log n)性能的场景
内存受限的环境
Top K问题
02.Java代码
import java.util.Arrays;
public class HeapSort {
// 堆排序
// 时间复杂度：O(n log n)，空间复杂度：O(1)
public static void heapSort(int[] arr) {
int n = arr.length;
// 步骤1：构建最大堆
// 从n/2-1开始向前遍历，调整每个非叶子节点
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 步骤2：一个个从堆中取出元素
for (int i = n - 1; i > 0; i--) {
// 将堆顶（最大值）与末尾元素交换
swap(arr, 0, i);
// 重新调整剩余元素为最大堆
heapify(arr, i, 0);
}
}
// 📊 执行示例：
// 输入：[12, 11, 13, 5, 6, 7]
// 构建堆：[13, 11, 12, 5, 6, 7]
// 排序过程：逐步将最大值移到末尾
// 最终：[5, 6, 7, 11, 12, 13]
// 调整堆：保证以i为根的子树是最大堆
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大值为根节点
int left = 2 * i + 1; // 左子节点索引
int right = 2 * i + 2; // 右子节点索引
// 如果左子节点存在且大于根节点
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点存在且大于当前最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点，交换并递归调整
if (largest != i) {
swap(arr, i, largest);
// 递归调整受影响的子树
heapify(arr, n, largest);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("排序前: " + Arrays.toString(arr));
heapSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
// 输出: 排序后: [5, 6, 7, 11, 12, 13]
}
}
03.Go代码
package main
import "fmt"
// 堆排序主方法
func heapSort(arr []int) {
n := len(arr)
// 构建最大堆
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
// 一个个从堆中取出元素
for i := n - 1; i > 0; i-- {
// 将当前最大值移到数组末尾
arr[0], arr[i] = arr[i], arr[0]
// 重新调整堆
heapify(arr, i, 0)
}
}
// 调整堆
func heapify(arr []int, n, i int) {
largest := i // 初始化最大值为根节点
left := 2*i + 1 // 左子节点
right := 2*i + 2 // 右子节点
// 如果左子节点大于根节点
if left < n && arr[left] > arr[largest] {
largest = left
}
// 如果右子节点大于当前最大值
if right < n && arr[right] > arr[largest] {
largest = right
}
// 如果最大值不是根节点
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
// 递归调整受影响的子树
heapify(arr, n, largest)
}
}
func main() {
arr := []int{12, 11, 13, 5, 6, 7}
fmt.Println("排序前:", arr)
heapSort(arr)
fmt.Println("排序后:", arr)
// 输出: 排序后: [5 6 7 11 12 13]
}
04.图解说明
📌 堆排序过程（以[4, 10, 3, 5, 1]为例）：
步骤1：构建最大堆
初始数组：[4, 10, 3, 5, 1]
数组表示的完全二叉树：
4
/ \
10 3
/ \
5 1
从最后一个非叶子节点开始调整（i = n/2-1 = 1）：
调整节点10（索引1）：
10的子节点：5(索引3), 1(索引4)
10 > 5 且 10 > 1，无需调整
调整节点4（索引0）：
4的子节点：10(索引1), 3(索引2)
10 > 4，交换
10
/ \
4 3
/ \
5 1
继续调整索引1的节点4：
4的子节点：5(索引3), 1(索引4)
5 > 4，交换
10
/ \
5 3
/ \
4 1
最大堆构建完成：[10, 5, 3, 4, 1]
步骤2：排序过程
第1轮：交换堆顶10和末尾1 → [1, 5, 3, 4, 10]
调整堆 → [5, 4, 3, 1, 10]
第2轮：交换堆顶5和末尾1 → [1, 4, 3, 5, 10]
调整堆 → [4, 1, 3, 5, 10]
第3轮：交换堆顶4和末尾3 → [3, 1, 4, 5, 10]
第4轮：交换堆顶3和末尾1 → [1, 3, 4, 5, 10]
排序完成：[1, 3, 4, 5, 10]
05.应用场景
✓ 需要稳定O(n log n)性能
✓ 内存受限环境（原地排序）
✓ Top K问题（最大/最小的K个元素）
✓ 优先队列实现
✗ 需要稳定排序（堆排序不稳定）
4.3 归并排序（Merge Sort）
01.说明
a.算法原理
采用分治思想，将数组分成两半
递归地对两半分别排序
合并两个已排序的子数组
b.时间复杂度
最好情况：O(n log n)
最坏情况：O(n log n)
平均情况：O(n log n)
c.空间复杂度
O(n) - 需要额外的临时数组
d.稳定性
稳定排序
e.适用场景
需要稳定排序的场景
外部排序（大文件排序）
链表排序
02.Java代码
import java.util.Arrays;
public class MergeSort {
// 归并排序
// 时间复杂度：O(n log n)，空间复杂度：O(n)
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// 找到中间点，分成两半
int mid = left + (right - left) / 2;
// 递归排序左半部分
mergeSort(arr, left, mid);
// 递归排序右半部分
mergeSort(arr, mid + 1, right);
// 合并两个已排序的子数组
merge(arr, left, mid, right);
}
}
// 📊 执行示例：
// 输入：[38, 27, 43, 3, 9, 82, 10]
// 分解：[38,27,43,3] 和 [9,82,10]
// 继续分解并合并...
// 最终：[3, 9, 10, 27, 38, 43, 82]
// 合并两个已排序的子数组
private static void merge(int[] arr, int left, int mid, int right) {
// 计算两个子数组的大小
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
int[] L = new int[n1];
int[] R = new int[n2];
// 复制数据到临时数组
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
// 合并临时数组
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
System.out.println("排序前: " + Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
System.out.println("排序后: " + Arrays.toString(arr));
// 输出: 排序后: [3, 9, 10, 27, 38, 43, 82]
}
}
03.Go代码
package main
import "fmt"
// 归并排序主方法
func mergeSort(arr []int, left, right int) {
if left < right {
// 找到中间点
mid := left + (right-left)/2
// 递归排序左半部分
mergeSort(arr, left, mid)
// 递归排序右半部分
mergeSort(arr, mid+1, right)
// 合并两个已排序的部分
merge(arr, left, mid, right)
}
}
// 合并两个已排序的子数组
func merge(arr []int, left, mid, right int) {
// 计算两个子数组的大小
n1 := mid - left + 1
n2 := right - mid
// 创建临时数组
L := make([]int, n1)
R := make([]int, n2)
// 复制数据到临时数组
for i := 0; i < n1; i++ {
L[i] = arr[left+i]
}
for j := 0; j < n2; j++ {
R[j] = arr[mid+1+j]
}
// 合并临时数组
i, j, k := 0, 0, left
for i < n1 && j < n2 {
if L[i] <= R[j] {
arr[k] = L[i]
i++
} else {
arr[k] = R[j]
j++
}
k++
}
// 复制剩余元素
for i < n1 {
arr[k] = L[i]
i++
k++
}
for j < n2 {
arr[k] = R[j]
j++
k++
}
}
func main() {
arr := []int{38, 27, 43, 3, 9, 82, 10}
fmt.Println("排序前:", arr)
mergeSort(arr, 0, len(arr)-1)
fmt.Println("排序后:", arr)
// 输出: 排序后: [3 9 10 27 38 43 82]
}
04.图解说明
📌 归并排序过程（以[38, 27, 43, 3, 9, 82, 10]为例）：
分治思想：分解 → 递归排序 → 合并
步骤1：分解（Divide）
[38, 27, 43, 3, 9, 82, 10]
↓ 分成两半
/ \
[38, 27, 43, 3] [9, 82, 10]
↓ ↓
/ \ / \
[38, 27] [43, 3] [9, 82] [10]
↓ ↓ ↓
/ \ / \ / \
[38][27] [43][3] [9][82]
步骤2：合并（Merge）
第1层合并（单个元素合并）：
[38]和[27]合并 → [27, 38]
[43]和[3]合并 → [3, 43]
[9]和[82]合并 → [9, 82]
[10]保持 → [10]
第2层合并：
[27, 38]和[3, 43]合并 → [3, 27, 38, 43]
[9, 82]和[10]合并 → [9, 10, 82]
第3层合并：
[3, 27, 38, 43]和[9, 10, 82]合并 → [3, 9, 10, 27, 38, 43, 82]
排序完成！
05.应用场景
✓ 需要稳定排序
✓ 外部排序（处理大文件，分块排序后合并）
✓ 链表排序（不需要随机访问）
✓ 并行排序（分治特性适合并行）
✗ 空间受限环境（需要O(n)额外空间）
4.4 二分查找（Binary Search）
01.说明
a.算法原理
在有序数组中查找目标值
每次比较中间元素，缩小搜索范围
时间复杂度远优于线性查找
b.时间复杂度
最好情况：O(1) - 目标值在中间
最坏情况：O(log n)
平均情况：O(log n)
c.空间复杂度
O(1) - 迭代实现
O(log n) - 递归实现
d.前提条件
数组必须是有序的
e.适用场景
有序数组的查找
查找边界值
旋转数组的查找
02.Java代码
public class BinarySearch {
// 方法一：迭代实现
// 时间复杂度：O(log n)，空间复杂度：O(1)
public static int binarySearch(int[] arr, int target) {
int left = 0; // 左边界
int right = arr.length - 1; // 右边界
while (left <= right) {
// 计算中间位置，防止溢出
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // 找到目标值，返回索引
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右半部分
} else {
right = mid - 1; // 目标在左半部分
}
}
return -1; // 未找到，返回-1
}
// 📊 执行示例：
// 输入：arr=[2, 3, 4, 10, 40, 50, 60], target=10
// 第1次：left=0, right=6, mid=3, arr[3]=10 == 10 ✓
// 返回：3
// 方法二：递归实现
// 时间复杂度：O(log n)，空间复杂度：O(log n)
public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
if (left > right) {
return -1; // 基本情况：未找到
}
int mid = left + (right - left) / 2;
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);
}
}
// 📊 执行示例：
// 输入：arr=[2, 3, 4, 10, 40], target=40
// 递归过程：[0,4] → [3,4] → 找到arr[4]=40
// 返回：4
public static void main(String[] args) {
int[] arr = {2, 3, 4, 10, 40, 50, 60};
int target = 10;
// 迭代实现
int result1 = binarySearch(arr, target);
if (result1 != -1) {
System.out.println("迭代: 元素 " + target + " 在索引 " + result1);
} else {
System.out.println("迭代: 元素未找到");
}
// 递归实现
int result2 = binarySearchRecursive(arr, target, 0, arr.length - 1);
if (result2 != -1) {
System.out.println("递归: 元素 " + target + " 在索引 " + result2);
} else {
System.out.println("递归: 元素未找到");
}
// 输出: 迭代: 元素 10 在索引 3
// 输出: 递归: 元素 10 在索引 3
}
}
03.Go代码
package main
import "fmt"
// 迭代实现
func binarySearch(arr []int, target int) int {
left, right := 0, len(arr)-1
for left <= right {
mid := left + (right-left)/2
if arr[mid] == target {
return mid // 找到目标值
} else if arr[mid] < target {
left = mid + 1 // 在右半部分查找
} else {
right = mid - 1 // 在左半部分查找
}
}
return -1 // 未找到
}
// 递归实现
func binarySearchRecursive(arr []int, target, left, right int) int {
if left > right {
return -1 // 未找到
}
mid := left + (right-left)/2
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)
}
}
func main() {
arr := []int{2, 3, 4, 10, 40, 50, 60}
target := 10
// 迭代实现
result1 := binarySearch(arr, target)
if result1 != -1 {
fmt.Printf("迭代: 元素 %d 在索引 %d\n", target, result1)
} else {
fmt.Println("迭代: 元素未找到")
}
// 递归实现
result2 := binarySearchRecursive(arr, target, 0, len(arr)-1)
if result2 != -1 {
fmt.Printf("递归: 元素 %d 在索引 %d\n", target, result2)
} else {
fmt.Println("递归: 元素未找到")
}
// 输出: 迭代: 元素 10 在索引 3
// 输出: 递归: 元素 10 在索引 3
}
04.图解说明
📌 二分查找过程（查找10，数组[2, 3, 4, 10, 40, 50, 60]）：
初始状态：
索引: 0 1 2 3 4 5 6
数组: [2, 3, 4, 10, 40, 50, 60]
↑ ↑ ↑
left mid right
第1次比较：
left=0, right=6, mid=3
arr[3]=10 == target=10 ✓
找到目标！返回索引3
📌 未找到的情况（查找25）：
第1次：
[2, 3, 4, 10, 40, 50, 60]
↑ ↑ ↑
left mid right
arr[3]=10 < 25，在右半部分查找
第2次：
[2, 3, 4, 10, 40, 50, 60]
↑ ↑ ↑
left mid right
arr[5]=50 > 25，在左半部分查找
第3次：
[2, 3, 4, 10, 40, 50, 60]
↑
left/mid/right
arr[4]=40 > 25，在左半部分查找
第4次：
left=4, right=3
left > right，未找到，返回-1
05.执行示例
📊 详细查找过程（查找40）：
输入：arr = [2, 3, 4, 10, 40, 50, 60], target = 40
第1轮：
left=0, right=6
mid = 0 + (6-0)/2 = 3
arr[3]=10 < 40
更新：left = mid + 1 = 4
第2轮：
left=4, right=6
mid = 4 + (6-4)/2 = 5
arr[5]=50 > 40
更新：right = mid - 1 = 4
第3轮：
left=4, right=4
mid = 4 + (4-4)/2 = 4
arr[4]=40 == 40 ✓
返回：4
06.常见错误与陷阱
⚠️ 常见错误：
1. mid计算溢出
错误：mid = (left + right) / 2
问题：left + right可能溢出
正确：mid = left + (right - left) / 2
2. 边界条件错误
错误：while (left < right)
问题：可能漏掉最后一个元素
正确：while (left <= right)
3. 更新边界错误
错误：left = mid 或 right = mid
问题：可能导致死循环
正确：left = mid + 1 或 right = mid - 1
4. 数组未排序
错误：对未排序数组使用二分查找
后果：结果不正确
正确：先排序或使用线性查找
5. 返回值理解错误
错误：认为返回-1表示数组为空
正确：返回-1表示未找到目标值
07.变体问题
a.查找第一个等于目标值的位置
当arr[mid] == target时，继续在左半部分查找
b.查找最后一个等于目标值的位置
当arr[mid] == target时，继续在右半部分查找
c.查找第一个大于等于目标值的位置
lower_bound问题
d.查找最后一个小于等于目标值的位置
upper_bound问题
08.性能分析
时间复杂度：O(log n)
- 每次查找范围减半
- 最多查找log₂n次
空间复杂度：
- 迭代：O(1)
- 递归：O(log n)（递归栈）
对比线性查找：
- 线性查找：O(n)
- 二分查找：O(log n)
- 当n=1000时，线性最多1000次，二分最多10次
09.应用场景
✓ 有序数组的查找
✓ 查找插入位置
✓ 旋转数组的查找
✓ 查找峰值元素
✓ 搜索二维矩阵
✓ 求平方根（二分答案）
✗ 无序数组（需要先排序）
LeetCode题目：
- 704. Binary Search
- 35. Search Insert Position
- 33. Search in Rotated Sorted Array
- 69. Sqrt(x)
4.5 广度优先搜索（BFS）
01.说明
a.算法原理
从起始节点开始，逐层遍历图或树
使用队列存储待访问的节点
先访问的节点，其邻居节点先被访问
b.时间复杂度
O(V + E) - V是顶点数，E是边数
c.空间复杂度
O(V) - 队列最多存储所有顶点
d.特点
可以找到最短路径（无权图）
层序遍历
e.适用场景
最短路径问题
层序遍历
连通性判断
02.Java代码
import java.util.*;
public class BFS {
// 广度优先搜索（BFS）
// 时间复杂度：O(V+E)，空间复杂度：O(V)
public static void bfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>(); // 记录已访问节点
Queue<Integer> queue = new LinkedList<>(); // 队列（FIFO）
// 从起始节点开始
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll(); // 出队
System.out.print(node + " ");
// 访问所有邻居节点
if (graph.containsKey(node)) {
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor); // 标记为已访问
queue.offer(neighbor); // 入队
}
}
}
}
}
// 📊 执行示例：
// 图：0-1, 0-2, 1-2, 2-3
// 从BFS(2)：queue=[2] → [0,3] → [3,1] → [1]
// 输出：2 0 3 1
// 二叉树的层序遍历
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
public static void main(String[] args) {
// 图的BFS示例
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(0, Arrays.asList(1, 2));
graph.put(1, Arrays.asList(2));
graph.put(2, Arrays.asList(0, 3));
graph.put(3, Arrays.asList(3));
System.out.print("BFS遍历: ");
bfs(graph, 2);
// 输出: BFS遍历: 2 0 3 1
}
}
03.Go代码
package main
import "fmt"
// 图的BFS遍历
func bfs(graph map[int][]int, start int) {
visited := make(map[int]bool)
queue := []int{start}
visited[start] = true
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
fmt.Print(node, " ")
// 访问所有邻居节点
if neighbors, ok := graph[node]; ok {
for _, neighbor := range neighbors {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
}
}
// 二叉树节点
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// 二叉树的层序遍历
func levelOrder(root *TreeNode) [][]int {
result := [][]int{}
if root == nil {
return result
}
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
level := []int{}
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
}
return result
}
func main() {
// 图的BFS示例
graph := map[int][]int{
0: {1, 2},
1: {2},
2: {0, 3},
3: {3},
}
fmt.Print("BFS遍历: ")
bfs(graph, 2)
// 输出: BFS遍历: 2 0 3 1
}
04.图解说明
📌 BFS遍历过程（图遍历，从节点2开始）：
图结构：
0 ← → 2
↓ ↓
1 → → 3 ↺
初始状态：
queue = [2]
visited = {2}
第1步：出队节点2
访问：2
邻居：0, 3（未访问）
queue = [0, 3]
visited = {2, 0, 3}
第2步：出队节点0
访问：0
邻居：1（未访问），2（已访问）
queue = [3, 1]
visited = {2, 0, 3, 1}
第3步：出队节点3
访问：3
邻居：3（已访问）
queue = [1]
visited = {2, 0, 3, 1}
第4步：出队节点1
访问：1
邻居：2（已访问）
queue = []
遍历完成：2 → 0 → 3 → 1
📌 二叉树层序遍历：
树结构：
3
/ \
9 20
/ \
15 7
第1层：queue = [3]
输出：[3]
加入子节点：queue = [9, 20]
第2层：queue = [9, 20]
输出：[9, 20]
加入子节点：queue = [15, 7]
第3层：queue = [15, 7]
输出：[15, 7]
结果：[[3], [9, 20], [15, 7]]
05.核心特点
a.使用队列（FIFO）
先进先出，保证按层遍历
b.逐层访问
同一层的节点在队列中连续
c.最短路径
在无权图中，BFS找到的路径是最短的
d.完全性
一定能找到解（如果存在）
06.应用场景
✓ 最短路径问题（无权图）
✓ 层序遍历（二叉树）
✓ 连通性判断
✓ 拓扑排序
✓ 迷宫求解
✓ 社交网络（好友推荐）
LeetCode题目：
- 102. Binary Tree Level Order Traversal
- 107. Binary Tree Level Order Traversal II
- 111. Minimum Depth of Binary Tree
- 127. Word Ladder
- 200. Number of Islands
4.6 深度优先搜索（DFS）
01.说明
a.算法原理
从起始节点开始，沿着一条路径深入到底
回溯到上一个节点，继续探索其他路径
使用栈（或递归）实现
b.时间复杂度
O(V + E) - V是顶点数，E是边数
c.空间复杂度
O(V) - 递归栈或显式栈的深度
d.特点
可以检测环
拓扑排序
路径查找
e.适用场景
路径搜索
连通性判断
拓扑排序
回溯问题
02.Java代码
import java.util.*;
public class DFS {
// 深度优先搜索（DFS）- 递归实现
// 时间复杂度：O(V+E)，空间复杂度：O(V)
public static void dfsRecursive(Map<Integer, List<Integer>> graph,
int node, Set<Integer> visited) {
visited.add(node); // 标记为已访问
System.out.print(node + " ");
// 递归访问所有未访问的邻居
if (graph.containsKey(node)) {
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
dfsRecursive(graph, neighbor, visited); // 递归
}
}
}
}
// 📊 执行示例：
// 图：0-1, 0-2, 1-2, 2-3
// DFS(2)：2 → 0 → 1 → 3
// 输出：2 0 1 3
// 图的DFS遍历（迭代）
public static void dfsIterative(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited.contains(node)) {
visited.add(node);
System.out.print(node + " ");
if (graph.containsKey(node)) {
// 逆序入栈，保证访问顺序
List<Integer> neighbors = graph.get(node);
for (int i = neighbors.size() - 1; i >= 0; i--) {
if (!visited.contains(neighbors.get(i))) {
stack.push(neighbors.get(i));
}
}
}
}
}
}
// 二叉树的前序遍历（DFS）
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public static void preorder(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " ");
preorder(root.left);
preorder(root.right);
}
public static void main(String[] args) {
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(0, Arrays.asList(1, 2));
graph.put(1, Arrays.asList(2));
graph.put(2, Arrays.asList(0, 3));
graph.put(3, Arrays.asList(3));
System.out.print("DFS递归: ");
dfsRecursive(graph, 2, new HashSet<>());
System.out.println();
System.out.print("DFS迭代: ");
dfsIterative(graph, 2);
// 输出: DFS递归: 2 0 1 3
// 输出: DFS迭代: 2 0 1 3
}
}
03.Go代码
package main
import "fmt"
// 图的DFS遍历（递归）
func dfsRecursive(graph map[int][]int, node int, visited map[int]bool) {
visited[node] = true
fmt.Print(node, " ")
if neighbors, ok := graph[node]; ok {
for _, neighbor := range neighbors {
if !visited[neighbor] {
dfsRecursive(graph, neighbor, visited)
}
}
}
}
// 图的DFS遍历（迭代）
func dfsIterative(graph map[int][]int, start int) {
visited := make(map[int]bool)
stack := []int{start}
for len(stack) > 0 {
// 弹出栈顶元素
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if !visited[node] {
visited[node] = true
fmt.Print(node, " ")
if neighbors, ok := graph[node]; ok {
// 逆序入栈
for i := len(neighbors) - 1; i >= 0; i-- {
if !visited[neighbors[i]] {
stack = append(stack, neighbors[i])
}
}
}
}
}
}
// 二叉树节点
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// 二叉树的前序遍历（DFS）
func preorder(root *TreeNode) {
if root == nil {
return
}
fmt.Print(root.Val, " ")
preorder(root.Left)
preorder(root.Right)
}
func main() {
graph := map[int][]int{
0: {1, 2},
1: {2},
2: {0, 3},
3: {3},
}
fmt.Print("DFS递归: ")
visited := make(map[int]bool)
dfsRecursive(graph, 2, visited)
fmt.Println()
fmt.Print("DFS迭代: ")
dfsIterative(graph, 2)
// 输出: DFS递归: 2 0 1 3
// 输出: DFS迭代: 2 0 1 3
}
04.图解说明
📌 DFS遍历过程（从节点2开始）：
图结构：
0 ← → 2
↓ ↓
1 → → 3 ↺
递归DFS过程：
访问2 → visited={2}
├─访问0 → visited={2,0}
│ └─访问1 → visited={2,0,1}
└─访问3 → visited={2,0,1,3}
遍历顺序：2 → 0 → 1 → 3
📌 二叉树DFS（前序遍历）：
树结构：
1
/ \
2 3
/ \
4 5
访问顺序：
1（根）→ 2（左子树）→ 4 → 5 → 3（右子树）
递归过程：
preorder(1)
├─访问1
├─preorder(2)
│ ├─访问2
│ ├─preorder(4) → 访问4
│ └─preorder(5) → 访问5
└─preorder(3) → 访问3
05.DFS vs BFS对比
特性 DFS BFS
数据结构 栈（递归/显式） 队列
遍历方式 深度优先 广度优先
路径 不一定最短 最短路径
空间复杂度 O(h)树高 O(w)树宽
应用 路径搜索、拓扑排序 最短路径
06.应用场景
✓ 路径搜索（迷宫）
✓ 拓扑排序
✓ 检测环
✓ 连通分量
✓ 回溯问题
✓ 树的遍历（前/中/后序）
LeetCode题目：
- 94/144/145. Binary Tree Traversal
- 200. Number of Islands
- 207. Course Schedule
- 547. Number of Provinces
4.7 动态规划（Dynamic Programming）
01.说明
a.算法原理
将复杂问题分解为子问题
保存子问题的解，避免重复计算
自底向上或自顶向下求解
b.时间复杂度
通常为O(n²)或O(n³)，取决于状态数和转移
c.空间复杂度
O(n)或O(n²)，可以通过滚动数组优化
d.核心要素
最优子结构
重叠子问题
状态转移方程
e.适用场景
最优化问题
计数问题
存在性问题
02.Java代码
import java.util.Arrays;
public class DynamicProgramming {
// 方法一：斐波那契数列（记忆化搜索）
// 时间复杂度：O(n)，空间复杂度：O(n)
public static int fibMemo(int n, int[] memo) {
if (n <= 1) return n; // 基本情况
if (memo[n] != -1) return memo[n]; // 已计算过，直接返回
// 计算并保存结果
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// 📊 执行示例：
// fib(5): 5 → 4+3 → (3+2)+(2+1) → ...
// 结果：5
// 方法二：斐波那契数列（动态规划）
// 时间复杂度：O(n)，空间复杂度：O(n)
public static int fibDP(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1]; // dp[i]表示第i个斐波那契数
dp[0] = 0; // 初始状态
dp[1] = 1;
// 状态转移：dp[i] = dp[i-1] + dp[i-2]
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 📊 执行示例：
// n=5: dp=[0,1,1,2,3,5]
// 返回：dp[5]=5
// 0-1背包问题
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
// 选择或不选择当前物品
dp[i][w] = Math.max(
dp[i - 1][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
// 最长公共子序列
public static int lcs(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
// 斐波那契数列
int n = 10;
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
System.out.println("Fib(10) 记忆化: " + fibMemo(n, memo));
System.out.println("Fib(10) DP: " + fibDP(n));
// 0-1背包
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 8;
System.out.println("背包最大价值: " + knapsack(weights, values, capacity));
// 最长公共子序列
String text1 = "abcde";
String text2 = "ace";
System.out.println("LCS长度: " + lcs(text1, text2));
// 输出: Fib(10) 记忆化: 55
// 输出: Fib(10) DP: 55
// 输出: 背包最大价值: 10
// 输出: LCS长度: 3
}
}
03.Go代码
package main
import "fmt"
// 斐波那契数列（记忆化搜索）
func fibMemo(n int, memo []int) int {
if n <= 1 {
return n
}
if memo[n] != -1 {
return memo[n]
}
memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
return memo[n]
}
// 斐波那契数列（动态规划）
func fibDP(n int) int {
if n <= 1 {
return n
}
dp := make([]int, n+1)
dp[0] = 0
dp[1] = 1
for i := 2; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
// 0-1背包问题
func knapsack(weights, values []int, capacity int) int {
n := len(weights)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, capacity+1)
}
for i := 1; i <= n; i++ {
for w := 1; w <= capacity; w++ {
if weights[i-1] <= w {
// 选择或不选择当前物品
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w-weights[i-1]]+values[i-1],
)
} else {
dp[i][w] = dp[i-1][w]
}
}
}
return dp[n][capacity]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// 最长公共子序列
func lcs(text1, text2 string) int {
m, n := len(text1), len(text2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if text1[i-1] == text2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[m][n]
}
func main() {
// 斐波那契数列
n := 10
memo := make([]int, n+1)
for i := range memo {
memo[i] = -1
}
fmt.Println("Fib(10) 记忆化:", fibMemo(n, memo))
fmt.Println("Fib(10) DP:", fibDP(n))
// 0-1背包
weights := []int{2, 3, 4, 5}
values := []int{3, 4, 5, 6}
capacity := 8
fmt.Println("背包最大价值:", knapsack(weights, values, capacity))
// 最长公共子序列
text1 := "abcde"
text2 := "ace"
fmt.Println("LCS长度:", lcs(text1, text2))
// 输出: Fib(10) 记忆化: 55
// 输出: Fib(10) DP: 55
// 输出: 背包最大价值: 10
// 输出: LCS长度: 3
}
04.图解说明
📌 斐波那契数列DP过程（n=5）：
状态定义：dp[i] = 第i个斐波那契数
状态转移：dp[i] = dp[i-1] + dp[i-2]
i: 0 1 2 3 4 5
dp: [ 0, 1, 1, 2, 3, 5 ]
↑ ↑
└──┴─→ dp[2] = 0+1 = 1
↑ ↑
└──┴─→ dp[3] = 1+1 = 2
↑ ↑
└──┴─→ dp[4] = 1+2 = 3
↑ ↑
└──┴─→ dp[5] = 2+3 = 5
📌 0-1背包问题（容量=5，物品=[重量2价值3, 重量3价值4, 重量4价值5]）：
dp[i][w] = 前i个物品，容量为w时的最大价值
容量w: 0 1 2 3 4 5
物品0: [0, 0, 0, 0, 0, 0]
物品1: [0, 0, 3, 3, 3, 3] 重2价3
物品2: [0, 0, 3, 4, 4, 7] 重3价4
物品3: [0, 0, 3, 4, 5, 7] 重4价5
最优解：dp[3][5] = 7（选物品1和2）
05.核心思想
a.最优子结构
问题的最优解包含子问题的最优解
b.重叠子问题
子问题会被多次计算，需要保存结果
c.状态转移方程
当前状态由之前的状态推导而来
d.两种实现方式
- 自顶向下（记忆化搜索）
- 自底向上（动态规划）
06.经典问题
✓ 斐波那契数列
✓ 爬楼梯
✓ 0-1背包
✓ 完全背包
✓ 最长公共子序列（LCS）
✓ 最长递增子序列（LIS）
✓ 编辑距离
✓ 股票买卖
LeetCode题目：
- 70. Climbing Stairs
- 322. Coin Change
- 300. Longest Increasing Subsequence
- 1143. Longest Common Subsequence
4.8 贪心算法（Greedy Algorithm）
01.说明
a.算法原理
每一步都选择当前最优解
不回溯，不考虑全局
希望通过局部最优达到全局最优
b.时间复杂度
通常为O(n log n)，取决于排序
c.空间复杂度
O(1)或O(n)
d.适用条件
贪心选择性质
最优子结构
e.适用场景
活动选择问题
霍夫曼编码
最小生成树
区间调度
02.Java代码
import java.util.*;
public class GreedyAlgorithm {
// 活动选择问题（区间调度）
static class Activity {
int start, end;
Activity(int start, int end) {
this.start = start;
this.end = end;
}
}
// 活动选择问题（贪心算法）
// 时间复杂度：O(n log n)，空间复杂度：O(1)
public static int activitySelection(Activity[] activities) {
// 按结束时间排序（贪心选择）
Arrays.sort(activities, (a, b) -> a.end - b.end);
int count = 1; // 至少选择第一个活动
int lastEnd = activities[0].end; // 记录上一个活动的结束时间
// 遍历所有活动
for (int i = 1; i < activities.length; i++) {
// 如果当前活动的开始时间≥上一个活动的结束时间
if (activities[i].start >= lastEnd) {
count++; // 选择该活动
lastEnd = activities[i].end; // 更新结束时间
}
}
return count;
}
// 📊 执行示例：
// 活动：[1,3],[2,5],[4,6],[6,7],[5,8],[8,9]
// 排序后选择：[1,3],[4,6],[6,7],[8,9]
// 返回：4
// 零钱兑换（贪心，仅适用于特定币值）
public static int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
int count = 0;
// 从大到小使用硬币
for (int i = coins.length - 1; i >= 0; i--) {
while (amount >= coins[i]) {
amount -= coins[i];
count++;
}
}
return amount == 0 ? count : -1;
}
// 跳跃游戏II（最少跳跃次数）
public static int jump(int[] nums) {
int jumps = 0;
int currentEnd = 0;
int farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
public static void main(String[] args) {
// 活动选择
Activity[] activities = {
new Activity(1, 3),
new Activity(2, 5),
new Activity(4, 6),
new Activity(6, 7),
new Activity(5, 8),
new Activity(8, 9)
};
System.out.println("最多活动数: " + activitySelection(activities));
// 零钱兑换
int[] coins = {1, 5, 10, 25};
int amount = 41;
System.out.println("最少硬币数: " + coinChange(coins, amount));
// 跳跃游戏
int[] nums = {2, 3, 1, 1, 4};
System.out.println("最少跳跃次数: " + jump(nums));
// 输出: 最多活动数: 4
// 输出: 最少硬币数: 4
// 输出: 最少跳跃次数: 2
}
}
03.Go代码
package main
import (
"fmt"
"sort"
)
// 活动选择问题
type Activity struct {
start, end int
}
func activitySelection(activities []Activity) int {
// 按结束时间排序
sort.Slice(activities, func(i, j int) bool {
return activities[i].end < activities[j].end
})
count := 1
lastEnd := activities[0].end
for i := 1; i < len(activities); i++ {
if activities[i].start >= lastEnd {
count++
lastEnd = activities[i].end
}
}
return count
}
// 零钱兑换（贪心）
func coinChange(coins []int, amount int) int {
sort.Ints(coins)
count := 0
// 从大到小使用硬币
for i := len(coins) - 1; i >= 0; i-- {
for amount >= coins[i] {
amount -= coins[i]
count++
}
}
if amount == 0 {
return count
}
return -1
}
// 跳跃游戏II
func jump(nums []int) int {
jumps := 0
currentEnd := 0
farthest := 0
for i := 0; i < len(nums)-1; i++ {
if i+nums[i] > farthest {
farthest = i + nums[i]
}
if i == currentEnd {
jumps++
currentEnd = farthest
}
}
return jumps
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
// 活动选择
activities := []Activity{
{1, 3},
{2, 5},
{4, 6},
{6, 7},
{5, 8},
{8, 9},
}
fmt.Println("最多活动数:", activitySelection(activities))
// 零钱兑换
coins := []int{1, 5, 10, 25}
amount := 41
fmt.Println("最少硬币数:", coinChange(coins, amount))
// 跳跃游戏
nums := []int{2, 3, 1, 1, 4}
fmt.Println("最少跳跃次数:", jump(nums))
// 输出: 最多活动数: 4
// 输出: 最少硬币数: 4
// 输出: 最少跳跃次数: 2
}
04.图解说明
📌 活动选择问题：
活动列表（按结束时间排序）：
A: [1, 3]
B: [2, 5]
C: [4, 6]
D: [6, 7]
E: [5, 8]
F: [8, 9]
贪心选择：
1. 选A [1,3] ✓ lastEnd=3
2. B[2,5] 开始2<3 × 跳过
3. 选C [4,6] ✓ lastEnd=6
4. 选D [6,7] ✓ lastEnd=7
5. E[5,8] 开始5<7 × 跳过
6. 选F [8,9] ✓ lastEnd=9
结果：选择A, C, D, F，共4个活动
05.贪心 vs 动态规划
特性 贪心算法 动态规划
决策 局部最优 全局最优
回溯 不回溯 保存子问题解
时间复杂度 通常较低 通常较高
适用性 需证明贪心性质 更通用
06.应用场景
✓ 活动选择问题
✓ 霍夫曼编码
✓ 最小生成树（Prim/Kruskal）
✓ 跳跃游戏
✓ 分配问题
LeetCode题目：
- 55. Jump Game
- 45. Jump Game II
- 435. Non-overlapping Intervals
- 452. Minimum Number of Arrows
4.9 回溯算法（Backtracking）
01.说明
a.算法原理
通过深度优先搜索尝试所有可能的解
遇到不满足条件的解时回退
剪枝优化，避免无效搜索
b.时间复杂度
通常为指数级O(2^n)或O(n!)
c.空间复杂度
O(n) - 递归栈的深度
d.核心思想
选择、探索、撤销
剪枝优化
e.适用场景
组合问题
排列问题
子集问题
棋盘问题
02.Java代码
import java.util.*;
public class Backtracking {
// 全排列
// 全排列（回溯算法）
// 时间复杂度：O(n!)，空间复杂度：O(n)
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>(); // 当前路径
boolean[] used = new boolean[nums.length]; // 标记元素是否已使用
backtrackPermute(nums, path, used, result);
return result;
}
private static void backtrackPermute(int[] nums, List<Integer> path,
boolean[] used, List<List<Integer>> result) {
// 结束条件：路径长度等于数组长度
if (path.size() == nums.length) {
result.add(new ArrayList<>(path)); // 找到一个排列
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // 剪枝：已使用的元素跳过
// 选择
path.add(nums[i]);
used[i] = true;
// 探索
backtrackPermute(nums, path, used, result);
// 撤销（回溯）
path.remove(path.size() - 1);
used[i] = false;
}
}
// 📊 执行示例：
// 输入：[1,2,3]
// 回溯树：[] → [1] → [1,2] → [1,2,3] ✓
// 结果：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// N皇后问题
public static List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(board[i], '.');
}
backtrackQueens(board, 0, result);
return result;
}
private static void backtrackQueens(char[][] board, int row,
List<List<String>> result) {
if (row == board.length) {
result.add(construct(board));
return;
}
for (int col = 0; col < board.length; col++) {
if (!isValid(board, row, col)) continue;
board[row][col] = 'Q';
backtrackQueens(board, row + 1, result);
board[row][col] = '.';
}
}
private static boolean isValid(char[][] board, int row, int col) {
int n = board.length;
// 检查列
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') return false;
}
// 检查左上对角线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
// 检查右上对角线
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true;
}
private static List<String> construct(char[][] board) {
List<String> res = new ArrayList<>();
for (char[] row : board) {
res.add(new String(row));
}
return res;
}
public static void main(String[] args) {
// 全排列
int[] nums = {1, 2, 3};
System.out.println("全排列: " + permute(nums));
// N皇后
int n = 4;
List<List<String>> queens = solveNQueens(n);
System.out.println("4皇后解法数: " + queens.size());
// 输出: 全排列: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
// 输出: 4皇后解法数: 2
}
}
03.Go代码
package main
import "fmt"
// 全排列
func permute(nums []int) [][]int {
result := [][]int{}
path := []int{}
used := make([]bool, len(nums))
backtrackPermute(nums, path, used, &result)
return result
}
func backtrackPermute(nums []int, path []int, used []bool, result *[][]int) {
if len(path) == len(nums) {
temp := make([]int, len(path))
copy(temp, path)
*result = append(*result, temp)
return
}
for i := 0; i < len(nums); i++ {
if used[i] {
continue
}
// 选择
path = append(path, nums[i])
used[i] = true
// 探索
backtrackPermute(nums, path, used, result)
// 撤销
path = path[:len(path)-1]
used[i] = false
}
}
// N皇后问题
func solveNQueens(n int) [][]string {
result := [][]string{}
board := make([][]byte, n)
for i := range board {
board[i] = make([]byte, n)
for j := range board[i] {
board[i][j] = '.'
}
}
backtrackQueens(board, 0, &result)
return result
}
func backtrackQueens(board [][]byte, row int, result *[][]string) {
if row == len(board) {
*result = append(*result, construct(board))
return
}
for col := 0; col < len(board); col++ {
if !isValid(board, row, col) {
continue
}
board[row][col] = 'Q'
backtrackQueens(board, row+1, result)
board[row][col] = '.'
}
}
func isValid(board [][]byte, row, col int) bool {
n := len(board)
// 检查列
for i := 0; i < row; i++ {
if board[i][col] == 'Q' {
return false
}
}
// 检查左上对角线
for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
if board[i][j] == 'Q' {
return false
}
}
// 检查右上对角线
for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
if board[i][j] == 'Q' {
return false
}
}
return true
}
func construct(board [][]byte) []string {
res := []string{}
for _, row := range board {
res = append(res, string(row))
}
return res
}
func main() {
// 全排列
nums := []int{1, 2, 3}
fmt.Println("全排列:", permute(nums))
// N皇后
n := 4
queens := solveNQueens(n)
fmt.Println("4皇后解法数:", len(queens))
// 输出: 全排列: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
// 输出: 4皇后解法数: 2
}
04.图解说明
📌 全排列回溯过程（[1,2,3]）：
回溯树：
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2][1,3] [2,1][2,3] [3,1][3,2]
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
执行过程：
1. 选择1 → path=[1]
选择2 → path=[1,2]
选择3 → path=[1,2,3] ✓ 找到一个解
撤鈀3 → path=[1,2]
撤鈀2 → path=[1]
选择3 → path=[1,3]
选择2 → path=[1,3,2] ✓
...
05.核心模板
void backtrack(path, choices) {
if (满足结束条件) {
result.add(path)
return
}
for (choice in choices) {
if (不合法) continue // 剪枝
// 选择
path.add(choice)
// 探索
backtrack(path, new_choices)
// 撤销
path.remove(choice)
}
}
06.应用场景
✓ 全排列/组合/子集
✓ N皇后问题
✓ 数独求解
✓ 迷宫问题
✓ 括号生成
LeetCode题目：
- 46. Permutations
- 51. N-Queens
- 78. Subsets
- 22. Generate Parentheses
4.10 分治算法（Divide and Conquer）
01.说明
a.算法原理
将问题分解为若干个规模较小的子问题
递归求解子问题
合并子问题的解得到原问题的解
b.时间复杂度
通常为O(n log n)
c.空间复杂度
O(log n) - 递归栈深度
d.三个步骤
分解（Divide）
解决（Conquer）
合并（Combine）
e.适用场景
归并排序
快速排序
二分查找
大整数乘法
02.Java代码
import java.util.Arrays;
public class DivideAndConquer {
// 归并排序（分治算法）
// 时间复杂度：O(n log n)，空间复杂度：O(n)
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 步骤1：分解（Divide）
mergeSort(arr, left, mid); // 递归排序左半部分
mergeSort(arr, mid + 1, right); // 递归排序右半部分
// 步骤3：合并（Combine）
merge(arr, left, mid, right);
}
}
// 📊 执行示例：
// 输入：[38, 27, 43, 3]
// 分解：[38,27] [43,3] → [38][27] [43][3]
// 合并：[27,38] [3,43] → [3,27,38,43]
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
// 最大子数组和（分治）
public static int maxSubArray(int[] nums) {
return maxSubArrayHelper(nums, 0, nums.length - 1);
}
private static int maxSubArrayHelper(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = left + (right - left) / 2;
// 分解
int leftMax = maxSubArrayHelper(nums, left, mid);
int rightMax = maxSubArrayHelper(nums, mid + 1, right);
// 跨越中点的最大子数组
int crossMax = maxCrossingSum(nums, left, mid, right);
// 合并
return Math.max(Math.max(leftMax, rightMax), crossMax);
}
private static int maxCrossingSum(int[] nums, int left, int mid, int right) {
int sum = 0;
int leftSum = Integer.MIN_VALUE;
for (int i = mid; i >= left; i--) {
sum += nums[i];
leftSum = Math.max(leftSum, sum);
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
rightSum = Math.max(rightSum, sum);
}
return leftSum + rightSum;
}
// 快速幂（分治）
public static long quickPow(long base, int exp) {
if (exp == 0) return 1;
if (exp == 1) return base;
// 分解
long half = quickPow(base, exp / 2);
// 合并
if (exp % 2 == 0) {
return half * half;
} else {
return half * half * base;
}
}
public static void main(String[] args) {
// 归并排序
int[] arr = {38, 27, 43, 3, 9, 82, 10};
System.out.println("排序前: " + Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
System.out.println("排序后: " + Arrays.toString(arr));
// 最大子数组和
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println("最大子数组和: " + maxSubArray(nums));
// 快速幂
System.out.println("2^10 = " + quickPow(2, 10));
// 输出: 排序前: [38, 27, 43, 3, 9, 82, 10]
// 输出: 排序后: [3, 9, 10, 27, 38, 43, 82]
// 输出: 最大子数组和: 6
// 输出: 2^10 = 1024
}
}
03.Go代码
package main
import "fmt"
// 归并排序（分治）
func mergeSort(arr []int, left, right int) {
if left < right {
mid := left + (right-left)/2
// 分解
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
// 合并
merge(arr, left, mid, right)
}
}
func merge(arr []int, left, mid, right int) {
n1 := mid - left + 1
n2 := right - mid
L := make([]int, n1)
R := make([]int, n2)
for i := 0; i < n1; i++ {
L[i] = arr[left+i]
}
for j := 0; j < n2; j++ {
R[j] = arr[mid+1+j]
}
i, j, k := 0, 0, left
for i < n1 && j < n2 {
if L[i] <= R[j] {
arr[k] = L[i]
i++
} else {
arr[k] = R[j]
j++
}
k++
}
for i < n1 {
arr[k] = L[i]
i++
k++
}
for j < n2 {
arr[k] = R[j]
j++
k++
}
}
// 最大子数组和（分治）
func maxSubArray(nums []int) int {
return maxSubArrayHelper(nums, 0, len(nums)-1)
}
func maxSubArrayHelper(nums []int, left, right int) int {
if left == right {
return nums[left]
}
mid := left + (right-left)/2
// 分解
leftMax := maxSubArrayHelper(nums, left, mid)
rightMax := maxSubArrayHelper(nums, mid+1, right)
// 跨越中点的最大子数组
crossMax := maxCrossingSum(nums, left, mid, right)
// 合并
return max(max(leftMax, rightMax), crossMax)
}
func maxCrossingSum(nums []int, left, mid, right int) int {
sum := 0
leftSum := -1 << 31
for i := mid; i >= left; i-- {
sum += nums[i]
leftSum = max(leftSum, sum)
}
sum = 0
rightSum := -1 << 31
for i := mid + 1; i <= right; i++ {
sum += nums[i]
rightSum = max(rightSum, sum)
}
return leftSum + rightSum
}
// 快速幂（分治）
func quickPow(base int64, exp int) int64 {
if exp == 0 {
return 1
}
if exp == 1 {
return base
}
// 分解
half := quickPow(base, exp/2)
// 合并
if exp%2 == 0 {
return half * half
}
return half * half * base
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
// 归并排序
arr := []int{38, 27, 43, 3, 9, 82, 10}
fmt.Println("排序前:", arr)
mergeSort(arr, 0, len(arr)-1)
fmt.Println("排序后:", arr)
// 最大子数组和
nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
fmt.Println("最大子数组和:", maxSubArray(nums))
// 快速幂
fmt.Println("2^10 =", quickPow(2, 10))
// 输出: 排序前: [38 27 43 3 9 82 10]
// 输出: 排序后: [3 9 10 27 38 43 82]
// 输出: 最大子数组和: 6
// 输出: 2^10 = 1024
}
04.图解说明
📌 分治三步骤：
1. 分解（Divide）
将问题分解为规模更小的子问题
2. 解决（Conquer）
递归求解子问题，直到基本情况
3. 合并（Combine）
将子问题的解合并为原问题的解
📌 快速幂示例（2^10）：
2^10 = (2^5) * (2^5)
↓ ↓
2^5 = (2^2) * (2^2) * 2
↓ ↓
2^2 = 2 * 2 = 4
计算过程：
2^2 = 4
2^5 = 4 * 4 * 2 = 32
2^10 = 32 * 32 = 1024
时间复杂度：O(log n)，而不是O(n)
05.分治 vs 动态规划
特性 分治算法 动态规划
子问题 独立 重叠
解决方式 递归 迭代/递归
合并 需要 不需要
例子 归并排序 斐波那契
06.应用场景
✓ 归并排序
✓ 快速排序
✓ 二分查找
✓ 大整数乘法（Karatsuba）
✓ 快速幂
✓ 最近点对问题
LeetCode题目：
- 53. Maximum Subarray
- 169. Majority Element
- 215. Kth Largest Element