瑞文网络计算机小课堂

math.MaxInt32表示32位int最大值 math.Sqrt(x float64)float64求平方根

问题描述有N件物品和一个容量是V的背包。每件物品只能使用一次。第件物品的体积是，价值是。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 背包问题类型1、0/1背包问题：每个元素最多选取一次2、完全背包问题：每个元素可以重复选择3、组合背包问题：背包中的物品要考虑顺序4、分组背包问题：不止一个背包，需要遍历每个背包 背包问题分类1、最值问题：要求最大值/最小值2、存在问题：是否存在…………，满足…………3、组合问题：求所有满足……的排列组合

性质1 a=k1m+r1 b=k2m+r2 那么

代码模版结构12345type UnionFind struct { parent []int rank []int count int } 初始化123456789func NewUnioinFind(n int) *UnionFind{ parent := make([]int, n) rank := make([]int, n) for i := range parent{ parent[i] = i rank[i] = 1 } return &UnionFind{parent, rank, n}} 查询(find)1234567func(uf *UnionFind)find(x int)int{ //由于初始化时parent[i] = i，所以代表元的特点为paren[i]=i if uf.parent[x] != x{ uf.parent[x] = uf.find(uf.parent[x]) //路径压缩 } return uf.parent[x]} 按秩 ...

定义Go语言的list是一个带头结点的双向链表，头结点中并不存储数据。双向链表中的每个元素都持有其前后元素的引用，在进行元素的插入和删除操作时需要同时修改前后元素的持有引用。 初始化1234//方式一var name list.List//方式二name := list.New() 插入元素链表的每次插入会返回一个*list.Element结构，用以指向当前插入值所在节点。 尾插法在链表尾部插入元素 1name.PushBack("a") 头插法在链表头部插入元素 1name.PushFront("b") 遍历链表123for l := name.Front(); l!= nil; l = l.Next(){ fmt.Println(l.Value)}

定义数组是一段存储固定类型固定长度的连续内存空间，它的大小在声明的时候就已经固定下来了。数组的声明方式： 12var array1 [size] T //需要通过遍历进行初始化var array2 [2]int {1, 2} //声明时初始化 数组大小不必须指定，可以是一个常量或者表达式，但必须在静态编译时就确定其大小，不能动态指定。 也可以通过使用”…”让编译器为我们判断数组大小 1array3 := [...]int{1, 2}

参考资料Skip Lists: A Probabilistic Alternative toBalanced Trees 设计跳表 https://oi-wiki.org/ds/skiplist/

本质找到某种性质将区间一份为二，一半满足，一半不满足。每次选择答案所在的区间 模版一：寻找绿色区间的左端点若绿色区间满足的性质为：大于等于target，则寻找到的结果为大于等于target最小的数。 1234567891011func binarySearch(l, r int) int{ for l < r { mid := l + (r - l)/2 if check(mid){ r = mid }else { l = mid + 1 } } return l} 模版二：寻找红色区间的右端点若红色区间满足的性质为：小于等于target，则寻找到的结果为小于等于target最大的数。 1234567891011func binarySearch(l, r int) int{ for l < r { mid := l + (r - l + 1)/2 //由于下取整的原因需要+1 if check(mid){ l = mid }e ...

max()、min()123func max[T cmp.Ordered](x T, y ...T) Tfunc min[T cmp.Ordered](x T, y ...T) T 这是一个泛型函数，用于从一组值中寻找并返回最大值、最小值，该函数至少要传递一个参数。在上述函数签名中，T表示类型参数，它必须满足 cmp.Ordered 接口中定义的数据类型要求，该接口的定义如下所示： 123456type Ordered interface { ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr | ~float32 | ~float64 | ~string} 该方法在Go 1.21中引入

[]int 排序升序排序123s := []int{2, 3, 1, 4}sort.Ints(s)// 排序会输出[1, 2, 3, 4] 降序排序12345s := []int{3, 2, 1, 4}sort.Slice(s, func(i, j int) bool { return s[i] > s[j]})// 排序会输出[4, 3, 2, 1]