算法笔记(下)

本文我将继续补充上一篇文章还未完成的部分，包括常见的代码手撕、常见库函数等。

常见算法实现的手撕

一、快排

1.基础快排(二路快排)

//基准值为arr[0]的快排
//缺陷：对有序或接近有序数组效率低（退化为 O (n²)）

//写法1
func qsort(arr []int) []int{
    if len(arr)<2{
        return
    }
    pivot := arr[0]
    //这个写法类似与归并排序的写法
    //但是没有原地修改数组，复杂度较高
    //而且创建新数组并没有对原切片的底层数组进行修改，需要显式赋值
    left := []int{}
    right := []int{}
    for i:=1;i<len(arr);i++{
        if arr[i]<pivot{
            left = append(left,arr[i])
        }else{
            right = append(right,arr[i])
        }
    }
    return append(qsort(left),append([]int{pivot},qsort(right)...)...)
}
//写法2
//原地修改数组
func quickSortBasic(arr []int, left int, right int) {
	if left >= right {
		return
	}
	pivot := partition(arr, left, right)
	quickSortBasic(arr, left, pivot-1)
	quickSortBasic(arr, pivot+1, right)
}

func partition(arr []int, left int, right int) int {
    //取出最左元素作为基准值，留出空隙
	pivot := arr[left]
	for left < right {
		for left < right && arr[right] >= pivot {
			right--
		}
        //填补left空隙，留下right空隙
		arr[left] = arr[right]
		for left < right && arr[left] <= pivot {
			left++
		}
        //填补right空隙，留下left空隙
		arr[right] = arr[left]
	}
    //最后一个空隙填充基准值
	arr[left] = pivot
	return left
}

2.随机基准值的快排

//随机基准版
//平均时间复杂度稳定为 O (n log n)

func quickSortRandom(arr []int, left int, right int) {
	if left >= right {
		return
	}
	rand.Seed(time.Now().UnixNano())
	index := rand.Intn(right-left+1) + left
	//得到的基准值下标与最左元素交换位置，就可以复用上面的算法
	arr[index], arr[left] = arr[left], arr[index]
	pivot := partition(arr, left, right)
	quickSortRandom(arr, left, pivot-1)
	quickSortRandom(arr, pivot+1, right)
}

3.三路快排

//由于数组中可能存在许多相等元素
//这些元素排序之后不需要再次参与下一轮排序
//三路快排即是加上等于区，无需再次排序

func quickSortThreeWay(arr []int) {
	if len(arr) < 2 {
		return
	}
	rand.Seed(time.Now().UnixNano())
	threeWay(arr, 0, len(arr)-1)
}

func threeWay(arr []int, left int, right int) {
	if left >= right {
		return
	}

	index := left + rand.Intn(right-left+1)
	arr[left], arr[index] = arr[index], arr[left]
	pivot := arr[left]
	// 分区指针：lt（小于区右边界）、gt（大于区左边界）、i（当前遍历）
	lt, gt, i := left, right, left+1
	for i <= gt {
		if arr[i] < pivot {
			// 当前元素小于基准，交换到小于区
			arr[lt], arr[i] = arr[i], arr[lt]
			lt++
            //这里递增是因为初值arr[lt]是基准值，大小关系已经确定，后续arr[lt]也都是已经处理过的，
            //而arr[gt]并没有处理过，需要不递增i进行检查
			i++
		} else if arr[i] > pivot {
			// 当前元素大于基准，交换到大于区
			arr[gt], arr[i] = arr[i], arr[gt]
			gt--
			// 注意这里i不递增，因为交换过来的元素还没检查
		} else {
			// 当前元素等于基准，直接跳过
			i++
		}
	}
	//[left,lt)和(gt,right]
	threeWay(arr, left, lt-1)
	threeWay(arr, gt+1, right)
}

二、归并排序

1.基础递归的归并排序

//递归版
//先归再并
//这个同样不是在原切片上修改
func mergeSort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	mid := len(arr) / 2
    //归
	arr1 := mergeSort(arr[:mid])
	arr2 := mergeSort(arr[mid:])
    //并
	return merge(arr1, arr2)
}
func merge(arr1 []int, arr2 []int) []int {
	l, r := 0, 0
	res := []int{}
	for l < len(arr1) && r < len(arr2) {
		if arr1[l] < arr2[r] {
			res = append(res, arr1[l])
			l++
		} else {
			res = append(res, arr2[r])
			r++
		}
	}
	res = append(res, arr1[l:]...)
	res = append(res, arr2[r:]...)
	return res
}

2.迭代的归并排序

//从数组长度等于1开始每次增长两倍
//这种写法修改了原切片，无需二次返回
func mergeSortIterative(nums []int) {
	n := len(nums)
	if n <= 1 {
		return
	}

	// 从子数组长度为1开始，逐步扩大到n
	for size := 1; size < n; size *= 2 {
		// 每次合并两个相邻的子数组
		for left := 0; left < n-size; left += 2 * size {
			mid := left + size
			right := mid + size
			if right > n {
				right = n // 处理右边界超出数组长度的情况
			}
			// 合并 [left, mid) 和 [mid, right)
			merged := merge(nums[left:mid], nums[mid:right])
			// 将合并结果复制回原数组
			copy(nums[left:right], merged)
		}
	}
}

3.基于链表的归并排序

type ListNode struct{
    Val int
    Next *ListNode
}
// 对链表进行归并排序
func mergeSortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	// 找到链表中点（快慢指针法）
	mid := findMiddle(head)
	// 拆分链表为两部分
	rightHead := mid.Next
	mid.Next = nil // 切断链表

	// 递归排序左右两部分
	left := mergeSortList(head)
	right := mergeSortList(rightHead)

	// 合并两个有序链表
	return mergeList(left, right)
}

// 查找链表的中点（慢指针最终指向中点前一个节点）
func findMiddle(head *ListNode) *ListNode {
	//这里第二个fast一定要用head.Next
	slow, fast := head, head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

// 合并两个有序链表
func mergeList(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			cur.Next = l1
			l1 = l1.Next
		} else {
			cur.Next = l2
			l2 = l2.Next
		}
		cur = cur.Next
	}
	if l1 != nil {
		cur.Next = l1
	}
	if l2 != nil {
		cur.Next = l2
	}
	return dummy.Next
}

4.多路归并

//多路归并是归并思想的扩展，用于将多个已排序的序列合并为一个有序序列。
//它在算法题中频繁出现（如合并 K 个有序链表 / 数组、外部排序、Top K 问题等），核心是通过高效选择当前最小元素来降低时间复杂度。
//典型应用场景
//1. 合并 K 个升序链表（LeetCode 23）
//与合并数组类似，区别在于元素存储在链表中，需通过 Next 指针移动。堆中存储链表节点，每次弹出最小值节点后，将其 Next 节点入堆（若存在）。
//2. 外部排序（大数据量排序）
//当数据量超过内存容量时，无法一次性加载排序：
//先分块：将数据分成 k 个小文件，分别加载到内存排序，得到 k 个有序小文件（子序列）。
//多路归并：用堆合并 k 个有序小文件，输出到最终文件。
//3. 查找第 K 小元素（多源有序数据）
//例如：从 k 个有序数组中找第 k 小的元素。无需完全合并，只需在多路归并过程中计数，取出第 k 个元素即可（提前终止）。
//4. 生成排序后的数据流
//如多个有序数据流（如日志、传感器数据），需实时输出整体有序的结果，用堆维护当前候选元素，每次输出最小值并补充新元素。

//1. 定义堆元素结构
//堆中需存储元素的值、所在数组的索引（用于定位子序列）、该数组内的元素索引（用于移动指针）：
type Item struct {
    val    int // 元素值
    arrIdx int // 所在数组的索引
    elemIdx int // 该数组内的元素索引
} 

//2. 实现堆接口
//Go 的 container/heap 包要求实现 heap.Interface 接口（Len(), Less(), Swap(), Push(), Pop()）：
// 定义小根堆（按 val 升序）
type MinHeap []Item

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].val < h[j].val } // 小根堆
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// Push：向堆中添加元素（append到末尾，由heap包自动上浮调整）
func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(Item))
}

// Pop：从堆顶移除元素（返回最后一个元素，由heap包自动下沉调整）
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

//3. 多路归并核心逻辑
// 合并 k 个有序数组（每个数组均为升序）
func mergeKArrays(arrays [][]int) []int {
    k := len(arrays)
    if k == 0 {
        return nil
    }

    // 初始化小根堆
    h := &MinHeap{}
    heap.Init(h)

    // 第一步：将每个数组的第一个元素入堆（若数组非空）
    for i := 0; i < k; i++ {
        if len(arrays[i]) > 0 {
            heap.Push(h, Item{
                val:    arrays[i][0],
                arrIdx: i,
                elemIdx: 0,
            })
        }
    }

    // 第二步：循环取堆顶（最小值），并补充下一个元素
    var result []int
    for h.Len() > 0 {
        // 取出当前最小值
        item := heap.Pop(h).(Item)
        result = append(result, item.val)

        // 若当前数组还有下一个元素，入堆
        nextElemIdx := item.elemIdx + 1
        if nextElemIdx < len(arrays[item.arrIdx]) {
            heap.Push(h, Item{
                val:    arrays[item.arrIdx][nextElemIdx],
                arrIdx: item.arrIdx,
                elemIdx: nextElemIdx,
            })
        }
    }

    return result
}
//leetcode23
func mergeKLists(lists []*ListNode) *ListNode {
    h := hp{}
    for _, head := range lists {
        if head != nil {
            h = append(h, head) // 把所有非空链表的头节点入堆
        }
    }
    heap.Init(&h) // 堆化

    dummy := &ListNode{}
    cur := dummy
    for len(h) > 0 { // 循环直到堆为空
        node := heap.Pop(&h).(*ListNode) // 剩余节点中的最小节点
        if node.Next != nil { // 下一个节点不为空
            heap.Push(&h, node.Next) // 下一个节点有可能是最小节点，入堆
        }
        cur.Next = node // 把 node 添加到新链表的末尾
        cur = cur.Next // 准备合并下一个节点
    }
    return dummy.Next
}

type hp []*ListNode
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].Val < h[j].Val } // 最小堆
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(*ListNode)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

三、堆排序

1.递归版堆排序

//堆排序的核心就是实现大顶堆，然后不断去除堆顶元素放到队尾，然后调整堆结构
func heapSort(arr []int) {
	n := len(arr)
	if n <= 1 {
		return
	}
	//建堆，从最后一个个非叶子节点开始
	for i := n/2 - 1; i >= 0; i-- {
		down(arr, i, n)
	}
    //取堆顶元素放到末尾并调整
	for i := n - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		down(arr, 0, i)
	}
}
func down(arr []int, i int, n int) {
	lastIndex := i
	if i*2+1 < n && arr[i*2+1] > arr[i] {
		lastIndex = i*2 + 1
	}
	if i*2+2 < n && arr[i*2+2] > arr[i] {
		lastIndex = i*2 + 2
	}
    //需要下沉
	if lastIndex != i {
		arr[i], arr[lastIndex] = arr[lastIndex], arr[i]
        //继续调整
		down(arr, lastIndex, n)
	}
}

2.迭代版堆排序

// 2. 优化版堆排序（迭代实现下沉，减少递归开销）
func heapSortOptimized(nums []int) {
	n := len(nums)
	if n <= 1 {
		return
	}

	// 1. 构建大顶堆（迭代方式下沉）
	for i := n/2 - 1; i >= 0; i-- {
		sinkOptimized(nums, n, i)
	}

	// 2. 提取堆顶元素并调整堆
	for i := n - 1; i > 0; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		sinkOptimized(nums, i, 0)
	}
}

// 优化版下沉操作（迭代实现，避免递归栈开销）
func sinkOptimized(nums []int, size, i int) {
	for {
		left := 2*i + 1
		right := 2*i + 2
		maxIdx := i

		if left < size && nums[left] > nums[maxIdx] {
			maxIdx = left
		}
		if right < size && nums[right] > nums[maxIdx] {
			maxIdx = right
		}

		if maxIdx == i {
			break // 无需下沉，退出循环
		}

		nums[i], nums[maxIdx] = nums[maxIdx], nums[i]
		i = maxIdx // 继续下沉子节点
	}
}

常见库函数

一、sort 包（排序相关）

//sort.Ints(a []int)：对整数切片升序排序（直接修改原切片）。
sort.Ints(a []int)
nums := []int{3, 1, 2}
sort.Ints(nums) // nums 变为 [1,2,3]

//sort.Slice(a interface{}, less func(i, j int) bool)：自定义排序（适用于任何类型切片）。
sort.Slice(a interface{}, less func(i, j int) bool)
// 对二维切片按第一元素升序、第二元素降序排序
sort.Slice(matrix, func(i, j int) bool {
    if matrix[i][0] == matrix[j][0] {
        return matrix[i][1] > matrix[j][1]
    }
    return matrix[i][0] < matrix[j][0]
})

//sort.Search(n int, f func(int) bool)：二分查找（返回第一个满足 f(i)=true 的索引，适用于有序切片）。
sort.Search(n int, f func(int) bool)
//在有序切片中查找第一个 >= 5 的元素索引
nums := []int{1,3,5,7}
idx := sort.Search(len(nums), func(i int) bool { return nums[i] >=5 }) // idx=2

二、字符串操作

//strings 包

//strings.Split(s, sep string) []string：按分隔符切割字符串。
parts := strings.Split("a,b,c", ",") // ["a","b","c"]

strings.Fields(s string) []string//按空格分割字符串

//strings.Join(parts []string, sep string) string：拼接字符串切片。
s := strings.Join([]string{"a","b"}, "-") // "a-b"

strings.Contains(s, substr string) bool//判断是否包含子串。

strings.Index(s, substr string) int//查找子串首次出现的索引（-1 表示不存在）。

strings.Repeat(s, n int) string//重复字符串 n 次。

//strconv 包（字符串与基本类型转换）

strconv.Atoi(s string) (int, error)//字符串转整数。

strconv.Itoa(i int) string//整数转字符串。

strconv.ParseInt(s string, base int, bitSize int) (int64, error)//解析指定进制的整数。

三、math包

//1.常量定义
//math.MaxInt：当前系统 int 类型的最大值（如 64 位系统为 9223372036854775807）。

//math.MinInt：当前系统 int 类型的最小值（如 64 位系统为 -9223372036854775808）。

//math.MaxInt32：32 位整数最大值（2147483647），常用于限制数组大小或坐标范围。

//math.MinInt32：32 位整数最小值（-2147483648）。

//math.Pi：圆周率（3.141592653589793），几何类题目常用。

//math.Abs(x float64) float64 求绝对值函数

//2.取整函数：
//math.Floor(x float64) float64：向下取整（如 Floor(2.8) = 2）。

//math.Ceil(x float64) float64：向上取整（如 Ceil(2.1) = 3）。

//math.Round(x float64) float64：四舍五入（如 Round(2.5) = 3）。

//应用：计算中位数、处理除法取整（如 (a + b - 1) / b 等价于 Ceil(a/b)）。

//3.幂运算与开方
//math.Pow(x, y float64) float64：计算 x^y（如 Pow(2, 3) = 8）。

//math.Sqrt(x float64) float64：计算平方根（如 Sqrt(16) = 4）。

四、rand包

// 初始化种子（建议在 main 函数或程序启动时执行一次）
rand.Seed(time.Now().UnixNano()) // 以当前纳秒时间为种子

//生成 [0, n) 范围内的整数：rand.Intn(n int) int
//最常用的函数，如生成 [0, 10) 的随机整数：
fmt.Println(rand.Intn(10)) // 可能输出 0-9 中的任意整数
//算法题中的典型应用
//随机快排的基准选择：避免有序数组退化，确保平均复杂度 O (n log n)：
// 在 [left, right] 范围内随机选择一个索引
pivotIdx := left + rand.Intn(right - left + 1)

//rand.Float64()：生成 [0.0, 1.0) 范围内的浮点数。
//扩展到 [a, b) 范围：a + rand.Float64() * (b - a)。