算法与数据结构学习笔记

POSTED 2024-11-05
UPDATE 2024-11-06

WORDS 78971
READ 3小时18分钟
VIEW 243

学习笔记

Hello 算法笔记

复杂度分析

数据结构

数组与链表

数组

数组 array是一种线性结构，用于将相同类型的元素存储在连续的内存空间中。元素在数组中的位置称为该元素的索引。

索引本质上就是内存地址的偏移量，所以首个元素的索引为 0，因为它的地址偏移量是 0

访问元素

在数组中访问元素非常高效，可以在 O(1)的的时间内访问数组中的任意一个元素。

func main() {
	nums := []int{1, 2, 3, 4}
	fmt.Println(nums[0])
}

插入元素

数组元素在内存中是连续的，如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移一位。但是，由于数组的长度是固定的，因此插入一个元素会导致尾部元素的丢失。

func insert(nums []int, num, index int) {
	for i := len(nums) - 1; i > index; i-- {
		nums[i] = nums[i-1]
	}
	nums[index] = num
}

删除元素

如果需要在数组中删除索引为 i的元素，则需要将 i之后的所有元素都向前移一位。

func remove(nums []int, index int) {
	for i := index; i < len(nums)-1; i++ {
		nums[i] = nums[i+1]
	}
}

遍历数组

func traverse(nums []int) {
	for i := 0; i < len(nums); i++ {
		fmt.Println(nums[i])
	}
	for _, value := range nums {
		fmt.Println(value)
	}
	for index, value := range nums {
		fmt.Printf("index: %d, value: %d \n", index, value)
	}
}

查找元素

在数组中查找指定元素需要遍历数组，每次判断元素值是否相等，相等则输出对应索引。因为数组是线性数据结构，所以查找操作也被称为线性查找。

func search(array []int, target int) int {
	for i := 0; i < len(array); i++ {
		if array[i] == target {
			return i
		}
	}
	return -1
}

扩容数组

在大多数编程语言中，数组的长度是不可变的。如果希望扩容数组，则需要建立一个更大的数组，然后将原数组元素依次复制到新数组，这是复杂度为 O(n)的操作。

func extend(nums []int, size int) []int {
	res := make([]int, len(nums)+size)
	for i := 0; i < len(nums); i++ {
		res[i] = nums[i]
	}
	return res
}

优点和局限性

优点：

空间效率高：分配连续的内存块，无需额外开销
直接随机访问：可以在 O(1)的时间内访问任意元素
缓存局部性：访问数据元素时，不仅会加载此元素，还会缓存周围的其它数据。

局限性：

时间复杂度高：插入和删除平均复杂度为 O(n)，n为数组长度
丢失元素：由于长度不可变，插入元素会导致元素丢失
内存浪费：删除元素后，其无意义的末尾元素会导致内存浪费
长度不可变：数组在初始化之后长度就固定了，扩容操作需要复制元素。

数组典型应用

随机访问：根据索引实现随机访问
排序和搜索：数组时排序和搜索算法最常用的数据结构
查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表
数据结构实现：数组可以实现栈、队列、哈希表、堆、图等数据结构

链表

链表 linked list是一种线性数据结构，每个元素都是一个节点对象，节点之间通过引用连接。引用记录了下一个节点的内存地址。

链表的设计使得节点可以分散存储在内存各处，内存地址无需连续。

链表的首个节点被称为头节点，最后一个节点为尾节点，链表节点除了包含值之外，还需额外保存下一个节点的引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。

// 链表节点结构体
type ListNode[T any] struct {
	Val  T
	Next *ListNode[T]
}

// 构造函数 创建一个链表节点
func NewListNode[T any](val T) *ListNode[T] {
	return &ListNode[T]{
		Val:  val,
		Next: nil,
	}
}

建立链表分为两步，第一步是初始化各个节点对象，第二部是构建节点之间的引用关系。

// 初始化节点
n0 := NewListNode[int](1)
n1 := NewListNode[int](2)
n2 := NewListNode[int](3)
// 初始化引用
n0.Next = n1
n1.Next = n2

插入节点

在链表中插入节点只需要改变新节点相邻两个节点的引用即可，时间复杂度为 O(1)。

func InsertNode[T any](node *ListNode[T], next *ListNode[T]) {
	n1 := node.Next
	next.Next = n1
	node.Next = next
}

删除节点

链表中删除节点也很方便，只需改变一个节点的引用即可。

// 删除节点node的下一个节点
func removeNode[T any](node *ListNode[T]) {
	if node.Next == nil {
		return
	}
	next := node.Next.Next
	node.Next = next
}

访问节点

在链表中访问节点的效率较低，链表中访问节点，程序需要从头节点出发，挨个向后遍历，直至找到目标节点，其操作的时间复杂度为 O(n)。

func Access[T any](head *ListNode[T], index int) *ListNode[T] {
	start := head
	for i := 0; i < index; i++ {
		if start == nil {
			return nil
		}
		start = start.Next
	}
	return start
}

查找节点

遍历链表，查询值相等的节点，输出该节点在链表中的索引。此过程也属于线性查找。

// 使用可比较的泛型约束
func findNode[T comparable](head *ListNode[T], target T) int {
	index := 0
	for head != nil {
		if head.Val == target {
			return index
		}
		head = head.Next
		index++
	}
	return -1
}

常见的链表类型

单向链表：普通链表，节点包含值和下一个节点的引用。
环形链表：如果单向链表的尾节点指向头节点，即得到一个环形链表。环形链表中的任意节点都可以视作头节点。
双向链表：与单向列表相比，双向列表记录了两个方向的引用，可以朝两个方向遍历链表。

// 双向链表节点 其类型必须是可比较的
type DoublyListNode[T comparable] struct {
	Val  T
	Next *DoublyListNode[T]
	Prev *DoublyListNode[T]
}

func NewDoublyListNode[T comparable](val T) *DoublyListNode[T] {
	return &DoublyListNode[T]{
		Val: val,
		Next: nil,
		Prev: nil,
	}
}

链表的典型应用

单向链表通常用于实现栈、队列、哈希表和图等数据结构：

栈与队列：当插入和删除操作都在链表的一端进行时，表现为先进后出，对应栈；当插入和删除分别在链表的两端进行时，表现为先进先出，对应队列。
哈希表：链式地址是解决哈希冲突的主流方案之一，所有哈希冲突的元素都会被放到一个链表中
图：邻接表是表示图的一种常用方式，图的每个顶点都与一个链表相关联，链表中的每个元素都代表该顶点相连的其它顶点。

双向链表常用于需要快速查找前一个和后一个元素的场景：

高级数据结构：比如在红黑树、B树中，需要访问节点的父节点，可以通过在节点中保存父节点的引用来实现。
浏览器历史：浏览器中，用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。
LRU算法

环形算法常用于需要周期性操作的场景，比如操作系统的资源调度

时间片轮转调度算法：一种常见的 CPU调度算法
数据缓冲区

列表

列表是一个抽象的数据结构概念，表示元素的有序集合，支持元素访问、添加、修改、删除和遍历等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。

链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容。
数组也支持元素增删查改，但由于其长度不可变，因此只能看作一个具有长度限制的列表。

当使用数组实现列表时，长度不可变的特性会导致列表的实用性降低。为了解决此问题，可以使用动态数组来实现列表。

访问元素

列表本质上数组，所有访问元素的操作和数组相同

插入和删除元素

列表可以自由的添加和删除元素。在尾部添加元素的时间复杂度为 O(1)，但插入和删除的元素的效率仍和数组相同。

// 初始化空列表
nums := make([]int, 0)

// 向尾部添加元素
nums = append(nums, 1)
nums = append(nums, 2)
nums = append(nums, 3)

//在索引2除插入元素
nums = append(nums[:2], append([]int{6}, nums[2:]...)...)

// 删除索引为2的元素
nums = append(nums[:2], nums[3:]...)

遍历列表

遍历方式和遍历数组一致

拼接列表

给定两个相同类型的列表，可以拼接在一起

nums1 := []int{1, 2, 3}
nums2 := []int{4, 5, 6}
// 将nums2拼接在nums1后面
nums3 := append(nums1, nums2...)
// go 1.20 以上版本 可以使用slices库中的Concat函数
nums4 := slices.Concat(nums1, nums2)

列表实现

实现一个简易的动态列表，包括三个重点设计：

初始容量：设定合理的数组初始容量
数量记录：记录列表的 size，判断当前列表是否需要扩容
扩容机制：当列表已满时插入元素就需要进行扩容

type ArrayList[T any] struct {
	cap   int
	size  int
	array []T
}

func NewArrayList[T any]() *ArrayList[T] {
	return &ArrayList[T]{
		cap:   10,
		size:  0,
		array: make([]T, 10),
	}
}
func (self *ArrayList[T]) Size() int {
	return self.size
}
func (self *ArrayList[T]) Cap() int {
	return self.cap
}
func (self *ArrayList[T]) Get(index int) T {
	if index < 0 || index >= self.size {
		panic("下标越界")
	}
	return self.array[index]
}
func (self *ArrayList[T]) Set(index int, value T) {
	if index < 0 || index >= self.size {
		panic("下标越界")
	}
	self.array[index] = value
}
// 向末尾添加元素
func (self *ArrayList[T]) Add(value T) {
	if self.size == self.cap {
		self.extendCapacity()
	}
	self.array[self.size] = value
	self.size++
}
// 插入元素
func (self *ArrayList[T]) Insert(index int, value T) {
	if index < 0 || index >= self.size {
		panic("下标越界")
	}
	if self.size == self.cap {
		self.extendCapacity()
	}
    // 将下标后面的元素后移一位
	for i := self.size - 1; i >= index; i-- {
		self.array[i+1] = self.array[i]
	}
	self.array[index] = value
	self.size++
}
// 删除元素
func (self *ArrayList[T]) Remove(index int) {
	if index < 0 || index >= self.size {
		panic("下标越界")
	}
    // 将下标后面的元素前移一位
	for i := index; i < self.size-1; i++ {
		self.array[i] = self.array[i+1]
	}
	self.size--
}
func (self *ArrayList[T]) ToArray() []T {
	return self.array[:self.size]
}

// 列表扩容
func (self *ArrayList[T]) extendCapacity() {
    // 扩容数量默认为当前列表大小的一倍
	extendSize := self.size
    // 如果当前列表数量大于等于1024 那么只扩容1.25倍
	if self.size >= 1024 {
		extendSize = int(float64(self.size) * 0.25)
	}
	self.array = append(self.array, make([]T, extendSize)...)
	self.cap = self.size + extendSize
}

小结

重点

数组和链表是两种基本的数据结构，分别代表数据在计算机内存中的两种存储方式：连续空间存储和分散空间存储。两者的特点呈现出互补的特性。
数组支持随机访问、占用内存较少；但插入和删除元素效率低，且初始化后长度不可变。
链表通过更改引用（指针）实现高效的节点插入与删除，且可以灵活调整长度；但节点访问效率低、占用内存较多。常见的链表类型包括单向链表、环形链表、双向链表。
列表是一种支持增删查改的元素有序集合，通常基于动态数组实现。它保留了数组的优势，同时可以灵活调整长度。
列表的出现大幅提高了数组的实用性，但可能导致部分内存空间浪费。
程序运行时，数据主要存储在内存中。数组可提供更高的内存空间效率，而链表则在内存使用上更加灵活。
缓存通过缓存行、预取机制以及空间局部性和时间局部性等数据加载机制，为 CPU 提供快速数据访问，显著提升程序的执行效率。
由于数组具有更高的缓存命中率，因此它通常比链表更高效。在选择数据结构时，应根据具体需求和场景做出恰当选择

Q & A

Q：数组存储在栈上和存储在堆上，对时间效率和空间效率是否有影响？

存储在栈上和堆上的数组都被存储在连续内存空间内，数据操作效率基本一致。然而，栈和堆具有各自的特点，从而导致以下不同点。

分配和释放效率：栈是一块较小的内存，分配由编译器自动完成；而堆内存相对更大，可以在代码中动态分配，更容易碎片化。因此，堆上的分配和释放操作通常比栈上的慢。
大小限制：栈内存相对较小，堆的大小一般受限于可用内存。因此堆更加适合存储大型数组。
灵活性：栈上的数组的大小需要在编译时确定，而堆上的数组的大小可以在运行时动态确定。

栈与队列

栈

栈 Stack是一种先进后出逻辑的线性数据结构，元素的顶部称为栈顶，底部称为栈底。把元素添加到栈顶的操作称为入栈，删除栈顶元素的操作叫做出栈。

栈的常用操作

方法	描述	复杂度
`push()`	元素入栈	`O(1)`
`pop()`	元素出栈	`O(1)`
`peek()`	访问栈顶元素	`O(1)`

栈的实现

栈遵循先入后出的原则，因此只能在栈顶添加或删除元素。然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以视为一种受限制的数组或链表

1. 基于链表实现

type stackNode[T any] struct {
	Val  T
	Next *stackNode[T]
}

type LinkedStack[T any] struct {
	head *stackNode[T]
	size int
}

func NewLinkedStack[T any]() *LinkedStack[T] {
	return &LinkedStack[T]{}
}

// 添加元素
func (self *LinkedStack[T]) Push(val T) {
	node := &stackNode[T]{
		Val:  val,
		Next: nil,
	}
	if self.size > 0 {
		node.Next = self.head
	}
	self.head = node
	self.size++
}

// 弹出栈顶元素
func (self *LinkedStack[T]) Pop() T {
	if self.IsEmpty() {
		panic("empty stack")
	}
	val := self.head.Val
	self.head = self.head.Next
	self.size--
	return val
}

// 访问栈顶元素
func (self *LinkedStack[T]) Peek() T {
	if self.IsEmpty() {
		panic("empty stack")
	}
	return self.head.Val
}

func (self *LinkedStack[T]) IsEmpty() bool {
	return self.size == 0
}

func (self *LinkedStack[T]) Size() int {
	return self.size
}

2. 基于数组的实现

使用数组实现栈时，可以将数组的尾部作为栈顶。入栈和出栈操作分别对应在数组尾部添加和删除元素，时间复杂度都为 O(1)

type ArrayStack[T any] struct {
	// 使用切片实现 可自动扩容
    data []T
}

func NewArrayStack[T any]() *ArrayStack[T] {
	return &ArrayStack[T]{
		data: make([]T, 0),
	}
}

func (self *ArrayStack[T]) Size() int {
	return len(self.data)
}
func (self *ArrayStack[T]) IsEmpty() bool {
	return len(self.data) == 0
}

func (self *ArrayStack[T]) Push(val T) {
	self.data = append(self.data, val)
}

func (self *ArrayStack[T]) Pop() T {
	if self.IsEmpty() {
		panic("stack empty")
	}
	index := len(self.data) - 1
	val := self.data[index]
	self.data = self.data[:index]
	return val
}

func (self *ArrayStack[T]) Peek() T {
	if self.IsEmpty() {
		panic("stack empty")
	}
	return self.data[len(self.data)-1]
}

实现对比

时间效率：

数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高
链表实现的栈可以提供更稳定的性能表现

空间效率：

数组实现的栈会造成一定程度的空间浪费
链表实现的栈由于链表节点要额外存储指针，因此链表节点占用的空间相对较大

典型应用

浏览器中的后退与前进、操作中的撤销和反撤销
程序内存管理，例如函数调用栈帧，用于记录函数的上下文信息

对列

队列 queue是一种遵循先入先出规则的线性数据结构。将队列头部称为队首，尾部称为队尾，将把元素加入队尾的操作称为入队，删除队首元素的操作称为出队

队列常用操作

方法	描述	复杂度
`push()`	元素入队，添加至队尾	`O(1)`
`pop()`	队首元素出队	`O(1)`
`peek()`	访问队首元素	`O(1)`

可以直接使用 go中的 list包

queue := list.New()
// 元素入队
queue.PushBack(1)
queue.PushBack(2)
queue.PushBack(3)
queue.PushBack(4)

// 访问队首元素
peek := queue.Front()

// 队首元素出队
pop := queue.Front()
queue.Remove(pop)

size := queue.Len()

队列实现

1. 基于链表实现

可以将链表的头节点和尾节点分别视为队首和队尾，规定队尾仅可添加节点，队首仅可删除节点

type queueNode[T any] struct {
	Val  T
	Next *queueNode[T]
}

type LinkedQueue[T any] struct {
	size int
    // 队首节点
	head *queueNode[T]
    // 队尾节点
	tail *queueNode[T]
}

func NewLinkedQueue[T any]() *LinkedQueue[T] {
	return &LinkedQueue[T]{}
}

func (self *LinkedQueue[T]) Size() int {
	return self.size
}

func (self *LinkedQueue[T]) IsEmpty() bool {
	return self.size == 0
}
// 元素入队
func (self *LinkedQueue[T]) Push(val T) {
	node := &queueNode[T]{
		Val:  val,
		Next: nil,
	}
    // 如果队首为空 那么队首 队尾都是当前节点
    // 否则将当前节点追加到队尾元素之后
	if self.head == nil {
		self.head = node
		self.tail = node
	} else {
		self.tail.Next = node
		self.tail = node
	}
	self.size++
}

func (self *LinkedQueue[T]) Peek() T {
	if self.IsEmpty() {
		panic("queue empty")
	}
	return self.head.Val
}

func (self *LinkedQueue[T]) Pop() T {
	if self.IsEmpty() {
		panic("queue empty")
	}
	val := self.head.Val
	self.head = self.head.Next
	self.size--
	return val
}

2. 基于数组实现

在数组中删除队首元素的时间复杂度为 0(1)，这会导致出队效率较低。

可以使用一个指向队首元素的索引和记录队列长度来规避此问题

type ArrayQueue[T any] struct {
    // 指向有效的队首元素
	front int
	size  int
	data  []T
}

func NewArrayQueue[T any]() *ArrayQueue[T] {
	return &ArrayQueue[T]{
		data: make([]T, 0),
	}
}

func (self *ArrayQueue[T]) Size() int {
	return self.size
}

func (self *ArrayQueue[T]) IsEmpty() bool {
	return self.size == 0
}

func (self *ArrayQueue[T]) Push(val T) {
	self.data = append(self.data, val)
	self.size++
}

func (self *ArrayQueue[T]) Peek() T {
	if self.IsEmpty() {
		panic("queue empty")
	}
	return self.data[self.front]
}

func (self *ArrayQueue[T]) Pop() T {
	if self.IsEmpty() {
		panic("queue empty")
	}
	val := self.data[self.front]
    // 将队首元素索引 +1
	self.front++
	self.size--
	return val
}

队列典型应用

消息队列，异步处理或者流量削峰，可以按照消息顺序平稳的进行处理
待办事项，例如下载任务队列等

双向队列

在队列中，仅能删除队首元素和在队尾添加元素。双向队列 double-endedqueue可以允许在头部和尾部执行元素的添加和删除操作。

双向队列常用操作

方法	描述	复杂度
`push_first()`	将元素添加至队首	`O(1)`
`push_last()`	将元素添加至队尾	`O(1)`
`pop_first()`	队首元素出队	`O(1)`
`pop_last()`	队尾元素出队	`O(1)`
`peek_first()`	访问队首元素	`O(1)`
`peek_last()`	访问队尾元素	`O(1)`

// 初始化双向队列
// 在 Go 中，将 list 作为双向队列使用
deque := list.New()

// 元素入队
deque.PushBack(2)      // 添加至队尾
deque.PushBack(5)
deque.PushBack(4)
deque.PushFront(3)     // 添加至队首
deque.PushFront(1)

// 访问元素
front := deque.Front() // 队首元素
rear := deque.Back()   // 队尾元素

// 元素出队
deque.Remove(front)    // 队首元素出队
deque.Remove(rear)     // 队尾元素出队

// 获取双向队列的长度
size := deque.Len()

双向队列实现

1. 基于双向链表实现

可以使用普通的单向链表来实现队列，对于双向队列来说，由于需要实现两个方向的操作，所以可以采用双向链表实现

type queueNode[T any] struct {
	Val  T
    // 下一个节点
	Next *queueNode[T]
    // 上一个节点
	Prev *queueNode[T]
}

type LinkedQueue[T any] struct {
	size int
	// 队首节点
	head *queueNode[T]
	// 队尾节点
	tail *queueNode[T]
}

func NewLinkedQueue[T any]() *LinkedQueue[T] {
	return &LinkedQueue[T]{}
}

func (self *LinkedQueue[T]) Size() int {
	return self.size
}

func (self *LinkedQueue[T]) IsEmpty() bool {
	return self.size == 0
}

// 队首添加元素
func (self *LinkedQueue[T]) PushFirst(val T) {
	node := &queueNode[T]{
		Val:  val,
		Next: nil,
		Prev: nil,
	}
	if self.size == 0 {
		self.head = node
		self.tail = node
	}
	self.head.Prev = node
	node.Next = self.head
	self.head = node
	self.size++
}

// 队尾添加元素
func (self *LinkedQueue[T]) PushLast(val T) {
	node := &queueNode[T]{
		Val:  val,
		Next: nil,
		Prev: nil,
	}
	if self.size == 0 {
		self.head = node
		self.tail = node
	}
	node.Prev = self.tail
	self.tail.Next = node
	self.tail = node
	self.size++
}

func (self *LinkedQueue[T]) PeekFirst() T {
	if self.IsEmpty() {
		panic("queue empty")
	}
	return self.head.Val
}

func (self *LinkedQueue[T]) PeekLast() T {
	if self.IsEmpty() {
		panic("queue empty")
	}
	return self.tail.Val
}

func (self *LinkedQueue[T]) PopFirst() T {
	if self.IsEmpty() {
		panic("queue empty")
	}
	val := self.head.Val
	self.head = self.head.Next
	self.size--
	return val
}

func (self *LinkedQueue[T]) PopLast() T {
	if self.IsEmpty() {
		panic("queue empty")
	}
	val := self.tail.Val
	self.tail = self.tail.Prev
	self.size--
	return val
}

2. 基于数组实现

在队列实现的基础上，增加队首入队和队尾出队的方法即可

双向队列应用

双向队列兼具栈与队列的逻辑，因此可以实现这两者的所有应用场景，同时提供更高的自由度。

小结

重点回顾：

栈是一种遵循先入后出原则的数据结构，可通过数组或链表来实现。
在时间效率方面，栈的数组实现具有较高的平均效率，但在扩容过程中，单次入栈操作的时间复杂度会劣化至 O(n) 。相比之下，栈的链表实现具有更为稳定的效率表现。
在空间效率方面，栈的数组实现可能导致一定程度的空间浪费。但需要注意的是，链表节点所占用的内存空间比数组元素更大。
队列是一种遵循先入先出原则的数据结构，同样可以通过数组或链表来实现。在时间效率和空间效率的对比上，队列的结论与前述栈的结论相似。
双向队列是一种具有更高自由度的队列，它允许在两端进行元素的添加和删除操作。

哈希表

哈希表 hash table，又称散列表，通过建立 key和值 value之间的映射，实现高效的元素查询。

除哈希表外，数组和链表也可实现查询功能，但它们的时间复杂度不同：

添加元素：将元素添加到数组（链表）尾部即可，使用 O(1)时间
查询元素：数组（链表）查询元素需要遍历，使用 O(n)时间
删除元素：需要先查询元素，再删除元素，使用 O(n)时间

操作	数组	链表	哈希表
查找元素	`O(n)`	`O(n)`	`O(1)`
添加元素	`O(1)`	`O(1)`	`O(1)`
删除元素	`O(n)`	`O(n)`	`O(1)`

在哈希表中进行增删查改的时间复杂度都是 O(1) ，非常高效

哈希表常用操作

哈希表的常用操作包括：初始化、查询、添加键值对和删除键值对等

// 初始化哈希表
hmap := make(map[int]rune)

// 添加操作 添加键值对
hmap[1] = 'a'
hmap[2] = 'b'
hmap[3] = 'c'

// 查询操作 通过key查询value
value := hmap[1]
fmt.Println(value)

// 删除操作 从哈希表中删除指定key
delete(hmap, 2)

哈希表有三种遍历方式：遍历键值对、遍历键、遍历值

// 遍历键值对
for key, value := range hmap {
    fmt.Printf("%d -> %s", key, value)
}

// 遍历值
for _, value := range hmap {
    fmt.Printf("value: %s", value)
}

// 遍历键
for key, _ := range hmap {
    fmt.Printf("key: %d", key)
}

哈希表简单实现

先考虑最简单的情况，使用数组实现哈希表，将数组中的每个空位称为桶 bucket，桶种存储键值对。通过哈希函数 hash function来计算出 key对应的桶在数组种的存放位置。

输入一个 key，哈希函数分为以下两步计算：

通过某种 hash算法得到哈希值
将哈希值对数组长度进行取模，获取该 key对应的桶索引

然后就可以根据索引访问对应的桶获取 value

type bucket[V any] struct {
	key   int
	value V
}

type ArrayHashMap[V any] struct {
	hashed  hash.Hash
	buckets []*bucket[V]
	size    int
}

func NewArrayHashMap[V any]() *ArrayHashMap[V] {
	return &ArrayHashMap[V]{
		hashed:  sha256.New(),
		buckets: make([]*bucket[V], 100),
	}
}

// 计算对应key的bucket下标
func (self *ArrayHashMap[V]) hashFunc(key int) int {
	return key % 100
}

// 查询操作
func (self *ArrayHashMap[V]) Get(key int) (result V, ok bool) {
	index := self.hashFunc(key)
	bucket := self.buckets[index]
	if bucket == nil {
		return
	}
	result = bucket.value
	ok = true
	return
}

// 添加操作
func (self *ArrayHashMap[V]) Put(key int, value V) {
	index := self.hashFunc(key)
	self.buckets[index] = &bucket[V]{key: key, value: value}
}

// 删除操作
func (self *ArrayHashMap[V]) Remove(key int) {
	index := self.hashFunc(key)
	self.buckets[index] = nil
}

func (self *ArrayHashMap[V]) Entitys() []*bucket[V] {
	result := make([]*bucket[V], 0)
	for _, value := range self.buckets {
		if value != nil {
			result = append(result, value)
		}
	}
	return result
}

func (self *ArrayHashMap[V]) KeySet() []int {
	result := make([]int, 0)
	for _, value := range self.buckets {
		if value != nil {
			result = append(result, value.key)
		}
	}
	return result
}

func (self *ArrayHashMap[V]) ValueSet() []V {
	result := make([]V, 0)
	for _, value := range self.buckets {
		if value != nil {
			result = append(result, value.value)
		}
	}
	return result
}

哈希冲突与扩容

哈希函数的作用是将 key构成的输入空间映射到输出空间。而输入空间往往大于输出空间，因此，一定存在多个输入对应一个输出的情况。这种多个输入对应到同一输出的情况称为哈希冲突。

例如上面的例子中 136 和 236 就会哈希冲突，哈希函数返回的下标都是 36

哈希表容量 n越大，多个 key被分配到同一个桶中的概率就越低，发生冲突的概率就越小。因此，可以通过扩容哈希表来减少哈希冲突。

类似于数组扩容，哈希表扩容需要将所有键值对从原哈希表迁移到新哈希表，非常耗时；并且因为哈希表容量的改变，需要重新使用哈希函数来重新计算所有键值对的存储位置。为此，一般都会预留足够大的哈希表容量，防止频繁扩容。

负载因子 load factor是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。

哈希冲突会导致查询结果错误，严重影响哈希表的可用性。为了解决该问题，每当遇到哈希冲突时，我们就进行哈希表扩容，直至冲突消失为止。但扩容会导致严重的性能问题，为了提示效率，可以采取以下策略：

改良哈希数据结构，使哈希表可以在出现哈希冲突时正常工作
仅在必要时，即当哈希冲突比较严重时，才执行扩容操作

哈希表的结构改良方法主要包括链式地址和开放寻址

链式地址

在原始哈希表中，每个桶仅能存储一个键值，链式地址 separate chaining将单个元素转化为链表，将键值对作为链表节点，所有发生冲突的键值对都存储在同一链表中。

基于链式地址实现的哈希表的操作方法也发生了变化

查询元素：输入 key ，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比 key 以查找目标键值对
添加元素：首先通过哈希函数访问链表头节点，然后将节点（键值对）添加到链表中。
删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查找目标节点并将其删除。

链式地址存在以下不足：

占用空间增大：链表节点保存节点指针，更耗费内存空间
查询效率较低：需要线性遍历链表来查询对应元素

type Bucket[T any] struct {
	key  int
	val  T
	next *Bucket[T]
}

type ChainingHashMap[T any] struct {
    // 哈希表的桶数量
	size        int
    // 哈希表容量
	cap         int
    // 负载因子阈值
	loadThres   float64
    // 哈希表的扩容倍数
	extendRatio int
	buckets     []*Bucket[T]
}

func NewChainingHashMap[T any]() *ChainingHashMap[T] {
	return &ChainingHashMap[T]{
		size:        0,
		cap:         4,
		loadThres:   0.75,
		extendRatio: 2,
		buckets:     make([]*Bucket[T], 4),
	}
}

func (self *ChainingHashMap[T]) hashFunc(key int) int {
	return key % self.cap
}

func (self *ChainingHashMap[T]) loadFactor() float64 {
	return float64(self.size) / float64(self.cap)
}

func (self *ChainingHashMap[T]) Get(key int) (result T, ok bool) {
	index := self.hashFunc(key)
	bucket := self.buckets[index]
	for bucket != nil {
		if bucket.key == key {
			result = bucket.val
			ok = true
			break
		}
		bucket = bucket.next
	}
	return
}

func (self *ChainingHashMap[T]) Put(key int, value T) {
	if self.loadFactor() >= self.loadThres {
		self.extend()
	}
	index := self.hashFunc(key)
    // 先获取索引对应的bucket 如果bucket链表内存在该key 那么直接更新value
    // 不存在就将当前键值对 设置尾bucket链表的头节点
	bucket := self.buckets[index]
	if bucket != nil {
		for bucket != nil {
			if bucket.key == key {
				bucket.val = value
				return
			}
			bucket = bucket.next
		}
	} else {
		self.size++
	}
	newBucket := &Bucket[T]{
		key:  key,
		val:  value,
		next: self.buckets[index],
	}
	self.buckets[index] = newBucket
}

func (self *ChainingHashMap[T]) Remove(key int) {
	index := self.hashFunc(key)
	bucket := self.buckets[index]
	if bucket == nil {
		return
	}
	if bucket.key == key {
		self.buckets[index] = bucket.next
		return
	}
	for bucket.next != nil {
		if bucket.next.key == key {
			bucket.next = bucket.next.next
			return
		}
		bucket = bucket.next
	}
}

// 哈希表扩容 先扩容bucket 再重新添加所有元素
func (self *ChainingHashMap[T]) extend() {
	length := len(self.buckets)
	oldBuckets := make([]*Bucket[T], length)
	for i := 0; i < length; i++ {
		oldBuckets[i] = self.buckets[i]
	}
	self.cap *= self.extendRatio
	self.buckets = make([]*Bucket[T], self.cap)
	for i := 0; i < length; i++ {
		bucket := oldBuckets[i]
		for bucket != nil {
			self.Put(bucket.key, bucket.val)
			bucket = bucket.next
		}
	}
}

开放寻址

开放寻址 open addressing不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突，探测方式主要包括线性探测、平方探测和多次哈希等。

线性探测

线性探测采用固定步长的线性搜索来进行探测

拆入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为 1 ），直至找到空桶，将元素插入其中。
查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None 。

但是，线性探测容易产生聚集现象，具体来说就是：数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。

另一个问题就是，不能在开放寻址哈希表中直接删除元素。因为删除元素会产生一个空桶，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，可能会误判这些元素不存在。

为了解决该问题，可以采用懒删除机制。不直接从哈希表中移除元素，而是利用一个常量 TOMESTONE来标记这个桶，表示这是一个空桶。并且在线性探测时，探测到 TOMESTONE也会继续向下遍历。但是懒删除可能会加速哈希表的性能退化，因为每次删除操作都会产生一个删除标记。

为此，可以在线性探测中记录遇到的首个 TOMBSTONE 的索引，并将搜索到的目标元素与该 TOMBSTONE 交换位置。这样每当查询或添加元素时，元素会被移动至距离理想位置（探测起始点）更近的桶，从而优化查询效率。

type Bucket[T any] struct {
	key      int
	val      T
	isRemove bool
}

type OpenAddressingHashMap[T any] struct {
	size        int
	cap         int
	loadThres   float64
	extendRatio int
	buckets     []*Bucket[T]
}

func NewOpenAddressingHashMap[T any]() *OpenAddressingHashMap[T] {
	return &OpenAddressingHashMap[T]{
		size:        0,
		cap:         4,
		loadThres:   0.75,
		extendRatio: 2,
		buckets:     make([]*Bucket[T], 4),
	}
}

func (self *OpenAddressingHashMap[T]) findBucket(key int) int {
	index := self.hashFunc(key)
	firstTombstone := -1
	for self.buckets[index] != nil {
		if self.buckets[index].key == key {
			// 如果删除标记可用 就将键值对移动到第一个删除标记处 然后将当前索引节点设置为已删除
			if firstTombstone != -1 {
				self.buckets[firstTombstone] = self.buckets[index]
				self.buckets[index].isRemove = true
				return firstTombstone
			}
			return index
		}
		// 如果删除标记还没初始化并且当前索引节点被删除 那么将删除标记设置为当前节点的索引
		if firstTombstone == -1 && self.buckets[index].isRemove == true {
			firstTombstone = index
		}
		index = (index + 1) % self.cap
	}
	// 若key不存在且有删除的节点 那么就将删除的节点做为添加点
	if firstTombstone != -1 {
		return firstTombstone
	}
	return index
}


func (self *OpenAddressingHashMap[T]) Get(key int) (result T, ok bool) {
	index := self.findBucket(key)
    // 如果获取到的桶不为空并且未被删除 那么就返回值
	if self.buckets[index] != nil && !self.buckets[index].isRemove {
		result = self.buckets[index].val
		ok = true
	}
	return
}

func (self *OpenAddressingHashMap[T]) Put(key int, value T) {
    // 添加时 先判断是否需要扩容
	if self.loadFactor() >= self.loadThres {
		self.extend()
	}
	index := self.findBucket(key)
    // 如果桶已存在并且未被删除 直接更新val即可
	if self.buckets[index] == nil || self.buckets[index].isRemove {
		self.buckets[index] = &Bucket[T]{key: key, val: value, isRemove: false}
		self.size++
	} else {
		self.buckets[index].val = value
	}
}

func (self *OpenAddressingHashMap[T]) Remove(key int) {
	index := self.findBucket(key)
    // 如果桶不存在或者已被删除 那么直接返回
	if self.buckets[index] == nil || self.buckets[index].isRemove {
		return
	}
    // 将桶设置为删除状态
	self.buckets[index].isRemove = true
	self.size--
}

func (self *OpenAddressingHashMap[T]) hashFunc(key int) int {
	return key % self.cap
}

func (self *OpenAddressingHashMap[T]) loadFactor() float64 {
	return float64(self.size) / float64(self.cap)
}

func (self *OpenAddressingHashMap[T]) extend() {
	oldBuckets := self.buckets
	self.cap *= self.extendRatio
	self.size = 0
	self.buckets = make([]*Bucket[T], self.cap*self.extendRatio)
	for _, bucket := range oldBuckets {
		if bucket != nil && !bucket.isRemove {
			self.Put(bucket.key, bucket.val)
		}
	}
}

平方探测

平凡探测和线性探测类似，都是开放寻址的策略之一。当发生冲突时，平方探测不是简单地跳过一个固定的步数，而是跳过“探测次数的平方”的步数，即 1,4,9,… 步。

平方探测具有以下优势：

平方探测通过跳过探测次数平方的距离，试图缓解线性探测的聚集效应。
平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀。

存在的问题：

仍然存在聚集现象，即某些位置比其他位置更容易被占用。
由于平方的增长，平方探测可能不会探测整个哈希表，这意味着即使哈希表中有空桶，平方探测也可能无法访问到它

多次哈希

多次哈希方法使用多个哈希函数进行探测

插入元素：若第一个哈希函数出现冲突，则继续尝试后续哈希函数，直到找到空位。
查找元素：在相同的哈希函数顺序下进行查找，直至找到目标元素。若遇到空位或以尝试左右哈希函数，那说明不存在，返回空

与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会带来额外的计算量。

编程语言的选择

Python采用开放寻址。字典 dict使用伪随机数进行探测
Java采用链式地址。JDK1.8之后，当 HashMap内数组长度达到64且链表长度达到8时，链表会转换为红黑树以提升查找性能
Go采用链式地址。规定每个存储桶最多存储8个键值对，超出容量则链接一个溢出桶；当溢出桶过多时，会执行一次特殊的等量扩容操作，以确保性能。

哈希算法

无论是开放寻址还是链式地址，它们只能保证哈希表可以在发生冲突时正常工作，而无法减少哈希冲突的发生。如果哈希冲突过于频繁，哈希表的性能则会急剧劣化。对于链式地址哈希表，理想情况下键值对均匀分布在各个桶中，达到最佳查询效率；最差情况下所有键值对都存储到同一个桶中，时间复杂度退化至 O(n) ，键值对的分布情况是由哈希函数决定的。

哈希算法的目标

哈希算法应具有以下特点：

确定性：对于相同的输入，哈希算法应始终计算出相同的哈希值
效率高：计算过程越快越好
均匀分布：分布越均匀，哈希冲突概率越低

此外，还需要具有一定的安全特性：

单向性：无法通过哈希值反推
抗碰撞性：两个不同的输入，哈希碰撞的概率应该非常低
雪崩效应：输入的微小变化也会导致输出的不可预测

哈希算法除了用于实现哈希表，还存在于其它领域：

密码存储：只存储用户密码的哈希值，需要比对时，通过哈希值进行比对
数据完整性检查：只有数据的哈希值匹配，才可视为数据时完整的

哈希算法的设计

加法哈希：将输入的每个字符 ASCII码相加，将得到的总和做为哈希值
乘法哈希：利用乘法的不相关性，每轮乘以一个尝试，将各个字符的 ASCII码累积到哈希值中
异或哈希：将输入数据的每个元素通过异或操作累积到一个哈希值中
旋转哈希：将每个字符的 ASCII 码累积到一个哈希值中，每次累积之前都会对哈希值进行旋转操作

// 用于取模的大质数
// 使用大质数作为模数，可以最大化地保证哈希值的均匀分布
// 因为质数不与其他数字存在公约数，可以减少因取模操作而产生的周期性模式，从而避免哈希冲突。
const modules = 1000000007

// 加法哈希
func addHash(key string) int {
	var hash int64
	for _, char := range []byte(key) {
		hash = (hash + int64(char)) % modules
	}
	return int(hash)
}

// 乘法哈希
func mulHash(key string) int {
	var hash int64
	for _, char := range []byte(key) {
		hash = (31*hash + int64(char)) % modules
	}
	return int(hash)
}

// 异或哈希
func xorHash(key string) int {
	hash := 0
	for _, char := range []byte(key) {
		hash ^= int(char)
		hash = (31*hash + int(char)) % modules
	}
	return hash & modules
}

// 旋转哈希
func spinHash(key string) int {
	var hash int64
	for _, char := range []byte(key) {
		hash = ((hash << 4) ^ (hash >> 28) ^ int64(char)) % modules
	}
	return int(hash)
}

常见哈希算法

	MD5	SHA-1	SHA-2	SHA-3
推出时间	1992	1995	2002	2008
输出长度	128bit	160bit	256/512bit	224/256/384/512 bit
哈希冲突	较多	较多	很少	很少
安全等级	低	低	高	高
应用	已被弃用，可用于完整性检查	已被弃用	交易验证、数字签名等	替代 `SHA-2`

数据结构的哈希值

哈希表的 key 可以是整数、小数或字符串等数据类型。编程语言通常会为这些数据类型提供内置的哈希算法，用于计算哈希表中的桶索引。

在 Python中，hash()函数用来计算各种数据类型的哈希值。

整数和布尔类型的哈希值就是其本身
浮点数和字符串的哈希值需要计算
元组的哈希值是对其中每一个元素进行哈希，然后将所有哈希值组合起来，得到单一的哈希值
对象的哈希值基于内存地址生成。可以重写哈希方法，实现基于内容生成哈希值

Go 未提供内置的 hash_code函数，对象也没有需要实现的 hash方法

在大部分编程语言中，只有不可变对象才可以做为哈希表的 key。例如将列表做为 key，当列表的内容发生变化时，它的哈希值也改变了。

树

二叉树

二叉树 binary tree是一种非线性数据结构，代表祖先与后代之间的派生关系，体现了一份为二的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。

type TreeNode[T comparable] struct {
	val   T
	left  *TreeNode[T]
	right *TreeNode[T]
}

func NewTreeNode[T comparable](val T) *TreeNode[T] {
	return &TreeNode[T]{
		val:   val,
		left:  nil,
		right: nil,
	}
}

每个节点都有两个引用，分别指向左子节点 left-child node和右子节点 right-child node，该节点被称为这两个子节点的父节点 parent node。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树 left subtree，同理可得右子树 right subtree。

在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。

二叉树常用术语

根节点（root node）：二叉树顶层的节点，没有父节点
叶节点 leaf node）：没有子节点的节点
边（edge）：连接两个节点的引用
节点所在的层（level）：从顶至底递增，根节点所在层为1
节点的度（degree）：节点的子节点数量
二叉树的高度（height）：从根节点到最远叶节点所经过的边数量
节点的深度（depth）：从根节点到该节点所经过的边的数量
节点的高度（height）：该节点到节点下最远叶节点的边数量

二叉树基本操作

初始化二叉树

// 初始化二叉树节点
n1 := NewTreeNode[int](1)
n2 := NewTreeNode[int](2)
n3 := NewTreeNode[int](3)
n4 := NewTreeNode[int](4)
n5 := NewTreeNode[int](5)

// 构建节点之间的引用关系
n1.Left = n2
n2.Right = n3
n2.Left = n4
n2.Right = n5

与链表类似，在二叉树中插入与删除节点也是通过修改指针来实现

// 在n1和n2之间插入n6节点
n6 := NewTreeNode[int](6)
n1.Left = n6
n6.Left = n2

// 删除节点n6
n1.Left = n2

常见的二叉树类型

完美二叉树 perfect bianry tree：所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0，其余所有节点的度都为 2；若树的高度为 $h$ ，则节点总数为 $2^{h+1}-1$ 。
完全二叉树 complete binary tree：只有最底层的节点未被填满，且最底层节点尽量靠左填充。完美二叉树也是一颗完全二叉树。
完满二叉树 full binary tree：除了叶节点之外，其余所有节点都有两个子节点。
平衡二叉树 balanced binary tree：中任意节点的左子树和右子树的高度之差绝对值不超过 1

二叉树退化

当二叉树的每层节点都被填满时，达到完美二叉树；而当所有节点都偏向一侧时，二叉树退化为链表。

完美二叉树是理想情况，可以充分发回二叉树分治的优势
退化为链表则各项操作都变为线性操作，时间复杂度退化为 $O(n)$

二叉树的最佳结构和最差结构

	完美二叉树	链表
第 $i$ 层的节点数量	$2^{i+1}$	1
高度为 $h$ 的树的叶节点数量	$2^{h}$	1
高度为 $h$ 的树的节点总数	$2^{h+1}-1$	$h+1$
节点总数为 $n$ 的树的高度	$\log_{2}(n+1)-1$	$n-1$

二叉树遍历

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历

层序遍历

层序遍历 level-order traversal 从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

层序遍历本质上广度优先遍历 breadth-first traversal，也称广度优先搜索 breadth-first search, BFS，体现一种一圈一圈向外扩展的逐层遍历方式。

// 层序遍历 利用队列的先进先出规则来实现
func LevelOrder[T comparable](root *TreeNode[T]) []T {
	queue := list.New()
	queue.PushBack(root)
	// 保存遍历结果
	result := make([]T, 0)
	for queue.Len() > 0 {
		// 将头节点出队
		node := queue.Remove(queue.Front()).(*TreeNode[T])
		result = append(result, node.Val)
		// 判断其左子节点和右子节点是否存在 存在则入队
		if node.Left != nil {
			queue.PushBack(node.Left)
		}
		if node.Right != nil {
			queue.PushBack(node.Right)
		}
	}
	return result
}

假设 $n$ 为节点数量，层序遍历需要将所有节点访问一次，即时间复杂度为 $O(n)$ ；在满二叉树的情况下，遍历到最底层节点之前，队列中最多存在 $(n+1)/2$ 个节点，那么空间复杂度也为 $O(n)$ 。

前序、中序、后序遍历

前序、中序和后续遍历都属于深度优先遍历 depth-first traversal ，也称深度优先搜索 depth-first search, DFS。

深度优先遍历就像是绕着二叉树的外围走一圈，通常使用递归实现。

// PreOrder 前序遍历
func PreOrder[T comparable](root *TreeNode[T], result *[]T) {
	if root == nil {
		return
	}
	// 访问优先级 根节点 -> 左子树 -> 右子树
	*result = append(*result, root.Val)
	PreOrder[T](root.Left, result)
	PreOrder[T](root.Right, result)
}

// InOrder 中序遍历
func InOrder[T comparable](root *TreeNode[T], result *[]T) {
	if root == nil {
		return
	}
	// 访问优先级 左子树 -> 根节点 -> 右子树
	InOrder[T](root.Left, result)
	*result = append(*result, root.Val)
	InOrder[T](root.Right, result)
}

// PostOrder 后序遍历
func PostOrder[T comparable](root *TreeNode[T], result *[]T) {
	if root == nil {
		return
	}
	// 访问优先级 左子树 -> 右子树 -> 根节点
	PostOrder[T](root.Left, result)
	PostOrder[T](root.Right, result)
	*result = append(*result, root.Val)
}

在递归的过程中，所有的节点都会被访问一次，所以时间复杂度为 $O(n)$ ；在最差的情况下，即树退化为链表，递归深度达到链表的长度，系统会占用 $O(n)$ 的栈帧空间，空间复杂度为 $O(n)$ 。

二叉树数组表示

根据层序遍历的特性，可以推导出父节点索引与子节点索引之间的映射关系。若某节点的索引为 $i$ ，则该节点的左子节点索引为 $2i+1$ ，右子节点索引为 $2i + 2$ 。给定数组中的任意一个节点，都可以通过映射公式来访问它的子节点。

// 使用数组表示一个完美二叉树
type ArrayBinaryTree struct {
	array []any
}

func NewArrayBinaryTree(array []any) *ArrayBinaryTree {
	return &ArrayBinaryTree{
		array: array,
	}
}

func (self *ArrayBinaryTree) Size() int {
	return len(self.array)
}

// 获取索引为 index 的节点的值
func (self *ArrayBinaryTree) Val(index int) any {
	if index < 0 || index >= self.Size() {
		return nil
	}
	return self.array[index]
}

// 获取索引为 index 的节点的左子节点索引
func (self *ArrayBinaryTree) Left(index int) int {
	return index<<1 - 1
}

// 获取索引为 index 的节点的右子节点索引
func (self *ArrayBinaryTree) Right(index int) int {
	return index<<1 + 2
}

// 获取索引为 index 的节点的父节点索引
func (self *ArrayBinaryTree) Parent(index int) int {
	return (index - 1) >> 1
}

// 层序遍历
func (self *ArrayBinaryTree) LevelOrder() []any {
	result := make([]any, 0)
	for _, item := range self.array {
		if item != nil {
			result = append(result, item)
		}
	}
	return result
}

// 前序遍历
func (self *ArrayBinaryTree) PreOrder() []any {
	result := make([]any, 0)
	self.dfs(0, "pre", &result)
	return result
}

// 中序遍历
func (self *ArrayBinaryTree) InOrder() []any {
	result := make([]any, 0)
	self.dfs(0, "in", &result)
	return result
}

// 后序遍历
func (self *ArrayBinaryTree) PostOrder() []any {
	result := make([]any, 0)
	self.dfs(0, "post", &result)
	return result
}

func (self *ArrayBinaryTree) dfs(index int, order string, result *[]any) {
	value := self.Val(index)
	if value == nil {
		return
	}
	if order == "pre" {
		*result = append(*result, value)
	}
	self.dfs(self.Left(index), order, result)
	if order == "in" {
		*result = append(*result, value)
	}
	self.dfs(self.Right(index), order, result)
	if order == "post" {
		*result = append(*result, value)
	}
}

完美二叉树是一个特例，二叉树的中间层通常存在非常多的 None。由于层序遍历并不包含这些 None，无法凭该序列推断 None的数量和分布位置，这就会导致可能有多种二叉树结构都符合该层序遍历序列。

为了在数组中表示任意二叉树，需要在层序遍历中显式写出所有的 None。这样处理后，层序遍历就可以表示唯一二叉树了。

// 数组表示 使用 nil 表示 None 位置
tree := []any{1, 2, 3, 4, nil, nil, 7}

若一个二叉树为完全二叉树，那么 None 只会出现在底层且靠右的位置，就可以推断出所有 None 一定会出现在层序遍历的末尾。可以省略存储。

// 数组表示的完全二叉树
tree := []any{1, 2, 3, 4, nil, nil, nil}

// 可以简写为
tree := []any{1, 2, 3, 4}

二叉树的数组表示有以下优点：

数组存储在连续的内存空间内，对缓存友好，访问和遍历速度较快。
不需要存储指针，节省内存空间
允许随机访问节点

也存在以下缺点：

数组存储需要连续内存空间，不适合存储数据量过大的树
增删节点需要通过数组插入和删除操作实现，效率较低
二叉树中存在大量 None 时，数组空间利用率较低

二叉搜索树

二叉搜索树 binary search tree 应当满足以下条件：

对于根节点，左子树中所有节点的值 $<$ 根节点的值 $<$ 右子树中所有节点的值
任意节点的左、右子树也是二叉搜索树，同样满足条件 1

二叉搜索树操作

查找节点

给定目标节点值 target ，可以根据二叉搜索树的性质来查找，声明一个节点 current 等于二叉搜索树的根节点，循环比较节点值 current.Val 和 target 之间的大小关系。

若 current.Val < target ，说明目标节点在右子树中，执行 current = cueernt.Right
若 current.Val > target ，说明目标节点在左子树中，执行 current = current.Left
若 current.Val == target，直接返回当前节点

二分搜索树的查找操作与二分算法的工作原理一致。循环次数最多为二叉树的高度，当二叉树平衡时使用 $O(\log n)$ 的时间。

// 二分搜索树类
type BinarySearchTree struct {
	root *TreeNode
}

func NewBinarySearchTree(root *TreeNode) *BinarySearchTree {
	return &BinarySearchTree{
		root: root,
	}
}

// 查找操作
func (self *BinarySearchTree) Search(target int) *TreeNode {
	node := self.root
	for node != nil {
		if node.Val < target {
			node = node.Right
		} else if node.Val > target {
			node = node.Left
		} else {
			break
		}
	}
	return node
}

插入节点

为了保持二叉搜索树左子树 < 根节点 < 右子树的性质，插入流程如下：

查找插入位置：与查找操作类型，从根节点出来，根据当前节点的值和待插入值的大小关系向下搜索
在指定位置插入节点

在插入节点时，需要注意以下两点：

二叉搜索树不允许存在重复节点，如果待插入的值在树中已存在，那么跳过插入
为了实现插入节点，我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时，可以获取到其父节点，从而完成节点插入操作

// 插入节点
func (self *BinarySearchTree) Insert(value int) {
	current := self.root
	if current == nil {
		self.root = NewTreeNode(value)
		return
	}
	var prev *TreeNode
	for current != nil {
		if current.Val == value {
			return
		}
		prev = current
		if current.Val < value {
			current = current.Right
		} else {
			current = current.Left
		}
	}
	node := NewTreeNode(value)
	if prev.Val < value {
		prev.Right = node
	} else {
		prev.Left = node
	}
}

和查找节点相同，插入节点也使用 $O(\log n)$ 的时间。

删除节点

先在二叉树中查找到目标节点，再将其删除。与插入节点类似，需要保证在删除操作完成后，二叉搜索树的左子树 < 根节点 < 右子树的性质仍然满足。

当待删除节点的度为 $0$ 时，表示该节点是叶节点，可以直接删除
当待删除节点的度为 $1$ 时，将待删除的节点替换为其子节点即可
当待删除节点的度为 $2$ 时，无法直接删除，需要使用一个节点来替换。这个节点可以是右子树的最小节点或左子树的最大节点

// 删除节点
func (self *BinarySearchTree) Remove(value int) {
	current := self.root
	var prev *TreeNode
	for current != nil {
		// 如果查询到了节点 直接 break
		if current.Val == value {
			break
		}
		prev = current
		if current.Val < value {
			current = current.Right
		} else {
			current = current.Left
		}
	}
	// 如果找不到待删除的节点 那么直接删除
	if current == nil {
		return
	}
	// 如果子节点数为 0 或者 1
	if current.Left == nil || current.Right == nil {
		// 拿到子节点
		var child *TreeNode
		if current.Left != nil {
			child = current.Left
		} else {
			child = current.Right
		}
		// 删除节点
		if current != self.root {
			// 替换上一个待删除节点父节点的指针
			if prev.Left == current {
				prev.Left = child
			} else {
				prev.Right = child
			}
		} else {
			self.root = child
		}
	} else {
		// 获取右子树中的最小节点
		tmp := current.Right
		for tmp.Left != nil {
			tmp = tmp.Left
		}
		// 先删除获取到的节点
		self.Remove(tmp.Val)
		// 将获取到的节点重新赋值给待删除的节点
		current.Val = tmp.Val
	}
}

中序遍历有序

二叉搜索树在进行中序遍历时，总是会优先搜索下一个最小节点，这就会导致二叉搜索树的中序遍历序列是升序的。这使得在二叉搜索树中获取有序数据仅需 $O(n)$ 时间，无需进行额外的排序操作。

二叉搜索树效率

二叉搜索树各项操作的时间复杂度都是对数阶，有较稳定且高效的性能。只有在高频添加、低频查找删除数据的场景下，数组比二叉搜索树的效率更高。

操作	无序数组	二叉搜索树
查找元素	$O(n)$	$O(\log n)$
插入元素	$O(1)$	$O(\log n)$
删除元素	$O(n)$	$O(\log n)$

理想情况下，二叉搜索树是平衡的，可以在 $\log n$ 轮查询内找到任意节点。但是，如果在二叉搜索树中不断插入和删除节点，可能会导致树退化为链表，这样各项操作的时间复杂度也会退化到 $O(n)$ 。

二叉搜索树应用场景

系统多级索引
搜索算法的底层数据结构
存储数据流，使其保持有序状态

AVL树

学不动了

红黑树

慢慢啃

堆

堆 heap 是一种满足特定条件的完全二叉树，主要分为两种类型：

小顶堆 min heap：任意节点的值 <= 子节点的值
大顶堆 max heap：任意节点的值 >= 子节点的值

堆做为完全二叉树的特例，具有以下特性：

最底层节点靠右填充，其它层节点都被填满
根节点称为堆顶，底层靠右的节点称为堆底
堆顶元素（跟节点）的值是最大（最小）的

堆常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列，在实际的使用中，可以直接使用编程语言实现的堆类或优先队列类。GO 的 container/heap 包内有堆的实现。

堆的常用操作

方法	描述	时间复杂度
`push()`	元素入堆	$O(\log n)$
`pop()`	堆顶元素出堆	$O(\log n)$
`peek()`	访问堆顶元素	$O(1)$
`size()`	获取堆元素数量	$O(1)$
`isEmpty()`	判断堆是否为空	$O(1)$

堆的实现

由于堆是一种完全二叉树，且完全二叉树非常适合使用数组来表示。所以可以使用数组来存储堆。

先定义堆类，再将树的数组索引映射公式封装为方法

// 可比较类型
type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr | ~float32 | ~float64 | ~string
}

// 大顶堆 如果需要小顶堆 将所有比较操作反向比较即可
type MaxHeap[T Ordered] struct {
	array []T
}

func NewMaxHeap[T Ordered]() *MaxHeap[T] {
	return &MaxHeap[T]{
		array: make([]T, 0),
	}
}

// 获取左子节点
func (self *MaxHeap[T]) left(index int) int {
	return index<<1 + 1
}
// 获取右子节点
func (self *MaxHeap[T]) right(index int) int {
	return index<<1 + 2
}
// 获取父节点
func (self *MaxHeap[T]) parent(index int) int {
	return (index - 1) >> 1
}
func (self *MaxHeap[T]) Size() int {
	return len(self.array)
}
func (self *MaxHeap[T]) IsEmpty() bool {
	return self.Size() == 0
}

需要访问堆顶元素时，直接返回数组的首个元素即可

// 访问堆顶元素
func (self *MaxHeap[T]) Peek() any {
	return self.array[0]
}

当元素入堆时，先将其添加到堆底。添加之后，其 value 可能大于堆中的其它元素，因此需要修复从插入节点到根节点的路径上的各个节点，这个操作称为堆化 heapify 。

考虑从入堆节点开始，从底至顶执行堆化。循环比较插入节点与其父节点的值，如果插入节点更大，则将它们交换。从底至顶修复堆中的各个节点，直至越过根节点或遇到无须交换的节点时结束。

堆化操作的循环次数和树的高度相关联，假设节点总数为 $n$ ，那么树的高度和元素入栈操作的时间复杂度均为 $O(\log n)$ 。

// 元素入堆
func (self *MaxHeap[T]) Push(value T) {
	// 直接添加到堆底
	self.array = append(self.array, value)
	// 从底置顶堆化
	self.siftUp(len(self.array) - 1)
}

func (self *MaxHeap[T]) siftUp(index int) {
	for {
		// 获取当前节点的父节点索引
		parent := self.parent(index)
		// 如果父节点不存在或当前节点小于等于父节点 那么直接跳过
		if parent < 0 || self.array[index] <= self.array[parent] {
			break
		}
		// 交换位置
		self.array[index], self.array[parent] = self.array[parent], self.array[index]
		// 继续向上循环
		index = parent
	}
}

堆顶元素出堆时，如果直接从列表中删除首元素，那么二叉树中所有节点的索引都会发生变化。为了尽量减少元素索引的变动，需要采用其它的删除策略：

交换堆顶元素与堆底元素
交换完成后，将堆底元素删除（此时的堆底是堆顶元素的值）
从根节点开始，从顶至底进行堆化

从顶至底堆化和从底至顶堆化的操作方向相反。需要循环将根节点的值和其两个子节点进行比较，把最大的子节点与根节点交换，知道越过根节点或遇到无须交换的节点时结束。

func (self *MaxHeap[T]) Pop() T {
	if self.IsEmpty() {
		panic("empty heap")
	}
	// 保存堆顶元素
	result := self.array[0]
	lastIndex := self.Size() - 1
	// 交换堆顶和堆底元素
	self.array[0], self.array[lastIndex] = self.array[lastIndex], self.array[0]
	// 删除堆底元素
	self.array = self.array[:lastIndex]
	// 从顶至底堆化
	self.siftDown(0)
	// 返回堆顶值
	return result
}

func (self *MaxHeap[T]) siftDown(index int) {
	for {
		left, right, maxChild := self.left(index), self.right(index), index
		// 判断左子节点是否大于当前节点
		if left < self.Size() && self.array[left] > self.array[maxChild] {
			maxChild = left
		}
		// 判断右子节点是否大于左子节点
		if right < self.Size() && self.array[right] > self.array[maxChild] {
			maxChild = right
		}
		// 如果当前节点 大于子节点 那么直接跳出
		if maxChild == index {
			break
		}
		// 交换当前节点和最大子节点的值
		self.array[index], self.array[maxChild] = self.array[maxChild], self.array[index]
		// 重置 index 为最大子节点的索引 继续下一次循环
		index = maxChild
	}
}

堆的常见应用

优先队列：堆通常作为实现优先队列的首选数据结构，其入队和出队操作时间复杂度均为 $O(\log n)$ ，建堆操作为 $O(n)$ ，都比较高效。
堆排序：使用数组建立堆，然后通过出堆操作得到有序数组
获取最大的 $n$ 个元素

建堆操作

使用一个列表的所有元素创建一个堆，称为建堆操作。建堆操作可以借助入堆操作实现，先创建一个空堆，然后遍历列表，对列表中的每个元素执行入堆操作。

入堆操作的时间复杂度为 $O(\log n)$ ，列表元素数量为 $n$ ，那么建堆操作的时间复杂度为 $O(n \log n)$ 。

此外，还有另一个更高效的办法。先将所有元素按照顺序添加到堆中，然后倒序遍历堆，依次为每个非叶节点执行从顶至底堆化。每当堆化一个节点后，以该节点为根节点的子树就会变成一个合格的子堆。由于是倒叙遍历，堆是从下往上构建的。

// NewMaxHeapByArray 通过列表创建大顶堆
func NewMaxHeapByArray[T Ordered](values []T) *MaxHeap[T] {
	mh := &MaxHeap[T]{
		array: values,
	}
	// 从最后一个叶节点的父节点开始遍历堆化
	for i := mh.parent(len(mh.array) - 1); i >= 0; i-- {
		mh.siftDown(i)
	}
	return mh
}

从输入列表到完成建堆操作的时间复杂度为 $O(n)$ ，比连续入堆操作高效。

Top-k 问题

一个经典问题，给定一个长度为 $n$ 的无序数组 array ，返回数组中最大的 $k$ 个元素。可用的解法非常多，但是效率各不相同。

遍历选择

对数组进行 $k$ 轮遍历，在每轮中提取出对应轮数最大的元素，时间复杂度为 $O(nk)$ ，当 $n$ 和 $k$ 接近时，时间复杂度接近 $O(n^{2})$ ，比较耗时。

排序选择

先对数组 array 进行排序，在返回最大的 $k$ 个元素，时间复杂度为 $O(\log n)$ 。但是排序会对数组中所有的元素都进行排序，但是题目只需要找出最大的 $k$ 个元素，不需要排序其它元素。

堆选择

先初始化一个小顶堆，其堆顶元素最小，再将数组的前 $k$ 个元素依次入堆，从 $k+1$ 个元素开始。若当前元素大于堆顶元素，就将堆顶元素出堆，当前元素入堆。当遍历完成后，堆中保存的就是最大的 $k$ 个元素。

// 使用堆查找数组中最大的 k 个元素
func topKHeap(nums []int, k int) []int {
	// 初始化一个小顶堆
	mh := NewMinHeap[int]()
	// 将前 k 个元素添加到堆中
	for i := 0; i < k; i++ {
		mh.Push(nums[i])
	}
	// 如果之后的元素大于堆顶元素 那么堆顶元素出堆 当前元素入堆
	for i := k; i < len(nums); i++ {
		if nums[i] > mh.Peek() {
			mh.Pop()
			mh.Push(nums[i])
		}
	}
	// 直接返回堆中的底层数组
	return mh.array
}

总共执行了 $n$ 轮入堆和出堆，堆的最大长度为 $k$ ，因此时间复杂度为 $O(n \log k)$ 。当 $k$ 较小时接近 $O(n)$ ；当 $k$ 较大时，最大也不会超过 $O(n \log n)$ 。

小结

堆是一棵完全二叉树，根据成立条件可分为大顶堆和小顶堆。大（小）顶堆的堆顶元素是最大（小）的。
优先队列的定义是具有出队优先级的队列，通常使用堆来实现。
堆的常用操作及其对应的时间复杂度包括：元素入堆 $O(\log n)$ 、堆顶元素出堆 $O(\log n)$ 和访问堆顶元素 $O(1)$ 等。
完全二叉树非常适合用数组表示，因此通常使用数组来存储堆。
堆化操用于维护堆的性质，经常使用在入堆和出堆操作中。
输入 $n$ 个元素并建堆的时间复杂度可以优化至 $O(n)$ 。
Top-k 是一个经典算法问题，可以使用堆数据结构高效解决，时间复杂度为 $O(n \log k)$ 。

图

图 Graph 是一种非线性数据结构，由顶点 vertex 和边 edge 组成。可以将图抽象表示为一组顶点和一组边的集合。

如果将顶点看作节点，边看作连接各个节点的引用，就可以把图看作一种从链表扩展而来的数据结构。相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高，也更为复杂。

图的常见类型

根据边是否具有方向，可分为无向图 undirected graph 和有向图 derected graph。

在无向图中，边表示顶点之间的双向连接关系，例如好友关系
在有向图中，边具有方向性，不同方向的边是独立的，例如关注于被关注关系

根据所有顶点是否连通，可分为连通图 connected graph 和非连通图 disconnected graph。

连通图中从某个顶点出发，可以到达其余任意顶点
在非连通图中，从某个顶点出发，至少有一个顶点无法到达

此外，还可以通过给图的边添加权重属性来得到有权图 weighted graph 。

图数据结构通常包含以下术语：

邻接 adjacency：当两个顶尖之间存在边相连时，称这两顶点邻接
路径 path：从一个顶点到另一个顶点经过的边所构成的序列称为路径
度 degree：一个顶点拥有的边数。对于有向图，入度 in-degree 表示有多少条边执行该顶点，出度 out-degree 表示有多少条边从该顶点指出

图的表示

图的常用表示方式包括邻接矩阵和邻接表。

邻接矩阵

设图的顶点数量为 $n$ ，邻接矩阵 adjacency matrix 使用 $n * n$ 大小的矩阵表示图，每一列或者行都可以代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。

设邻接矩阵为 $M$ 、顶点列表为 $V$ ，那么当矩阵元素 $M[i,j] = 1$ 表示顶点 $V[i]$ 到顶点 $V[y]$ 之间存在边，反之则不存在。

// 顶点列表 1 3 2 5 4
// 无论行还是列 表达的意义都是相同的
// 顶点1的索引为0 顶点3的索引为1  matrix[0][1] == 1所以 matrix[1, 3] == 1 
// 也就说明顶点1到顶点3之间存在边，反之顶点1到顶点4之间就不存在边
matrix := [][]int {
		{ 0, 1, 1, 1, 0 }, // 表示顶点1所拥有的边
		{ 1, 0, 1, 0, 0 }, // 表示顶点2所拥有的边
		{ 1, 1, 0, 1, 1 },
		{ 1, 0, 1, 0, 1 },
		{ 0, 0, 1, 1, 0 },
	}

邻接矩阵具有以下特性：

顶点不能与自身相连，因此邻接矩阵对角线元素没有意义
对于无向图，两个方向的对等边，此时邻接矩阵关于主对角线对称
将邻接矩阵的元素从 1 和 0 替换为权重，即可表示有权图

使用邻接矩阵表示图时，可以直接访问矩阵元素以获取边，因此增删改查的效率很高，时间复杂度均为 $O(1)$ 。但是空间复杂度为 $O(n^{2})$ ，比较耗费内存。

邻接表

邻接表 adjacency list 使用 $n$ 个链表来表示图，链表节点表示节点。每一个链表都对应一个顶点，其中存储了改顶点的所有邻接节点。

邻接表仅存储实际存在的边，相较于邻接矩阵更节省空间，但是需要通过遍历链表来查找边，时间效率不如邻接矩阵。

邻接表结构与哈希表中的链式地址相似，也可以采用类似的优化方法来提升效率。比如当链表较长时，将链表转化为红黑树或 AVL 树，从而将时间效率提升至 $O(\log n)$ 。

图的常见应用

场景	顶点	边	解决问题
社交网	用户	好友关系	好友推荐
交通线路	站点	站点间的连通性	最短线路推荐

图的基础操作

图的基础操作克分为对边的操作和对顶点的操作。

基于邻接矩阵实现

添加或删除边：直接在邻接矩阵中修改指定的边即可，使用 $O(1)$ 时间，注意需要同时修改两个方向的边
添加顶点：在邻接矩阵的尾部添加一行一列，并全部填 0 ，使用 $O(n)$ 时间
删除顶点：在邻接矩阵中删除一行一列，最差情况下使用 $O(n^{2})$ 时间
初始化：初始化顶点列表使用 $O(n)$ 时间，初始化邻接矩阵使用 $O(n^{2})$ 时间

type GraphAdjacencyMatrix struct {
	vertices []int   // 顶点列表
	adjMat   [][]int // 邻接矩阵
}

func NewGraphAdjacencyMatrix(vertices []int, edges [][]int) *GraphAdjacencyMatrix {
	// 初始化矩阵
	length := len(vertices)
	adjMat := make([][]int, length)
	for i := range adjMat {
		adjMat[i] = make([]int, length)
	}
	// 初始化图
	g := &GraphAdjacencyMatrix{
		vertices: vertices,
		adjMat:   adjMat,
	}
	// 添加边
	for i := range edges {
		g.AddEdge(edges[i][0], edges[i][1])
	}
	return g
}

func (self *GraphAdjacencyMatrix) Size() int {
	return len(self.vertices)
}

// AddVertex 添加顶点
func (self *GraphAdjacencyMatrix) AddVertex(value int) {
	self.vertices = append(self.vertices, value)
	// 在矩阵中添加一行
	newRow := make([]int, self.Size())
	self.adjMat = append(self.adjMat, newRow)
	// 为矩阵中的每一行再添加一列
	for i := range self.adjMat {
		self.adjMat[i] = append(self.adjMat[i], 0)
	}
}

// RemoveVertex 删除顶点
func (self *GraphAdjacencyMatrix) RemoveVertex(index int) {
	if index < 1 || index >= self.Size() {
		return
	}
	// 从顶点列表中移除
	self.vertices = append(self.vertices[:index], self.vertices[index+1:]...)
	// 从矩阵行中移除
	self.adjMat = append(self.adjMat[:index], self.adjMat[index+1:]...)

	// 在矩阵的每一列中移除
	for i := range self.adjMat {
		self.adjMat[i] = append(self.adjMat[i][index:], self.adjMat[i][index+1:]...)
	}

}

func (self *GraphAdjacencyMatrix) AddEdge(i, j int) {
	// 判断元素索引是否合法
	if i < 0 || j < 0 || i >= self.Size() || j >= self.Size() || i == j {
		return
	}
	// 在无向图中，邻接矩阵关于对角线对称 即 (i,j) == (j,i)
	// 将元素设置为1
	self.adjMat[i][j] = 1
	self.adjMat[j][i] = 2
}

func (self *GraphAdjacencyMatrix) RemoveEdge(i, j int) {
	// 判断元素索引是否合法
	if i < 0 || j < 0 || i >= self.Size() || j >= self.Size() || i == j {
		return
	}
	// 将元素设置为0
	self.adjMat[i][j] = 0
	self.adjMat[j][i] = 0
}

基于邻接表实现

设无向图的顶点总数为 $n$ 、边总数为 $m$

添加边：在顶点对应链表的末尾添加即可，使用 $O(1)$ 时间，无向图需要同时添加两个方向的边。
删除边：在顶点对应链表中删除边，使用 $O(m)$ 时间，无向图需要同时删除两个方向的边
添加顶点：在邻接表中添加一个链表，将新增节点作为链表头节点，使用 $O(1)$ 时间
删除顶点：遍历整个链表，删除顶点和包含该顶点的所有边，使用 $O(n+m)$ 时间
初始化：在邻接表中创建 $n$ 个顶点和 $2m$ 边，使用 $O(n+m)$ 时间

为了简化实现，使用列表代替链表，使用哈希表来存储邻接表

type GraphAdjacencyList struct {
	list map[int][]int
}

func NewGraphAdjacencyList(edges [][]int) *GraphAdjacencyList {
	g := &GraphAdjacencyList{
		list: make(map[int][]int),
	}
	for _, edge := range edges {
		g.AddVertex(edge[0])
		g.AddVertex(edge[1])
		g.AddEdge(edge[0], edge[1])
	}
	return g
}

func (self *GraphAdjacencyList) Size() int {
	return len(self.list)
}

// AddEdge 添加边
func (self *GraphAdjacencyList) AddEdge(vet1, vet2 int) {
	// 判断两个顶点是否存在
	_, ok1 := self.list[vet1]
	_, ok2 := self.list[vet2]
	if !ok1 || !ok2 || ok1 == ok2 {
		return
	}
	// 无向图需要分别添加边
	self.list[vet1] = append(self.list[vet1], vet2)
	self.list[vet2] = append(self.list[vet2], vet1)
}

// RemoveEdge 删除边
func (self *GraphAdjacencyList) RemoveEdge(vet1, vet2 int) {
	// 判断两个顶点是否存在
	_, ok1 := self.list[vet1]
	_, ok2 := self.list[vet2]
	if !ok1 || !ok2 || ok1 == ok2 {
		return
	}
	// 删除 vet1 -> vet2 的边 无向图中需要双向删除
	// 借助slices包的函数
	self.list[vet1] = slices.DeleteFunc(self.list[vet1], func(item int) bool {
		return item == vet2
	})

	self.list[vet2] = slices.DeleteFunc(self.list[vet2], func(item int) bool {
		return item == vet1
	})
}

// AddVertex 添加顶点
func (self *GraphAdjacencyList) AddVertex(vet int) {
	if _, ok := self.list[vet]; ok {
		return
	}
	// 初始化列表
	self.list[vet] = make([]int, 0)
}

// RemoveVertex 删除顶点
func (self *GraphAdjacencyList) RemoveVertex(vet int) {
	if _, ok := self.list[vet]; !ok {
		return
	}
	// 删除顶点
	delete(self.list, vet)
	// 遍历删除顶点中所有和被删除节点有关的边
	for key, value := range self.list {
		self.list[key] = slices.DeleteFunc(value, func(item int) bool {
			return item == vet
		})
	}
}

效率对比

设无向图的顶点总数为 $n$ 、边总数为 $m$

操作	邻接矩阵	邻接表（链表）	邻接表（哈希表）
判断是否邻接	$O(1)$	$O(m)$	$O(1)$
添加边	$O(1)$	$O(1)$	$O(1)$
删除边	$O(1)$	$O(m)$	$O(1)$
添加顶点	$O(n)$	$O(1)$	$O(1)$
删除顶点	$O(n^{2})$	$O(n+m)$	$O(n)$
内存占用	$O(n^{2})$	$O(n+m)$	$O(n+m)$

图的遍历

图的遍历方式也分为两种，广度优先遍历和深度优先遍历

广度优先遍历

广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。

func GraphBfs(graph *GraphAdjacencyList, root int) []int {
	// 返回列表
	res := make([]int, 0)
	// map 判断顶点是否已经在返回列表中存在
	hashed := make(map[int]struct{})
	hashed[root] = struct{}{}

	// Bfs通常通过队列来实现
	queue := list.New()
	// 当前顶点入队
	queue.PushBack(root)

	for queue.Len() > 0 {
		element := queue.Front()
		// 出队
		queue.Remove(element)
		vet := element.Value.(int)
		res = append(res, vet)
		// 获取当前顶点的邻接节点
		for _, adjVet := range graph.list[vet] {
			if _, ok := hashed[adjVet]; ok {
				continue
			}
			// 将为访问过的节点添加到队列中
			queue.PushBack(adjVet)
			hashed[adjVet] = struct{}{}
		}
	}
	return res
}

时间复杂度：所有顶点都会入队出队一次，在遍历邻接顶点是，由于是无向图，所有边都会被访问两次。

深度优先遍历

深度优先遍历和树的深度优先遍历一致，都需要先走到底，通常使用递归来实现。

func GraphDfs(graph *GraphAdjacencyList, root int) []int {
	res := make([]int, 0)
	hashed := make(map[int]struct{})
	dfs(graph, hashed, &res, root)
	return res
}

func dfs(graph *GraphAdjacencyList, hashed map[int]struct{}, res *[]int, vet int) {
	// 添加顶点
	*res = append(*res, vet)
	hashed[vet] = struct{}{}
	// 获取当前顶点的邻接顶点
	for _, adjVet := range graph.list[vet] {
		// 判断是否被访问 如果没有那么递归调用
		if _, ok := hashed[adjVet]; !ok {
			dfs(graph, hashed, res, adjVet)
		}
	}
}

时间复杂度：所有的顶点都会被访问一次，所有的边都会被访问两次

小结

搜索

二分查找

二分查找 binary search 是一种基于分治策略的高效搜索算法。利用数据的有序性，每轮缩小一半的搜索范围，直至找到目标元素或区间为空为止。在二分循环中，搜索区间每轮缩小一半，因此时间复杂度为 $O(\log n)$ 。在搜索时，区间的索引使用常数空间大小，空间复杂度为 $O(1)$ 。

type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr | ~float32 | ~float64 | ~string
}

// 二分查找 （双闭区间）
func BinarySearch[T Ordered](array []T, target T) int {
	// 获取双闭区间的开始和结束索引
	start, end := 0, len(array)-1
	// 循环 当搜索区间为空时结束
	for start <= end {
		// 获取搜索区间中点元素索引
		mIndex := start + (end-start)>>1
		// 如果小于 那么区间的起始索引为中点 + 1 反之则结束索引为中点 - 1
		if array[mIndex] < target {
			start = mIndex + 1
		} else if array[mIndex] > target {
			end = mIndex - 1
		} else {
			return mIndex
		}
	}
	return -1
}

二分查找在时间和空间方面都有较好的性能，查询的时间效率高并且无需额外空间。但是，二分查找也并非适用于所有情况，仅适用于有序数据和数组，并且在小数据量下，线性查找性能更好。

二分查找插入点

不存在重复元素的情况下，当数组包含待插入的值时，插入点的索引就是该值的索引；不包含时，因此 start 指向首个大于待插入值的元素，直接返回 start 作为插入索引。

func BinarySearchInsert[T Ordered](array []T, target T) int {
	start, end := 0, len(array)-1
	for start <= end {
		mIndex := start + (end-start)>>1
		if array[mIndex] < target {
			start = mIndex + 1
		} else if array[mIndex] > target {
			end = mIndex - 1
		} else {
			// 若在区间中找到了target 那么直接返回
			return mIndex
		}
	}
	// 返回插入点 start
	return start
}

存在重复元素时，如果需要将待插入元素插入到最左边，那么先找到任意一个 target 索引，然后向左线性遍历，直到找到最左边的 target 。

func BinarySearchInsert[T Ordered](array []T, target T) int {
	start, end := 0, len(array)-1
	for start <= end {
		// 当元素大于和等于 target 时，都继续向左
		mIndex := start + (end-start)>>1
		if array[mIndex] < target {
			start = mIndex + 1
		} else {
			end = mIndex - 1
		}
	}
	// 返回插入点 start
	return start
}

二分查找边界

当需要在一个包含重复元素的有序数组中查找某一个 target 最左或最右的索引时，也可以使用二分查找。其查找操作和上面的重复复元素查找插入点类似，可以直接复用。

func BinarySearchLeftEdge[T Ordered](array []T, target T) int {
	// 查找最左边的插入索引
	index := BinarySearchInsert[T](array, target)
	// 判断是不是等于 target
	if index >= len(array) || array[index] != target {
		return -1
	}
	return index
}

查找右边界有两种方法，第一种是在二分查找时反方向收缩指针

if array[mIndex] > target {
	start = mIndex -1
} else {
	end = mIndex - 1
}

第二种是复用查找有边界的方法，查找 target + 1 的元素。当查找完成时，start 将指向最左一个 target + 1 （如果存在），而 end 将指向最右一个 target。

func BinarySearchRightEdge[int](array []int, target int) int {
	// 查找 target + 1
	index := BinarySearchInsert[int](array, target + 1)
	end := index - 1
	if end < 0 || array[end] != target {
		return -1
	}
	return index
}

哈希优化策略

可以通过将线性查找替换为哈希查找来降低时间复杂度，以某个经典算法题为例

给定一个整数数组 nums 和一个目标元素 target ，找出数组中和为 target 的两个元素，并返回它们的数组索引。

线性查找，通过双层循环暴力枚举查找，以时间换空间。时间复杂度为 $O(n^{2})$ ，在数据量很大的情况下非常耗时！

func TwoSumBruteForce(nums []int, target int) []int {
	size := len(nums)
	for i := 0; i < size-1; i++ {
		for y := i + 1; y < size; y++ {
			if nums[i]+nums[y] == target {
				return []int{i, y}
			}
		}
	}
	return nil
}

通过哈希表优化之后，可以将时间复杂度降低至 $O(n)$ ，但时空间复杂度也提升至 $O(n)$ ，是典型的以空间换时间解法。

func TwoSumHash(nums []int, target int) []int {
	hashed := make(map[int]int)
	for index, value := range nums {
		// 判断是否在哈希表中存在
		if preIndex, ok := hashed[target-value]; ok {
			return []int{index, preIndex}
		}
		// 不存在那么添加进哈希表
		hashed[value] = index
	}
	return nil
}

搜索算法

搜索算法 searching algorithm 用于在数据结构中搜索一个或一组满足特定条件的元素。

通过遍历数据结构来获取目标元素：例如数组、链表、树和图的遍历
高效元素查找：例如二分查找、哈希查找和二叉搜索树查找等

暴力搜索

暴力搜索通过遍历数据结构的每个元素来进行查找。优点是简单且通用性好，无需对数据进行预处理或借助额外的数据结构，缺点是时间复杂度为 $O(n)$ ，不适合数据量较大的情况。

线性查找适用于数组和链表等数据结构
广度优先搜索和深度优先搜索适用于图和树等数据结构

自适应搜索

自适应搜索利用数据的特有属性（有序性等）来优化搜索过程，优点是效率高，时间复杂度可达 $O(\log n)$ 或 $O(q)$ ，缺点是往往需要对数据进行预处理或需要借助额外的数据结构，例如哈希表。

二分查找：利用数据的有效性进行查找，适用于数组
哈希查找：利用哈希表进行查找
树查找：在特定的树结构中进行查找

搜索方法选取

操作	线性搜索	二分查找	树查找	哈希查找
查找元素	$O(n)$	$O(\log n)$	$O(\log n)$	$O(1)$
插入元素	$O(1)$	$O(n)$	$O(\log n)$	$O(1)$
删除元素	$O(n)$	$O(n)$	$O(\log n)$	$O(1)$

排序

选择排序

选择排序 selection sort 的工作原理是每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

// SelectionSort 选择排序
func SelectionSort[T Ordered](array []T) {
	size := len(array)
	for i := 0; i < size-1; i++ {
		// 记录最小元素的索引
		minIndex := i
		for y := i + 1; y < size; y++ {
			// 如果小于 那么重新赋值索引
			if array[y] < array[minIndex] {
				minIndex = y
			}
		}
		// 交换当前元素和最小元素的位置
		array[i], array[minIndex] = array[minIndex], array[i]
	}
}

时间复杂度为 $O(n^{2})$ ，非自适应排序。空间复杂度为 $O(1)$ ，原地排序，无需借助额外空间。

冒泡排序

冒泡排序 bubble sort 通过连续比较和交换相邻元素实现排序。

// BubbleSort 冒泡排序
func BubbleSort[T Ordered](array []T) {
	size := len(array)
	for i := size - 1; i > 0; i-- {
		for y := 0; y < i; y++ {
			// 如果当前元素大于后一个元素
			if array[y] > array[y+1] {
				// 那么交换位置
				array[y], array[y+1] = array[y+1], array[y]
			}
		}
	}
}

时间复杂度为 $O(n^{2})$ ，自适应排序。空间复杂度为 $O(1)$ ，原地排序。

插入排序

插入排序 insertion sort 是一种简单的排序算法，原理是在未排序区间选择一个元素，将该元素与其左侧已排序区间的元素逐一比较大小，并插入到正确的位置。

// InsertionSort 插入排序
func InsertionSort[T Ordered](array []T) {
	for i := 1; i < len(array); i++ {
		// 基准值
		base := array[i]
		y := i - 1
		for y >= 0 && array[y] > base {
			array[y+1] = array[y]
			y--
		}
		array[y+1] = base
	}
}

时间复杂度为 $O(n^{2})$ ，自适应排序。空间复杂度为 $O(1)$ ，原地排序。

在数据量较小的情况下，插入排序通常更快。并且在实际情况中，插入排序的使用频率高于冒泡排序和选择排序。

快速排序

算法流程

快速排序 quick sort 是基于分治策略的排序算法。快排的核心操作是选取数组中的某个元素做为基准数，将所有小于基准数的元素移至左侧，大于基准数的元素移到右侧。划分完成后，原数组被分为三部分：左子数组、基准数、右子数组，且满足左子数组任意元素 $\le$ 基准数 $\le$ 右子数组任意元素。后续对两个子数组继续递归执行划分操作，直到子数组的长度为1时终止。

// QuickSort 快速排序
func QuickSort[T Ordered](array []T, left, right int) {
	// 指针相遇 子数组长度为1是跳出
	if left >= right {
		return
	}
	// 划分并获取基准数下标
	index := partition(array, left, right)
	// 递归排序左子树
	QuickSort(array, left, index-1)
	// 递归排序右子树
	QuickSort(array, index+1, right)
}

// 快速排序划分
func partition[T Ordered](array []T, left, right int) int {
	// 首尾指针 以 left 索引元素做为基准数
	start, end := left, right
	for start < end {
		// 从右向左查找第一个小于基准数的元素
		for start < end && array[end] >= array[left] {
			end--
		}
		// 从左向右查找第一个大于基准数的元素
		for start < end && array[start] <= array[left] {
			start++
		}
		// 交换这两个元素 使其小于的在左边 大于的在右边
		array[start], array[end] = array[end], array[start]
	}
	// 循环结束后 start 和 end 指针会相遇 start指针指向的是小于基准数的元素
	// 当基准数和该元素交换后 基准数的两侧就是左子树和右子树 且满足 左子树 <= 基准数 <= 右子树
	array[start], array[left] = array[left], array[start]
	// 返回基准数的下标
	return start
}

特性

时间复杂度为 $O(n \log n)$ ，非自适应排序。空间复杂度为 $O(n)$ 原地排序。快速排序虽然平均时间复杂度与归并排序和堆排序相同，但通常效率更高。

出现最差情况的概率很低：快速排序的最差时间复杂度为 $O(n^{2})$ ，但只会在极少的情况下出现。
缓存使用效率高：在进行划分时，系统会将整个子数组加入缓存
复杂度的常熟系数小：比较、赋值、交换等操作的总数量最小

优化

快速排序在基准数选取不佳的情况下时间效率可能降低，为此可以优化划分中基准数的选取策略。可以数组中选取三个元素做为候选元素（通常中首、中、尾三个元素），取这三个元素的中位做为基准数。

l, m, r := array[left], array[(left+right)>>1], array[right]
// 选取基准数
var media int
if (l <= m && r >= m) || (r <= m && l >= m) {
	media = (left + right) >> 1
} else if (m <= l && r >= l) || (r <= l && m >= l) {
	media = left
} else {
	media = right
}
// 将基准数交换到最左侧
array[left], array[media] = array[media], array[left]

此外，为了防止递归操作时栈帧空间积累，还可以进行尾递归优化。在每轮划分完成后，仅对长度较短的子数组进行递归。

// QuickSort 快速排序 尾递归优化
func QuickSort[T Ordered](array []T, left, right int) {
	// 指针相遇 子数组长度为1是跳出
	for left < right {
		// 划分并获取基准数下标
		index := partition(array, left, right)
		// 对较短的子数组进行排序
		if index-left < index-right {
			// 递归排序左子数组
			QuickSort(array, left, index-1)
			// 剩余未排序区间 [index + 1, right]
			left = index + 1
		} else {
			// 递归排序右子数组
			QuickSort(array, index+1, right)
			// 剩余未排序区间 [left, index - 1]
			right = index - 1
		}
	}
}

归并排序

归并排序 merge sort 也是一种基于分治策略的排序方法，主要分为划分和合并两个阶段。

划分：通过递归不断将数组从中点分开，将长数组的排序问题转化为短数组的排序问题
合并：当子数组长度为1时开始合并，持续将左右两个较短的有序数组合并为一个有序数组

// MergeSort 归并排序
func MergeSort[T Ordered](array []T, left, right int) {
	if left <= right {
		return
	}
	mid := left + (right-left)>>1
	// 先划分
	MergeSort(array, left, mid)
	MergeSort(array, mid+1, right)
	// 再合并
	merge(array, left, mid, right)
}

// 归并排序的辅助合并方法
func merge[T Ordered](array []T, left, mid, right int) {
	// 创建一个临时数组 存储合并完成后的有序数据
	temp := make([]T, right-left+1)
	// 获取左子数组的、右子数组的起始索引和临时数组的赋值索引
	leftIndex, rightIndex, index := left, mid+1, 0
	// 左子数组和右子数组都没处理完的情况下才执行
	// 加入某一侧的子数组被处理完 那么另一侧的数组已经说有序的了 直接拼接在临时数组中即可
	for leftIndex <= mid && rightIndex <= right {
		// 哪一侧的元素较小 就往临时数组中添加哪一侧的元素 并将对应一侧的子数组索引加一 用于访问下一个元素
		if array[leftIndex] <= array[rightIndex] {
			temp[index] = array[leftIndex]
			leftIndex++
		} else {
			temp[index] = array[rightIndex]
			rightIndex++
		}
		// 挨个往临时数组中添加元素
		index++
	}
	// 将左右两侧子数组的剩余元素复制到临时数组中
	for leftIndex <= mid {
		temp[index] = array[leftIndex]
		index++
		leftIndex++
	}
	for rightIndex <= right {
		temp[index] = array[rightIndex]
		index++
		rightIndex++
	}
	// 将临时数组中的元素复制到 array 对应的区间
	for i, item := range temp {
		array[left+i] = item
	}
}

时间复杂度为 $O(n \log n)$ ，非自适应排序。空间复杂度为 $O(n)$ ，非原地排序。

堆排序

堆排序 heap sort 是一种基于数据结构的排序算法。可以利用建立小顶堆和元素出堆操作实现，但是这种实现方式需要借助一个额外的数组来保存弹出的元素，比较浪费内存。

一种比较优雅的实现方式是先建立一个大顶堆，将堆底和堆顶元素交换，交换完成后，将堆的长度减1并执行从顶到底堆化操作。此时，堆的性质得以修复并且以排序的元素数量加1。上述操作重复执行 $n-1$ 轮后，便得到了一个排序后的数组。

时间复杂度为 $O(n \log n)$ ，非自适应排序。空间复杂度为 $O(1)$ ，原地排序。

桶排序

桶排序 bucket sort 通过设置一些具有具体大小的桶，每个桶对应一个数据范围，将数据对应的分配到各个桶中。然后，在每个桶中分别执行排序，最后按照桶的顺序将数据合并。

// BucketSort 桶排序 假设nums只包含 1-500 之内的数据
func BucketSort(nums []int) {
	// 分成5个桶 每个桶分别存储 0-100 100-200 的数据 以此类推
	buckets := make([][]int, 5)
	// 初始化桶
	for i := range buckets {
		buckets[i] = make([]int, 0)
	}
	// 平均分配元素
	for _, value := range nums {
		index := value / 100
		buckets[index] = append(buckets[index], value)
	}
	// 分别堆桶内的元素进行排序
	for i := range buckets {
		// 借助 sort 包内的排序函数
		sort.Ints(buckets[i])
	}
	index := 0
	// 合并桶内的元素到原数组
	for _, bucket := range buckets {
		for _, value := range bucket {
			nums[index] = value
			index++
		}
	}
}

桶排序适用于处理量很大的数据，当内存无法一次性加载所有数据时，可以将数据分为若干个桶分别进行排序，排序完成之后再合并。桶排序的时间复杂度为 $O(n+k)$ ， $k$ 为桶的数量，当桶数量较大时，时间复杂度将接近 $O(n)$ 。空间复杂度为 $O(n+k)$ ，非原地排序。

达到桶排序的最佳时间复杂度的关键就是尽可能的将元素均匀分配到各个桶中。

计数排序

计数排序 counting sort 通过统计元素数量实现排序，通常适用于正整形数组和数据量大且数据范围小的情况。

// CountingSort 计数排序
func CountingSort(nums []uint) {
	// 获取数组中最大的元素
	var maxNum uint
	for _, num := range nums {
		if num > maxNum {
			maxNum = num
		}
	}
	// 创建一个 maxNum + 1 的空数组
	counter := make([]int, maxNum+1)
	// 遍历待排序的数组 使用value做为下标 在空数组中执行自增操作
	for _, num := range nums {
		counter[num]++
	}
	index := 0
	// 数组下标天然有序 只需要遍历新增的数组 将值大于0的下标复制到原数组即可
	// 双重循环是因为一个数字可能出现多次
	for i, value := range counter {
		for y := 0; y < value; y++ {
			nums[index] = uint(i)
			index++
		}
	}
}

时间复杂度 $O(n + m)$ ，非自适应排序。空间复杂度 $O(n+m)$ ，非原地排序。

小结

	时间复杂度	空间复杂度	稳定性	就地性	自适应性	基于比较
选择排序	最佳 $O(n^{2})$ 平均 $O(n^{2})$ 最差 $O(n^{2})$	$O(1)$	非稳定	原地	非自适应	是
冒泡排序	最佳 $O(n)$ 平均 $O(n^{2})$ 最差 $O(n^{2})$	$O(1)$	稳定	原地	自适应	是
插入排序	最佳 $O(n)$ 平均 $O(n^{2})$ 最差 $O(n^{2})$	$O(1)$	稳定	原地	自适应	是
快速排序	最佳 $O(n \log n)$ 平均 $O(n \log n)$ 最差 $O(n^{2})$	$O(\log n)$	非稳定	原地	非自适应	是
归并排序	最佳 $O(n \log n)$ 平均 $O(n \log n)$ 最差 $O(n \log n)$	$O(n)$	稳定	非原地	非自适应	是
堆排序	最佳 $O(n \log n)$ 平均 $O(n \log n)$ 最差 $O(n \log n)$	$O(1)$	非稳定	原地	非自适应	是
桶排序	最佳 $O(n+k)$ 平均 $O(n+k)$ 最差 $O(n^{2})$	$O(n+k)$	稳定	非原地	非自适应	否
计数排序	最佳 $O(n+m)$ 平均 $O(n+m)$ 最差 $O(n+m)$	$O(n+m)$	稳定	非原地	非自适应	否

分治

分治算法

分治 divide and conquer ，全程分而治之，是一种常见且重要的算法策略。分治通常使用递归实现，包括分和治两个步骤。

分（划分阶段）：递归地将原问题划分为小问题，直至达到最小问题时终止。
治（合并阶段）：从最小问题开始，从第至顶将子问题的解进行合并，从而得到原问题的解

判断一个问题是否适合使用分治解决，主要有以下几点

问题可以分解
子问题是独立的
子问题的解可以合并

分治除了可以解决算法问题，还能提升算法的效率，最重要的两点就是：

操作数量优化
并行计算优化

分治搜索策略

时间复杂度为 $O(\log n)$ 的搜索算法通常是基于分治策略实现的，比如二分查找和树。前面搜索章节中的二分算法是其余迭代来实现的，但是二分查找也可以基于分治来实现。

func dfs(array []int, target, left, right int) int {
	// 如果搜索区间为空 那么返回 -1
	if left > right {
		return -1
	}
	// 计算中点索引
	mid := left + (right-left)>>1
	if array[mid] < target {
		// 如果中点元素小于目标元素 那么递归搜索右子数组
		return dfs(array, target, mid+1, right)
	} else if array[mid] > target {
		// 大于则搜索左子数组
		return dfs(array, target, left, mid-1)
	} else {
		// 找到元素 返回中点索引
		return mid
	}
}

// BinarySearch 递归版本的二分搜索
func BinarySearch(nums []int, target int) int {
	return dfs(nums, target, 0, len(nums)-1)
}

构建树问题

给定一颗二叉树的前序遍历 preorder 和中序遍历 inorder，请从中构建二叉树，返回二叉树的根节点。

原问题定义为从 preorder 和 inorder 构建二叉树，是一个典型的分治问题。

问题可以分解：将原问题划分为两个子问题：构建左子树、构建右子树。
子问题是独立的：左子树和右子树是互相独立的。
子问题的解可以合并：得到了左子树和右子树后，就可以将它们链接到根节点。

假设树的前序遍历值为 [3, 9, 2, 1, 7] ，中序遍历值为 [9, 3, 1, 2, 7]。那么根据前序遍历的特性可以得知树的根节点为 3 ，再根据 3 在中序遍历中的索引位置，可以将中序遍历分割为 [9 | 3 | 1, 2, 7] ，这样就得到了树的左子树和右子树元素数量。再通过中序遍历的元素数量可以将前序遍历划分为 [3 | 9 | 1, 2, 7] （因为左子树的元素数量为1）。这样就可以完整的得出根节点、左子树、右子树在 preorder 和 inorder 中的索引区间。

设当前树根节点在 reorder 中的索引为 $i$ 、在 inorder 中的索引为 $m$ ；树在 inorder 中的索引区间为 $[l, r]$

	根节点在 `preorder` 中的索引	子树在 `inorder` 中的索引
当前树	$i$	$[l, r]$
左子树	$i+1$	$[l, m-1]$
右子树	$i+1+(m-l)$	$[m+1,r]$

// BuildTree 通过前序遍历和中序遍历构建二叉树
func BuildTree[T comparable](preOrder, inOrder []T) *TreeNode[T] {
	inOrderMap := make(map[T]int)
	for index, value := range inOrder {
		inOrderMap[value] = index
	}
	root := dfsBuildTree(preOrder, inOrderMap, 0, 0, len(inOrder)-1)
	return root
}

// 分治递归构建树
func dfsBuildTree[T comparable](preOrder []T, inOrderMap map[T]int, i, l, r int) *TreeNode[T] {
	// 子树区间为空
	if l > r {
		return nil
	}
	// 从 preorder 中获取根节点
	root := NewTreeNode(preOrder[i])
	// 从inorder中获取根节点的索引 用于区分左右子树
	// 这里使用 map 加快搜索速度
	m := inOrderMap[preOrder[i]]
	// 递归创建左子树
	root.Left = dfsBuildTree(preOrder, inOrderMap, i+1, l, m-1)
	// 递归创建右子树
	root.Right = dfsBuildTree(preOrder, inOrderMap, i+1+m-l, m+1, r)
	return root
}

汉诺塔问题

给定三个名称为 A、B、C 的柱子。初始状态下，柱子 A 上面套着 n 个圆盘，按照从上到下从小到大的顺序排列。需要把这 n 个圆盘移到 C 柱上，并保存原有顺序不变。在移动过程中，需要遵循以下规则：

只能从一根柱子顶部拿出，从另一根柱子顶部放入

每次只能移动一个圆盘

小圆盘必须时刻位于大圆盘上面

将大小为 $i$ 的汉诺塔问题设为 $f(i)$ 。对于 $f(1)$ 即只有一个圆盘时，直接将它从 A 移动到 C 即可；对于 $f(2)$ ，有两个圆盘时，由于需要满足小圆盘时刻在大圆盘之上，需要借助 B 来辅助完成，具体步骤为：

先将小圆盘从 A 移动到 B
再将大圆盘从 A 移到 C
最后将小圆盘从 B 移到 C

过程可以总结为将两个圆盘借助 B 从 A 移动到 C。此时，C 称为目标柱、B 称为缓冲柱、。

对于 $f(3)$ ，可以从分治的角度思考，分为两次 $f(2)$ 和一次 $f(1)$ 来解决

设 B 为目标柱，借助 C 将上面两个圆盘从 A 移到 B
将 A 中剩余的圆盘移到 C
设 C 为目标柱，借助 A 将 B 上的两个圆盘移到 C

得到的分治策略为：将原问题 $f(n)$ 划分为两个子问题 $f(n-1)$ 和一个子问题 $f(1)$ ，并按照如下顺序运行：

将 $n-1$ 个圆盘借助 C 从 A 移到 B
将剩余 $1$ 个圆盘从 A 移到 C
将 $n-1$ 个圆盘借助 A 从 B 移到 C

// SolveHanota 处理汉诺塔问题
func SolveHanota(a, b, c *list.List) {
	dfsHanota(a.Len(), a, b, c)
}

// 递归汉诺塔问题
func dfsHanota(size int, src, buf, tar *list.List) {
	// 当圆盘只剩下一个时，直接移动
	if size == 1 {
		move(src, tar)
		return
	}
	// 子问题 f(n-1) 借助 tar 将 src 移动到 buf
	dfsHanota(size-1, src, tar, buf)
	// 直接移动剩下的一个圆盘
	move(src, tar)
	// 子问题 f(n-1) 借助 src 将 buf 移动到 tar
	dfsHanota(size-1, buf, src, tar)
}

// 移动圆盘
func move(src, tar *list.List) {
	// 从 src 顶部拿出一个圆盘
	element := src.Back()
	// 将圆盘放到 tar 顶部
	tar.PushBack(element.Value)
	src.Remove(element)
}

汉诺塔形成一颗高度为 n 的递归树，每个节点对应一个子问题，因此时间复杂度为 $O(n^{2})$ ，空间复杂度为 $O(n)$ 。

回溯

回溯算法

回溯算法 backtracking algorithm 是一种通过穷举来解决问题的方法。核心思想是从一个初始状态出发，暴力搜素可能的解决方法，当遇到正确的解则将其记录，直至找到解或者尝试完所有的可能为止。

回溯算法通常采用深度优先搜索来遍历解空间。

给定一颗二叉树，记录所有值为 target 的节点，并返回节点列表

func SearchTree[T comparable](root *TreeNode[T], target T, result *[]*TreeNode[T]) {
	// 如果根节点为空 直接返回
	if root == nil {
		return
	}
	// 如果节点值等于目标值 那么添加到结果列表中
	if root.Val == target {
		*result = append(*result, root)
	}
	// 搜索左子树
	SearchTree(root.Left, target, result)
	// 搜索右子树
	SearchTree(root.Right, target, result)
}

尝试与回退

回溯算法在搜索解空间时会采用尝试与回退策略。当算法在搜索过程中遇到某个状态无法继续或者无法得到解时，会撤销上一步的选择，退回到之前的状态，并尝试其它可能的选择。

在二叉树中记录所有值为 target 的节点，返回跟节点到这些节点的路径

func SearchTreeWithPath[T comparable](root *TreeNode[T], target T, result *[][]*TreeNode[T], path *[]*TreeNode[T]) {
	if root == nil {
		// 回退
		return
	}
	// 添加访问路径
	*path = append(*path, root)
	if root.Val == target {
		// 复制一份访问路径 将副本添加到结果列表中
		cloned := slices.Clone(*path)
		*result = append(*result, cloned)
	}
	SearchTreeWithPath(root.Left, target, result, path)
	SearchTreeWithPath(root.Right, target, result, path)
	// 删除访问路径中的当前节点 恢复到本次尝试之前的状态
	*path = (*path)[:len(*path)-1]
}

可以将尝试与回退理解为前进与撤销，两个操作互为逆向。

剪枝

复杂的回溯问题通常包括一个或多个约束条件，约束条件通常用于剪枝。剪枝是为了过滤掉不满足约束条件的搜索分支。

在二叉树中记录所有值为 target 的节点，返回跟节点到这些节点的路径，要求路径中不包含值为 filter 的节点

func SearchTreeByFilter[T comparable](root *TreeNode[T], target, filter T, result *[][]*TreeNode[T], path *[]*TreeNode[T]) {
    // 判断是否满足约束条件 如果不满足那么剪枝
	if root == nil || root.Val == filter {
		return
	}
	// 添加访问路径
	*path = append(*path, root)
	if root.Val == target {
		// 复制一份访问路径 将副本添加到结果列表中
		cloned := slices.Clone(*path)
		*result = append(*result, cloned)
	}
	SearchTreeWithPath(root.Left, target, result, path)
	SearchTreeWithPath(root.Right, target, result, path)
	// 删除访问路径中的当前节点
	*path = (*path)[:len(*path)-1]
}

常用术语

名词	定义
解 `solution`	满足问题特定条件的答案，可能有一个或多个
约束条件 `constraint`	限制解可行性的条件，通常用于剪枝
状态 `state`	问题在某一时刻的情况，包括已经做出的选择
尝试 `attempt`	根据可用选择来尝试解空间的过程，包括做出选择、更新状态、检查是否为解
回退 `backtracking`	遇到不满足约束条件的状态时，撤销前面做出的选择，回到上一状态
剪枝 `pruning`	根据问题特性和约束条件避免无意义的搜索路径

全排列问题

全排列问题是回溯算法的一个典型应用。定义是在给定一个集合的情况下，找出其中元素的所有可能排列组合。

给定一个整数数组，其中不包含重复元素，返回所有可能的排列

从回溯算法的角度看，可以把生成排列的过程想象成一系列选择的结果。候选集合 choices 是输入数组中的所有元素，状态 state 是截止目前已经被选择的元素，但是每个元素只允许被选择一次，所以 state 中的元素都应该是唯一的。

func Permutations(nums []int) [][]int {
	state := make([]int, 0)
	selected := make([]bool, len(nums))
	result := make([][]int, 0)
	backtrack(&state, &nums, &selected, &result)
	return result
}

// 回溯算法 全排列
func backtrack(state *[]int, choices *[]int, selected *[]bool, result *[][]int) {
	// 如果状态的长度等于元素数量时 说明当前选择已经成立
	// 可以往结果中记录解了
	if len(*state) == len(*choices) {
		newState := slices.Clone(*state)
		*result = append(*result, newState)
	}
	// 遍历所有选择
	for i := range *choices {
		// 剪枝条 如果当前下标的元素已经被选择 那么直接开启下一轮循环
		if (*selected)[i] {
			continue
		}
		num := (*choices)[i]
		// 做出选择 更新状态
		*state = append(*state, num)
		(*selected)[i] = true
		// 开启下一轮选择
		backtrack(state, choices, selected, result)
		// 回退 撤销选择 恢复到之前的状态
		*state = (*state)[:len(*state)-1]
		(*selected)[i] = false
	}
}

如果考虑数组中包含重复元素的情况，那么还需要在每一轮选择中借助哈希表记录已经尝试过的元素，并将重复元素剪枝。

// 回溯算法 全排列 包含重复元素
func backtrackByRepeat(state *[]int, choices *[]int, selected *[]bool, result *[][]int) {
	// 如果状态的长度等于元素数量时 说明当前选择已经成立
	// 可以往结果中记录解了
	if len(*state) == len(*choices) {
		newState := slices.Clone(*state)
		*result = append(*result, newState)
	}
	hashed := make(map[int]struct{})
	// 遍历所有选择
	for i := range *choices {
		num := (*choices)[i]
		// 剪枝 不允许重复选择元素 不允许重复选择相等元素
		if _, ok := hashed[num]; !ok && !(*selected)[i] {
			// 做出选择 更新状态
			hashed[num] = struct{}{}
			*state = append(*state, num)
			(*selected)[i] = true
			// 开启下一轮选择
			backtrack(state, choices, selected, result)
			// 回退 撤销选择 恢复到之前的状态
			*state = (*state)[:len(*state)-1]
			(*selected)[i] = false
		}
	}
}

虽然 selected 和 hashed 都用于剪枝，但目标不同：

重复选择剪枝：整个搜索过程只有一个 selected ，记录的是当前状态中包含哪些元素，避免某个元素在 state 重复出现。
相等元素剪枝：每轮选择都包含一个 hashed ，目的是确保相等的元素只会被选择一次。

子集和问题

给定一个正整数数组 nums 和一个目标正整数 target ，请找出所有可能的组合，使得组合中的元素和等于 target 。给定数组无重复元素，每个元素可以被选取多次。请以列表形式返回这些组合。

由于集合中的元素可以无限被选取，所以无需使用 selected 记录被使用过的元素。

// 求子集和
func subsetSumINaive(nums []int, target int) [][]int {
	state := make([]int, 0)
	total := 0
	result := make([][]int, 0)
	backtrackSubsetSumINaive(total, target, &state, &nums, &result)
	return result
}

func backtrackSubsetSumINaive(total, target int, state, choices *[]int, result *[][]int) {
	// 如果当前和等于 target 那么直接将子集添加到结果中
	if total == target {
		newState := slices.Clone(*state)
		*result = append(*result, newState)
		return
	}
	// 遍历每一种选择
	for i := range *choices {
		sum := (*choices)[i] + total
		// 如果大于那么剪枝
		if sum > target {
			continue
		}
		// 添加状态
		*state = append(*state, (*choices)[i])
		backtrackSubsetSumINaive(sum, target, state, choices, result)
		// 回退状态
		*state = (*state)[:len(*state)-1]
	}
}

这样虽然可以找出所有和为 target 的子集，但是结果中会存在重复的子集。为了去除重复子集，一种思路是对结果列表进行去重，另一种就是在搜索过程中剪枝进行去重。

由于对结果列表去重效率非常低，所以直接考虑使用剪枝进行去重。

// 求子集和 去重子集版本
func subsetSumINaiveSort(nums []int, target int) [][]int {
	state := make([]int, 0)
	result := make([][]int, 0)
    // 先对数组进行排序 这样 start 之后的元素一定会比当前元素大
    // 例如 [3,4] 的子集出现后 再从 4 开始搜索是不会搜索到 3 的
    // 一定不会再出现 [4,3] 子集
	sort.Ints(nums)
	backtrackSubsetSumINaiveSort(0, target, &state, &nums, &result)
	return result
}

func backtrackSubsetSumINaiveSort(start, target int, state, choices *[]int, result *[][]int) {
	// 当 target == 0 时 说明已经找到解
	if target == 0 {
		newState := slices.Clone(*state)
		*result = append(*result, newState)
		return
	}
	// 遍历每一种选择
	for i := start; i < len(*choices); i++ {
		if target-(*choices)[i] < 0 {
			// 直接直接跳出 因为数组是经过排序的 后面的元素只会更大
			break
		}
		*state = append(*state, (*choices)[i])
		// 继续搜索后面的元素 此时的 target 应该是减去当前元素后的大小
		backtrackSubsetSumINaive(i, target-(*choices)[i], state, choices, result)
		*state = (*state)[:len(*state)-1]
	}
}

如果给定数组中包含重复元素，并且题目要求每个元素只可被访问一次，也可以通过剪枝操作来实现

// 包含重复元素的求子集和， choices 需要先排序
func backtrackSubsetSumINaiveNotRepeat(start, target int, state, choices *[]int, result *[][]int) {
	// 当 target == 0 时 说明已经找到解
	if target == 0 {
		newState := slices.Clone(*state)
		*result = append(*result, newState)
		return
	}
	// 遍历每一种选择
	for i := start; i < len(*choices); i++ {
		if target-(*choices)[i] < 0 {
			// 直接直接跳出 因为数组是经过排序的 后面的元素只会更大
			break
		}
		// 如果当前索引大于 start 并且当前元素和上一个元素相等 那么符合剪枝条件
		if i > start && (*choices)[i] == (*choices)[i-1] {
			continue
		}
		*state = append(*state, (*choices)[i])
		// 继续搜索后面的元素 此时的 target 应该是减去当前元素后的大小
		// 此时的索引需要加 1 ，因为每个元素只能出现一次
		backtrackSubsetSumINaive(i+1, target-(*choices)[i], state, choices, result)
		*state = (*state)[:len(*state)-1]
	}
}

动态规划

动态规划 dynamic programming 是一个重要的算法范式，将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

DP问题

给定一个共有 $n$ 阶的楼梯，你每步可以上 1 阶或者 2 阶，请问有多少种方案可以爬到楼顶？

可以使用回溯来穷举所有的可能性

// ClimbingStairsBacktrack 爬楼梯回溯解法
// num 楼梯的阶数
// nums 每次可以爬的阶数
func ClimbingStairsBacktrack(num int, nums []int) int {
	var res int
	backtrack(0, num, nums, &res)
	return res
}

func backtrack(state, target int, nums []int, res *int) {
	// 当爬的阶数等于楼梯的阶数时 将解加 1
	if state == target {
		*res++
		return
	}
	for i := range nums {
		// 如果已经爬过的阶数加上当前准备爬的阶数大于目标阶数
		// 那么直接剪枝
		if nums[i]+state > target {
			continue
		}
		backtrack(state+nums[i], target, nums, res)
	}
}

暴力搜索

回溯算法通常并不显式的对问题进行拆解，而是将求解问题看作一系列决策步骤，通过试探和剪枝，搜索出所有可能的解。

假设爬到第 $i$ 阶共有 $dp[i]$ 种方案，由于每轮只能上 1 阶或者 2 阶，那么爬到第 $i -1$ 阶的方案数加上爬到第 $i-2$ 阶的方案数就等于爬到 $i$ 阶的方案数，即 $dp[i] = dp[i - 1] + dp[i - 2]$ 。可以根据递推公式得到暴力搜索解法，以 $dp[n]$ 为起点，递归的将一个较大问题拆解为两个较小问题的和，直至到达最小问题 $dp[1]$ 和 $dp[2]$ 时返回。

// ClimbingStairs 爬楼问题 暴力搜索
func ClimbingStairs(num int) int {
	return dfs(num)
}

func dfs(i int) int {
    // 一次只能爬 1 阶或者 2 阶，dp[1]或者dp[2]
	if i == 1 || i == 2 {
		return i
	}
    // dp[i] = dp[i - 1] + dp[i - 2]
	return dfs(i-1) + dfs(i-2)
}

对于问题 $dp[n]$ ，其递归树的深度为 $n$ ，时间复杂度为 $O(2^{n})$ 。如果是一个比较大的 $n$ ，那么等待的时间会非常久。其指数阶的时间复杂度是重叠子问题引起的。例如 $dp[]9$ 被分解为 $dp[8]$ 和 $dp[7]$ ， $dp[8]$ 会继续分解为 $dp[7]$ 和 $dp[6]$ ，这其中都包含了 $dp[7]$ 这个子问题。

记忆化搜索

为了提升算法效率，可以记录每个子问题的结果，不再结算每个重复的子问题。

// 缓存优化版
func ClimbingStairsDFSMem(num int) int {
	cache := make([]int, num+1)
	for i := range cache {
		cache[i] = -1
	}
	return dfsMem(num, cache)
}

func dfsMem(i int, cache []int) int {
	if i == 1 || i == 2 {
		return i
	}
	// 先从结果集中获取 判断该子问题是否已经被计算
	if cache[i] != -1 {
		return cache[i]
	}
	total := dfs(i-1) + dfs(i-2)
	// 将子问题的计算结果保存到结果集中
	cache[i] = total
	return total
}

经过了优化处理后，所有的重复子问题只需要计算一次，时间复杂度优化至 $O(n)$ 。

动态规划

记忆化搜素是一种从顶至底的方法，递归的将较大子问题分解为较小子问题，直至已知的最小子问题。之后再通过回溯逐层收集子问题的解，构建出原问题的解。

而动态规划是一种从底至顶的方法，从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。

func ClimbingStairsDP(num int) int {
	if num == 1 || num == 2 {
		return num
	}
    // 初始化dp表 存储子问题的解
	dp := make([]int, num+1)
	dp[1] = 1
	dp[2] = 2
    // 从较小子问题逐步求解较大子问题
	for i := 3; i <= num; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[num]
}

同时，由于这里的解只和 $[i-1]$ 和 $[i-2]$ 有关。无需使用数组保存所有解的结果。

func ClimbingStairsDP(num int) int {
	if num == 1 || num == 2 {
		return num
	}
	a, b := 1, 2
	for i := 3; i <= num; i++ {
		a, b = b, a+b
	}
	return dp[num]
}

这样优化后，空间复杂度从 $O(n)$ 下降到了 $O(1)$ 。

在动态规划中，当前状态往往仅与前面有限个状态有关，这时可以只保留必要的状态。这种空间优化技巧称作滚动变量或滚动数组。

DP问题特性

子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点各有不同。

分治算法递归的将原问题划分为多个项目独立的子问题，直至最小问题，并在回溯中合并子问题的解，最终得到原问题的解
动态规划也对问题进行递归分解，但是子问题是相互依赖的，在分解过程中会出现许多重叠子问题
回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支

最优子结构

给定一个楼梯，每步可以上 1 阶或者 2 阶，每一阶楼梯上都有一个非负整数，表示在该阶楼梯需要付出的代价。给定一个非负整数数组 cost ，其中 cost[i] 表示在 i 阶楼梯需要付出的代价，cost[0] 为地面。算出最少需要多少代价才能到达顶部。

设 $dp[i]$ 为爬到第 $i$ 阶楼梯累计付出的代价，由于第 $i$ 阶只能从 $i-1$ 或者 $i-2$ ，而为了尽可能的减少代价，应该选择较小的那一个

$dp[i] = min(dp[i-1], dp[1-2]) + cost[i]$

这便是最优子结构的含义：原问题的最优解是从子问题的最优解构建而来的

func MinCostClimbingStairsDP(cost []int) int {
	n := len(cost) - 1
	if n == 1 || n == 2 {
		return cost[n]
	}
    // dp表 存储子问题的解
	dp := make([]int, len(cost))
    // 预设的最小子问题的解
	dp[1] = cost[1]
	dp[2] = cost[2]
	for i := 3; i <= len(cost); i++ {
		dp[i] = minInt(dp[i-1], dp[i-2]) + cost[i]
	}
	return dp[n]
}
func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}

也可以进行空间优化，将空间复杂度为 $O(n)$ 降至 $O(1)$ 。

func MinCostClimbingStairsDP(cost []int) int {
	n := len(cost) - 1
	if n == 1 || n == 2 {
		return cost[n]
	}
    // 使用滚动变量进行空间优化
	a, b := cost[1], cost[2]
	for i := 3; i <= len(cost); i++ {
		temp := b
		b = minInt(a, b) + cost[i]
		a = temp
	}
	return b
}

无后效性

无后效性是动态规划能有效解决问题的重要特性之一，其定义为：给定一个明确的状态，它的未来发展之和当前状态有关，与过去经历的所有状态无关。

以之前的爬楼梯为例，给定状态 $i$ ，它会发展出 $i+1$ 和 $i+2$ ，在做这两种选择时，无需考虑 $i$ 之前的状态。

DP解题思路

问题判断

如果一个问题包含重复子问题、最优子结构、并满足无后效性，那么通常适合使用动态规划来求解。为了检查问题是否满足这些特性，通常会先判断问题是否适合使用回溯穷举解决。

适合回溯解决的问题通常满足决策树模型，这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。

在此基础上，还有一些适合使用动态规划解决问题的判断依据：

问题包含最大（多）或最小（少）等最优化描述
问题的状态能够使用列表、多维矩阵或树来表示，并且一个状态和周围的状态存在递推关系。

也有不适用使用的判断依据：

问题的目标是找出所有可能的解决方案，而不是找出最优解
问题描述中有明显的排列组合的特征，需要返回具体的多个方案

问题求解步骤

以最小路径和问题为例

给定一个 $n×m$ 的二维网格 grid ，网格中的每个单元格包含一个非负整数，表示该单元格的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。请返回从左上角到右下角的最小路径和。

第一步：思考每轮的决策，定义状态，从而得到 $dp$ 表

设当前格子的索引为 $dp[x,y]$ ，向下或向右走一步后变为 $dp[x+1,y]$ 或 $dp[x,y+1]$ 。因此，状态应包含行索引和列索引两个变量，记为 $[x,y]$ 。

状态 $[x,y]$ 对应的子问题为从：从起始点 $[0,0]$ 到 $[x,y]$ 的最短路径和，解记为 $dp[x,y]$ 。

第二步：找出最优子结构，进而推导出状态转移方程

对于状态 $[x,y]$ ，它只能从状态 $[x-1,y]$ 或 $[x,y-1]$ 得来，进而推导出的状态转移公式为： $dp[x,y]=min(dp[x-1,y], dp[x,y-1]) + cost[x,y]$ 。

第三步：确定边界和条件执行顺序

由于状态只能从其左边或上边得来，且必须以左上角单元格为起来，那么 $x=0$ 和 $y=0$ 就是边界条件。对于状态转移，使用循环来遍历矩阵，外循环遍历行，内循环遍历列。

暴力搜索

从状态 $[x,y]$ 开始搜索，不断拆分为更小的 $[x-1, y]$ 和 $[x,y-1]$ 子问题。

// 最小路径和 暴力搜索解法
func MinPathSumDfs(grid [][]int, x, y int) int {
	if x == 0 && y == 0 {
		return grid[0][0]
	}
	// 当某一行或某一列越界后 返回无穷大
	// 表示 剪枝 不会选择这条路
	if x < 0 || y < 0 {
		return math.MaxInt32
	}
	// 两个选择 分别是 [x-1, y] 和 [x, y-1]
	upSum := MinPathSumDfs(grid, x-1, y)
	leftSum := MinPathSumDfs(grid, x, y-1)
	// 最终解等于可选择的最小路径 + 当前单元格的代价
	return min(leftSum, upSum) + grid[x][y]
}

暴力搜索同样回造成重叠子问题，因为有多条路径可以从左上角访问到同一单元格。

记忆化搜索

引入记忆列表，对子问题的解进行记录，对重叠子问题进行剪枝

// 最小路径和 记忆化搜索
func MinPathSumMemDfs(grid [][]int, mem []int, x, y int) int {
	if x == 0 && y == 0 {
		return grid[0][0]
	}
	// 当某一行或某一列越界后 返回无穷大
	// 表示不会选择这条路
	if x < 0 || y < 0 {
		return math.MaxInt32
	}
	// 计算此单元格在列表 mem 中的索引
	cellIndex := x*(len(grid[0])) + y
	if mem[cellIndex] != -1 {
		return mem[cellIndex]
	}
	// 两个选择 分别是 [x-1, y] 和 [x, y-1]
	upSum := MinPathSumMemDfs(grid, mem, x-1, y)
	leftSum := MinPathSumMemDfs(grid, mem, x, y-1)
	// 最终解等于可选择的最小路径 + 当前单元格的代价
	num := min(leftSum, upSum) + grid[x][y]
	// 将问题的就解记忆起来
	mem[cellIndex] = num
	return num
}

动态规划

func MinPathSumDP(grid [][]int) int {
	l, m := len(grid), len(grid[0])
	// 初始化dp表
	ans := make([][]int, l)
	for i := range ans {
		ans[i] = make([]int, m)
	}
	// 初始化首行和首列
	ans[0][0] = grid[0][0]
	// 状态转移 首行
	for i := 1; i < m; i++ {
		ans[0][i] = ans[0][i-1] + grid[0][i]
	}
	// 状态转移 首列
	for i := 1; i < l; i++ {
		ans[i][0] = ans[i-1][0] + grid[i][0]
	}
	//对其余行和列做状态转移
	for i := 1; i < l; i++ {
		for j := 1; j < m; j++ {
			// 当前这一步永远是上一步的最优解
			ans[i][j] = min(ans[i-1][j], ans[i][j-1]) + grid[i][j]
		}
	}
	// 返回最终的步数
	return ans[l-1][m-1]
}

由于需要遍历整个网格且 $dp$ 表需要保存每一步的结果，所以时间和空间复杂度均为 $O(nm)$ 。

空间优化

由于某个格子之和其左边和上边的格子有关，可以使用一个当行数组来充当 $dp$ 表。

func MinPathSumOnlyDP(grid [][]int) int {
	l, m := len(grid), len(grid[0])
	dp := make([]int, m)
	dp[0] = grid[0][0]
	// 初始化首行元素
	for i := 1; i < m; i++ {
		dp[i] = dp[i-1] + grid[0][i]
	}
	//对其余行和列做状态转移
	for i := 1; i < l; i++ {
		// 网格中每换一次行 就对dp表中的首个元素重新赋值
		// 其余元素都还是上一行的结果
		dp[0] = dp[0] + grid[i][0]
		for j := 1; j < m; j++ {
			// 当前这一步永远是上一步的最优解
			dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
		}
	}
	// 返回最终的步数
	return dp[m-1]
}

优化后空间复杂度降至 $O(m)$ 。

01背包问题

背包问题是动态规划中最常见的问题形式，具有很多种变种，比如01背包问题、完全背包问题、多重背包问题等。

给定 $n$ 个物品，第 $i$ 个物品的重量和价值分别为 $wight[i-1]$ 、 $value[i-1]$ ，和一个容量为 $cap$ 的背包。每个物品只能选择一次，求在限定背包容量小所能放入物品的最大价值。

将01背包看作一个 $n$ 轮决策组成的过程，对于某个物品都有放入和不放入两种决策，因此满足决策树模型。

暴力搜索

// 01背包问题 暴力搜索
func knapsackDFS(weight, value []int, index, c int) int {
	// 如果背包容量已满或已遍历完物品列表 那么直接返回0
	if index == len(value)+1 || c == 0 {
		return 0
	}
	// 如果当前物品的重量大于背包所剩的容量 那么无法放入
	if weight[index-1] > c {
		return knapsackDFS(weight, value, index+1, c)
	}
	// 物品放入背包的总价值
	no := knapsackDFS(weight, value, index+1, c)
	// 物品不放入背包的总价值
	yes := knapsackDFS(weight, value, index+1, c-weight[index-1]) + value[index-1]
	// 返回最大价值
	return max(no, yes)
}

动态规划

对于每个物品来说，不放入背包，背包容量不变；放入背包，背包容量减小。由此可得状态定义：当前物品编号 $i$ 和背包容量 $c$ ，记为 $[i,c]$ 。

状态 $[i,c]$ 对应的子问题是：前 $i$ 个物品在容量为 $c$ 的背包中的最大价值，记为 $dp[i,c]$ 。其状态转移公式为

$dp[i,c] = \max(dp[i-1,c], dp[i-1,c-weight[i-1]] + value[i-1])$

待求解的是 $dp[n,cap]$ ，因此需要一个尺寸为 $(n+1) * (cap+1)$ 的二维 $dp$ 表。

// 01背包问题 DP
func knapsackDP(weight, value []int, c int) int {
   size := len(weight)
   // 创建dp表
   dp := make([][]int, size+1)
   // 初始化dp表的每一行
   for i := range dp {
   	dp[i] = make([]int, c+1)
   }
   for i := 1; i <= size; i++ {
   	for y := 1; y <= c; y++ {
   		// 如果当前物品的重量在dp表中还不存在 那么直接赋值
   		if weight[i-1] > y {
   			dp[i][y] = dp[i-1][y]
   		} else {
   			// 最大价值
   			dp[i][y] = max(dp[i-1][y], dp[i-1][y-weight[i-1]]+value[i-1])
   		}
   	}
   }
   return dp[size][c]
}

时间和空间复杂度都为数组 dp 大小决定，即 $O(n*cap)$ 。

空间优化

每个状态都只与其上一行的状态有关，可以使用两个数组滚动前进 + 倒序遍历来将空间复杂度从 $O(n^{2})$ 降至 $O(n)$ 。

// 01背包问题 DP 空间优化
func knapsackDPComp(weight, value []int, c int) int {
	size := len(weight)
	// 初始化 dp 表
	dp := make([]int, c+1)
	// 状态转移
	for i := 1; i <= size; i++ {
		// 倒序遍历
		for y := c; y >= 1; y-- {
			if weight[i-1] <= y {
				dp[y] = max(dp[y], dp[y-weight[i-1]]+value[i-1])
			}
		}
	}
	return dp[c]
}

完全背包问题

完全背包问题和 0-1背包问题基本一致，只是每个元素可以重复选取，同样是求能放入物品的最大价值。

在完全背包问题的规定下，状态 $[i,c]$ 的变化分为两种情况：

不放入物品 $i$ ：与 0-1 背包相同，转移至 $[i-1, c]$
放入物品：与 0-1 背包不同，转移至 $[i, c-weight[i-1]]$

那么，状态转移方程变为：

$dp[i,c] = \max(dp[i-1, c], dp[i, c-weight[i-1]] + value[i-1])$

// 完全背包问题 DP
func unboundedKnapsackDP(weight, value []int, c int) int {
	size := len(weight)
	dp := make([][]int, size+1)
	for i := range dp {
		dp[i] = make([]int, c+1)
	}
	for i := 1; i <= size; i++ {
		for y := 1; y <= c; y++ {
			if weight[i-1] > y {
				dp[i][y] = dp[i-1][y]
			} else {
				// 使用新的状态转移公式
				dp[i][y] = max(dp[i-1][y], dp[i][y-weight[i-1]]+value[i-1])
			}
		}
	}
	return dp[size][c]
}

由于当前状态是从左边和上边的状态转移而来，因此空间优化应该对 $dp$ 表中的每一行进行正序遍历。

// 完全背包 DP 空间优化
func unboundedKnapsackDPComp(weight, value []int, c int) int {
	size := len(weight)
	dp := make([]int, c+1)
	for i := 1; i <= size; i++ {
		for y := 1; y <= c; y++ {
			if weight[i-1] <= y {
				dp[y] = max(dp[y], dp[y-weight[i-1]]+value[i-1])
			}
		}
	}
	return dp[c]
}

编辑距离问题

编辑距离，也称 Levenshtein 距离，指两个字符串之间互相转换的最少修改次数，通常用于在信息检索和自然语言处理中度量两个序列的相似度。

学不懂后面补

贪心

贪心算法 greedy algorithm 是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。

贪心和动态规划都用于解决优化问题，但工作原理不同：

动态规划会根据之前的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解
贪心算法不会考虑之前的决策，而是一路向前不断贪心选择，直至找到问题的解

给定 $n$ 种硬币，第 $i$ 种硬币的面值为 $coins[i -1]$ ，目标金额为 $amt$ ，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。如果无法凑出，返回 -1

// 硬币兑换 贪心版本
func coinChangeGreedy(coins []int, amt int) int {
	// 假设coins是有序的 获取面值最大的硬币的索引
	index := len(coins) - 1
	// 兑换需要的硬币数
	var count int
	// 循环直到要兑换的金额归零
	for amt > 0 {
		// 找到小于当前金额的最大硬币
		for index > 0 && coins[index] > amt {
			index--
		}
		// 将金额减去选中的硬币面值
		amt -= coins[index]
		// 硬币数 + 1
		count++
	}
	// 如果当前金额不为0 说明无法兑换 返回 -1
	if amt != 0 {
		return -1
	}
	// 返回硬币数
	return count
}

贪心算法的优点和局限性

贪心算法操作直接、实现简单，通常效率也比较高。然而，对于有些硬币面值组合，贪心并不能找到最优解。

$coins=[1,20,50]$ ：假设 $amt=60$ ，贪心只能找到 $50+1*10$ 的兑换组合，而动态规划可以找到 $20*3$ 。
$coins=[1,49,50]$ ：假设 $amt=98$ ，贪心只能找到 $50+1*49$ 的兑换组合，而动态规划可以找到 $49*2$ 。

也就是说，对于零钱兑换问题，贪心算法无法保证找到全局最优解，并且有可能找到非常差的解。这种问题更适合用动态规划解决。

一般情况下，贪心算法的适用情况分以下两种：

可以保证找到最优解
可以找到近似最优解

贪心算法特性

贪心选择性质：只有当局部最终选择始终可以导致全局最优解时，贪心算法才可以保证找到最优解
最优子结构：原问题的最优解包含子问题的最优解

贪心算法解题步骤

贪心问题的解决流程大致可以概括为：先梳理与理解问题特性，包括状态定义、优化目标和约束条件等；再确定如何在每一步中做出贪心选择；最后需要证明问题具有贪心选择性质和最佳子结构。

确定贪心策略是求解问题的核心步骤，但实施起来考虑的问题有很多：

不同问题的贪心策略的差异较大
某些贪心策略具有较强的迷惑性

为了保证答案的正确性，应当对探测策略进行严谨的数学证明，通常需要用到反证法或数学归纳法。

贪心典型例题

硬币找零问题
区间调度问题
分数背包问题
股票买卖问题
霍夫曼编码
Dijkstra算法

分数背包问题

给定 $n$ 个物品，第 i 个物品的重量为 $weight[i−1]$ 、价值为 $value[i−1]$ ，和一个容量为 $cap$ 的背包。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，问在限定背包容量下背包中物品的最大价值。

分数背包问题和 0-1 背包问题很相似，不同点在于，分数背包允许选择物品的一部分。可以对物品任意的进行切分，并按照重量比例来计算价值。

对于物品 $i$ ，它在单位重量下的价值为 $value[i-1] / weight[i-1]$ ，简称单位价值
假设放入一部分物品 $i$ ，重量为 $w$ ，那么背包增加的价值为 $w * (value[i-1] / weight[i-1])$ 。

最大化背包物品内总价值，本质上是最大化单位重量下的物品价值，由此可以确定贪心策略：

将物品按照单位价值从高到低进行排序
遍历所有物品，每轮贪心的选择价值最高的物品
若剩余背包容量不足，则使用当前物品的一部分填满背包

type Item struct {
	Weight int
	Value  int
}

// 分数背包 贪心
func fractionalKnapsack(weights, values []int, size int) float64 {
	// 创建一个物品列表
	items := make([]*Item, len(weights))
	for i := range items {
		items[i] = &Item{Weight: weights[i], Value: values[i]}
	}
	// 将物品按单位价值从高到低排序
	sort.Slice(items, func(i, j int) bool {
		return float64(items[i].Value)/float64(items[i].Weight) > float64(items[j].Value)/float64(items[j].Weight)
	})
	var total float64
	// 遍历物品列表
	for _, item := range items {
		// 判断背包是否能完整装下当前价值最高的物品
		if item.Weight < size {
			total += float64(item.Value)
			size -= item.Value
		} else {
			// 如果装不下 ，取部分物品装满背包
			// 此时背包已满 直接跳出循环
			total += float64(size) * (float64(item.Value) / float64(item.Weight))
			break
		}
	}
	return total
}

除排序之外，在最差情况下，需要遍历整个物品列表，因此时间复杂度为 $O(n)$ 。此外，由于需要一个保存物品列表的额外数组，所以空间复杂度也为 $O(n)$ 。

最大容量问题

输入一个数组 $height$ ，其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。

容器的容量等于高度和宽度的乘积（面积），其中高度由较短的隔板决定，宽度是两个隔板的数组索引之差。

请在数组中选择两个隔板，使得组成的容器的容量最大，返回最大容量。

容器右任意两个隔板围成，因此状态为两个隔板的索引，记为 $[i,y]$ 。容量等于高度乘以宽度，其中高度由短板决定，宽度是两隔板的数组索引之差，设容量为 $cap[i,y]$ ，那么计算公式为：

$cap[i,y]=min(height[i],height[t]) * (j-i)$

贪心策略为：先初始化两端指针，每轮计算当前两个指针之间的容量并取最大值保存，计算完成后，将高度较低的一侧指针向内收缩，直至两指针相遇。

// MaxBucketCap 计算最大容量
func MaxBucketCap(height []int) int {
	// 初始化首位索引和最大容量
	left, right, result := 0, len(height)-1, 0
	for right > left {
		// 计算当前区间的容量
		currentCap := min(height[left], height[right]) * (right - left)
		// 保存最大容量
		result = max(result, currentCap)
		// 移动高度较低的一端
		if height[right] < height[left] {
			right--
		} else {
			left++
		}
	}
	// 返回最大容量
	return result
}

本文使用 CC BY-NC-SA 4.0 许可协议，转载请注明出处