Canyang Blog
0%

算法笔记

发表于 分类于

算法笔记

本文我将分享一些常见算法题的模板，包括二分的几种不同区间写法、滑动窗口的模板、dfs bfs模板、优先队列、完全背包 01背包 多重背包模板等。 以及一些常见基础算法实现的代码手撕，如快排及其变种、归并排序，堆排序等。还总结了算法题中一些常见的函数，如字符串函数、sort包的函数和接口等。仅供学习与参考。

常见题模板

一、二分查找

二分查找是非常经典的减少查找复杂度的算法，其核心思想是“丢弃”，即在数据有序的前提下，快速舍弃掉不符合的区间，并对余下区间进行判断，一般复杂度为O(logn)。实现二分查找一般有三种写法：闭区间、开区间、半开半闭。不同点往往在于左右端点何时退出循环，返回的值是与哪个端点有关还是与mid有关。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//闭区间写法，一般来说最方便。
func binarySearch(nums []int,target int)int{
    //nums升序排列，查找target下标的index，没有则返回-1
    ans := -1
    l,r := 0,len(nums)-1
    for l<=r{
        mid := l + (r-l)/2 //这里为了防止某些情况下l+r溢出
        if nums[mid] == target{
            ans = mid
            break
        }
        if nums[mid] < target{
            //舍弃闭区间[l,mid]
            l = mid + 1
        }else{
            //舍弃闭区间[mid,r]
            r = mid - 1
        }
    }
   	return ans
}
//上面返回的是mid,下面是需要返回端点的写法
//力扣35. 搜索插入位置
func searchInsert(nums []int, target int) int {
	//根据题意如果target不存在的时候并不返回-1而是该被插入的位置，因此需要返回端点
    l,r := 0,len(nums)-1
	for l<=r{
		mid := l + (r-l)/2 //这里为了防止某些情况下l+r溢出
		if nums[mid] < target{
			//舍弃闭区间[l,mid]
			l = mid + 1
		}else{
			//舍弃闭区间[mid,r]
			r = mid - 1
		}
	}
	//因为有效值在[l,mid]中，最终这个区间长度变为1，即left
	//为什么不返回mid(如果记录了的话)，因为mid的更新是满足循环条件之后才会做的，
	//但最后舍弃完区间后可能以及退出了循环而没有更新mid
	//因此按区间端点来返回，后面几种返回端点的做法也有类似原因
	return left
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//开区间写法。
func binarySearch(nums []int,target int)int{
    //条件同上
    ans := -1
    //开区间要包含所有nums的元素
    l,r := -1,len(nums)
    //保证开区间内有元素
    for l + 1 < r{
        mid := l + (r-l)/2 //这里为了防止某些情况下l+r溢出
        if nums[mid] == target{
            ans = mid
            break
        }
        if nums[mid] < target{
            //舍弃区间(l,mid]
            l = mid
        }else{
            //舍弃区间[mid,r)
            r = mid
        }
    }
   	return ans
}
//力扣35的开区间做法
func searchInsert(nums []int, target int) int{
    //开区间要包含所有nums的元素
    l,r := -1,len(nums)
    //保证开区间内有元素
    for l + 1 < r{
        mid := l + (r-l)/2 //这里为了防止某些情况下l+r溢出
        if nums[mid] < target{
            //舍弃区间(l,mid]
            l = mid
        }else{
            //舍弃区间[mid,r)
            r = mid
        }
    }
    //right端点元素一定大于等于target，left端点元素一定小于target
    //结合题意如果没找到target的话返回第一个大于它的数的index，因此返回right
   	return right
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//半开半闭
func binarySearch(nums []int,target int)int{
    ans := -1
    //左开右闭
    l,r := -1,len(nums)-1
    //保证区间内有元素
    for l < r{
        mid := l + (r-l)/2 //这里为了防止某些情况下l+r溢出
        if nums[mid] == target{
            ans = mid
            break
        }
        if nums[mid] < target{
            //舍弃区间(l,mid]
            l = mid
        }else{
            //舍弃区间[mid,r]
            r = mid - 1
        }
    }
   	return ans
}
func binarySearch(nums []int,target int)int{
    ans := -1
    //左闭右开
    l,r := 0,len(nums)
    //保证区间内有元素
    for l < r{
        mid := l + (r-l)/2 //这里为了防止某些情况下l+r溢出
        if nums[mid] == target{
            ans = mid
            break
        }
        if nums[mid] < target{
            //舍弃区间[l,mid]
            l = mid + 1
        }else{
            //舍弃区间[mid,r)
            r = mid
        }
    }
   	return ans
}

//力扣35的半开半闭写法
func searchInsert(nums []int, target int) int{
    //这里选择左闭右开写法
    //这样的话结果返回left还是right都可以
    //因为区间端点最终重合且都大于等于target(由开区间的right推出大于等于)
    l,r := 0,len(nums)
    //保证开区间内有元素
    for l < r{
        mid := l + (r-l)/2 //这里为了防止某些情况下l+r溢出
        if nums[mid] < target{
            //舍弃区间[l,mid]
            l = mid + 1
        }else{
            //舍弃区间[mid,r)
            r = mid
        }
    }

   	return left //或right
}

二、滑动窗口模板

滑动窗口其实也有几种区间写法，但无非就是什么时候读入第一个元素的问题，这里以力扣76. 最小覆盖子串为例给出一个模板式的写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func minWindow(s string, t string) string {
	m := make(map[rune]int, 0)
	for _, v := range t {
		m[v]++
	}
	window := make(map[rune]int, 0)
    //检查窗口内字符数量是否满足字串中出现的次数
	checkTimes := func() bool {
		for i, v := range m {
			if window[i] < v {
				return false
			}
		}
		return true
	}

	minLength := math.MaxInt
	ans := [2]int{}
	//这样写是左闭右开的写法，初始化的时候没有元素，然后读入一个元素，右窗口递增一
	l, r := 0, 0
	for r < len(s) {
		//延申右窗口
		window[rune(s[r])]++
		r++
		for l < r && window[rune(s[l])] > m[rune(s[l])] {
			//读入右边后检查左边是否需要缩小窗口
			window[rune(s[l])]--
			l++
		}
		//检查窗口内值是否满足且长度最小
		if checkTimes() && r-l < minLength {
			ans = [2]int{l, r}
			minLength = r - l
		}
	}
	return s[ans[0]:ans[1]]
}

三、两种搜索dfs与bfs

dfs和bfs其实能够解决非常多的问题，其变式也不少，这里只分享几种简单的写法，后续可能会结合例题再总结一些变式写法。总的来说，dfs一般适用于暴力搜索、记录层级状态并回溯、模拟路径遍历、求最大深度、自顶向下的dp等问题，而bfs则适用于图的连通性、最短路径问题、层次遍历、避免dfs栈溢出而使用bfs等场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//dfs
//比如求子集的题
func subsets(nums []int) ans [][]int{
    ans := make([][]int,0)
    n:=len(nums)
    var dfs func([]int,int)
    //这里采用参数中带out不需要恢复现场，否则一般要进行回溯操作
    //dfs函数的定义入参中一般包含了搜索的层数，函数中先处理层数，若满足退出条件则退出
    //然后处理当前层的数据，考虑继续下层搜索还是退出
    //其中不少题都需要用到记忆化数组进行剪枝，减少搜索的次数，遇到以及搜索到分支则直接退出或跳过
    dfs = func(out []int,index int){
        if index==n{
            temp := make([]int,len(out))
            copy(temp,out)
            ans = append(ans,temp)
            return
        }
        //不选这个数
        dfs(out,index+1)
        //选这个数
        out = append(out,nums[index])
        dfs(out,index+1)
    }
    dfs([]int{},0)
    return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//bfs
//例如二叉树层序遍历（按层输出节点值）
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}

	result := [][]int{}
    //初始化层队列
    q := make([]*TreeNode,0)
    q = append(q,root)

	for Len(q) > 0 {
		sz := Len(q) // 当前层的节点数量
		currentLevel := []int{}  // 存储当前层的节点值

		// 遍历当前层的所有节点
		for i := 0; i < sz; i++ {
			node := q[i]
			currentLevel = append(currentLevel, node.Val)

			// 将下一层的节点加入队列
			if node.Left != nil {
				q = append(q,node.Left)
			}
			if node.Right != nil {
				q = append(q,node.Right)
			}
		}
		//清除已经遍历的节点
        q = q[sz:]
		result = append(result, currentLevel)
	}

	return result
}

四、优先队列

go中优先队列一般借助sort包中提供的接口来实现，其底层就是堆排序，可以自定义优先级。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
type People struct {
	Name string
	Age  int
}
type PeopleQueue []People

func (p PeopleQueue) Len() int {
	return len(p)
}
func (p PeopleQueue) Less(i, j int) bool {
	return p[i].Age < p[j].Age
}
func (p PeopleQueue) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}
//Push 和 Pop 两个方法使用指针接收器是因为要对原切片进行修改，如果采用值接收器则只改变了底层数组
func (p *PeopleQueue) Push(x interface{}) {
	*p = append(*p, x.(People))
}
func (p *PeopleQueue) Pop() interface{} {
	n := len(*p)
	old := *p
	x := old[n-1]
	*p = old[0 : n-1]
	return x
}
func TestPriorityQueue(t *testing.T) {
	queue := PeopleQueue{
		{"Alice", 25},
		{"Bob", 30},
		{"Charlie", 20},
		{"David", 35},
		{"Eve", 28},
	}
	heap.Init(&queue)
	for queue.Len() > 0 {
		fmt.Println(heap.Pop(&queue))
	}
}
/*
{Charlie 20}
{Alice 25}
{Eve 28}
{Bob 30}
{David 35}
*/

五、动态规划（背包问题）

动态规划作为变式极多，上限也极高的算法，这里无法作过多解析，只给出背包问题中典型的三个变式，从最开始的完全背包，到01背包，再到多重背包及其二进制优化。暂时并不涉及多重背包的单调队列优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//完全背包，即所有物品无限，在一个固定容量下求能去到的最大价值
func completeKnapsack(V int,values []int,weights []int) int{
    //个人喜欢用自底向上的写法
    dp := make([]int,V+1)//容量从零到V
    //遍历容量
    for i:=1;i<=V;i++{
        //遍历物品
        for j,w := range weights{
            if i-w>=0{
                dp[i] = max(dp[i],dp[i-w]+values[j])
            }
        }
    }
    return dp[V]
}
//下面写法相对更好一些
func completeKnapsack(V int,values []int,weights []int) int{
    //个人喜欢用自底向上的写法
    dp := make([]int,V+1)//容量从零到V
    //遍历物品
    for i:=0;i<n;i++{
        //遍历容量
        for j:= weight[i];j<=V;j++{
            dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
        }
    }
    return dp[V]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//01背包 每种物品只有一个
//一般有二维和一维两种写法

//二维
func zeroOneKnapsack(weights []int, values []int, V int) int{
    n:= len(weight)
    dp := make([][]int,n+1)//第一维选择物品
    for i,_:=range dp{
        dp[i] = make([]int,V+1)//第二维遍历容量
    }
    for i:=1;i<=n;i++{
        for j:=1;j<=V;j++{
            if j < weight[i]{
                dp[i][j] = dp[i-1][j]
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-weights[i-1]]+values[i-1])
            }
        }
    }
    return dp[n][V]
}
//一维写法
func zeroOneKnapsack(weights []int, values []int, V int) int {
	n := len(weights)
	// dp[i]表示容量为i的背包能装的最大价值
	dp := make([]int, V+1)
	
	// 遍历物品
	for i := 0; i < n; i++ {
		// 倒序遍历容量（防止重复使用同一物品）
        // 因为从小遍历容量会计算更大容量，影响后续计算
		for j := V; j >= weights[i]; j-- {
			// 状态转移方程：取或不取当前物品
			dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
		}
	}
	return dp[V]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//多重背包 即一种数量的物品有多个
//可以按每个物品算一种，转化成01背包
//也可以进行二进制优化，假设一种物品有n个
//那么从0-n的所有选择情况都可以用二进制数表示(如五个物品可以表示为101)
//把每个位当作一种新物品进行选择，即是优化后的01背包

//无优化版本
func multipleKnapsack(weight []int, value []int, count []int, capacity int) int {
	n := len(weight)
	dp := make([]int, capacity+1)
	
	// 遍历物品
	for i := 0; i < n; i++ {
		// 倒序遍历容量
		for j := capacity; j >= weight[i]; j-- {
			// 遍历物品数量（取0到最大可能数量）
			for k := 1; k <= count[i] && k*weight[i] <= j; k++ {
				dp[j] = max(dp[j], dp[j-k*weight[i]]+k*value[i])
			}
		}
	}
	return dp[capacity]
}

// 多重背包的二进制优化版本
func multipleKnapsackOptimized(weight []int, value []int, count []int, capacity int) int {
	// 将多重背包转化为01背包
	var newWeights, newValues []int
	
	for i := 0; i < len(weight); i++ {
		c := count[i]
		// 二进制拆分
		k := 1
		for c > k {
			newWeights = append(newWeights, weight[i]*k)
			newValues = append(newValues, value[i]*k)
			c -= k
			k *= 2
		}
		// 剩余数量
		newWeights = append(newWeights, weight[i]*c)
		newValues = append(newValues, value[i]*c)
	}
	
	// 使用01背包求解
	return zeroOneKnapsack(newWeights, newValues, capacity)
}

由于篇幅原因，常见排序的手撕和常用函数将放在下一篇文章中。