常见算法思想

golang algorithm
algorithm
发布日期:   2021-03-01
更新日期:   2025-12-08
文章字数:   2.7k
阅读时长:   11 分

常见算法思想记录

贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法不是对所有问题都能得到最优解，但对某些问题可以得到最优解，比如找零问题、区间覆盖、活动选择、Huffman编码等。

思想说明
贪心算法每一步都做出局部最优的选择，并且希望通过一系列局部最优的选择，能够导致全局最优解。其基本步骤是：

  1. 设计贪心策略（即如何选择每一步的最优选择），确保每个步骤的选择都是局部最优的。
  2. 按照贪心策略迭代并求解，直到无法再选择为止。

适用场景
如果一个问题满足“贪心选择性质”（即通过局部最优能推出全局最优），通常可以用贪心算法解决。常见的如：最小生成树、最短路径、最小硬币数等。

典型例子

  • 硬币找零：总是选择面值最大的硬币作为当前的最优选择，直到达到目标金额。
  • 区间调度：按照结束时间最早的原则选择，能够让最多的活动不交叠。
  • Huffman编码：每次合并权值最小的两个节点。

Golang示例：硬币找零问题

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
package main

import (
	"fmt"
	"sort"
)

// 硬币找零：使用贪心算法，每次选择面值最大的硬币
func coinChange(coins []int, amount int) []int {
	// 将硬币面值从大到小排序
	sort.Sort(sort.Reverse(sort.IntSlice(coins)))
	
	result := make([]int, 0)
	remaining := amount
	
	for _, coin := range coins {
		// 贪心策略：尽可能多地使用当前最大面值的硬币
		count := remaining / coin
		for i := 0; i < count; i++ {
			result = append(result, coin)
		}
		remaining %= coin
		
		if remaining == 0 {
			break
		}
	}
	
	if remaining != 0 {
		return nil // 无法找零
	}
	
	return result
}

func main() {
	coins := []int{1, 5, 10, 25, 50}
	amount := 87
	
	result := coinChange(coins, amount)
	if result != nil {
		fmt.Printf("找零 %d 元，需要硬币: %v\n", amount, result)
		fmt.Printf("硬币数量: %d\n", len(result))
	} else {
		fmt.Println("无法找零")
	}
	
	// 输出: 找零 87 元，需要硬币: [50 25 10 1 1]
	// 硬币数量: 5
}

分治思想

分治是一种将复杂问题分解为更简单子问题的方法。大问题拆分成若干子问题，递归求解各子问题，再将各子问题的解合并得到原问题的解。

思想说明

  1. 分：将原问题划分成若干规模较小、结构与原问题相似的子问题。
  2. 治：递归地求解各子问题。
  3. 合：将各子问题的解合并，得到原问题的解。

适用场景
分治适用于可以分解成相互独立的子问题，并且子问题之间的解可以合并得到全局解的场景。如归并排序、快速排序、FFT、二分查找、数的幂等。

典型例子

  • 归并排序：把数组分为两半，分别排序再合并。
  • 快速排序：将数组划分为左右两部分，递归排序。
  • 汉诺塔问题：将盘子分段搬运。
  • 最近点对问题。

Golang示例：归并排序

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
package main

import "fmt"

// 归并排序：分治思想的典型应用
func mergeSort(arr []int) []int {
	// 递归终止条件：数组长度小于等于1时，已经有序
	if len(arr) <= 1 {
		return arr
	}
	
	// 分：将数组分成两半
	mid := len(arr) / 2
	left := mergeSort(arr[:mid])  // 递归排序左半部分
	right := mergeSort(arr[mid:]) // 递归排序右半部分
	
	// 合：合并两个有序数组
	return merge(left, right)
}

// 合并两个有序数组
func merge(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))
	i, j := 0, 0
	
	// 比较两个数组的元素，将较小的元素加入结果
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}
	
	// 将剩余元素加入结果
	result = append(result, left[i:]...)
	result = append(result, right[j:]...)
	
	return result
}

func main() {
	arr := []int{38, 27, 43, 3, 9, 82, 10}
	fmt.Println("排序前:", arr)
	
	sorted := mergeSort(arr)
	fmt.Println("排序后:", sorted)
	
	// 输出:
	// 排序前: [38 27 43 3 9 82 10]
	// 排序后: [3 9 10 27 38 43 82]
}

回溯思想

回溯是一种试探法，主要用于在搜索某些问题的所有可行解时，逐步选择并尝试每一种可能，当发现某种选择无法得到正确解时，便回退一步，重新选择。回溯是一种“通过构建解的所有可能性，进行全排列搜索”的方法。

思想说明

  1. 从一个初始状态出发，进行选择或尝试；
  2. 每一次选择后判断当前状态是否满足目标条件，如果不满足则回溯到上一步；
  3. 如果选择满足目标，则递归进行下一步尝试，直到满足终止条件。

适用场景
常见于排列、组合、子集、图的遍历、约束满足问题（如数独、八皇后）等。

典型例子

  • 八皇后问题：每一行依次放皇后，不符合就回退；
  • 全排列：尝试每一种排列方式，递归选择和撤销。

Golang示例：全排列问题

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
package main

import "fmt"

// 全排列：使用回溯算法生成所有可能的排列
func permute(nums []int) [][]int {
	var result [][]int
	var path []int
	used := make([]bool, len(nums))
	
	var backtrack func()
	backtrack = func() {
		// 终止条件：路径长度等于数组长度，说明已经完成一个排列
		if len(path) == len(nums) {
			// 注意：需要复制path，因为path会被修改
			temp := make([]int, len(path))
			copy(temp, path)
			result = append(result, temp)
			return
		}
		
		// 尝试每一个可能的选项
		for i := 0; i < len(nums); i++ {
			// 跳过已经使用过的元素
			if used[i] {
				continue
			}
			
			// 做选择：将当前元素加入路径
			path = append(path, nums[i])
			used[i] = true
			
			// 递归：继续选择下一个元素
			backtrack()
			
			// 撤销选择：回溯到上一步
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	
	backtrack()
	return result
}

func main() {
	nums := []int{1, 2, 3}
	result := permute(nums)
	
	fmt.Printf("数组 %v 的全排列:\n", nums)
	for i, perm := range result {
		fmt.Printf("排列 %d: %v\n", i+1, perm)
	}
	
	// 输出:
	// 数组 [1 2 3] 的全排列:
	// 排列 1: [1 2 3]
	// 排列 2: [1 3 2]
	// 排列 3: [2 1 3]
	// 排列 4: [2 3 1]
	// 排列 5: [3 1 2]
	// 排列 6: [3 2 1]
}

动态规划

动态规划是解决具有重叠子问题和最优子结构问题的一种算法。通过将问题拆分为子问题，对子问题的解进行记录（记忆化）以避免重复计算，并自底向上计算出最终结果。

思想说明

  1. 分析问题，找出状态和状态之间的转移关系（即状态转移方程）；
  2. 定义dp数组（或表格）表示子问题的最优解；
  3. 按照递推或迭代方式填表，得到最终问题的解。

适用场景
当问题可以分解成多个子问题，且子问题之间有重复计算时，可以用动态规划，典型如背包问题、最长子序列、编辑距离等。

典型例子

  • 斐波那契数列：f(n) = f(n-1) + f(n-2)
  • 背包问题：每个物品选与不选两种状态
  • 最长上升子序列
  • 编辑距离

Golang示例：0-1背包问题

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
66
67
68
69
70
71
72
73
74
75
76
package main

import "fmt"

// 0-1背包问题：动态规划经典问题
// 有n个物品，每个物品有重量weight和价值value，背包容量为capacity
// 求在不超过背包容量的前提下，能装入的最大价值
func knapsack(weights, values []int, capacity int) int {
	n := len(weights)
	
	// dp[i][w] 表示前i个物品，在容量为w的背包中能获得的最大价值
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, capacity+1)
	}
	
	// 填充dp表
	for i := 1; i <= n; i++ {
		for w := 1; w <= capacity; w++ {
			// 状态转移方程：
			// 1. 不选第i个物品：dp[i][w] = dp[i-1][w]
			// 2. 选第i个物品：dp[i][w] = dp[i-1][w-weights[i-1]] + values[i-1]
			dp[i][w] = dp[i-1][w] // 不选当前物品
			
			if w >= weights[i-1] {
				// 选当前物品，取较大值
				if dp[i-1][w-weights[i-1]]+values[i-1] > dp[i][w] {
					dp[i][w] = dp[i-1][w-weights[i-1]] + values[i-1]
				}
			}
		}
	}
	
	return dp[n][capacity]
}

// 空间优化版本：使用一维数组
func knapsackOptimized(weights, values []int, capacity int) int {
	// dp[w] 表示容量为w的背包能获得的最大价值
	dp := make([]int, capacity+1)
	
	for i := 0; i < len(weights); i++ {
		// 从后往前遍历，避免覆盖需要使用的历史状态
		for w := capacity; w >= weights[i]; w-- {
			// 状态转移：选或不选当前物品
			if dp[w-weights[i]]+values[i] > dp[w] {
				dp[w] = dp[w-weights[i]] + values[i]
			}
		}
	}
	
	return dp[capacity]
}

func main() {
	weights := []int{2, 3, 4, 5}   // 物品重量
	values := []int{3, 4, 5, 6}    // 物品价值
	capacity := 8                   // 背包容量
	
	maxValue := knapsack(weights, values, capacity)
	fmt.Printf("背包容量: %d\n", capacity)
	fmt.Printf("物品重量: %v\n", weights)
	fmt.Printf("物品价值: %v\n", values)
	fmt.Printf("最大价值: %d\n", maxValue)
	
	// 使用优化版本
	maxValueOpt := knapsackOptimized(weights, values, capacity)
	fmt.Printf("优化版本最大价值: %d\n", maxValueOpt)
	
	// 输出:
	// 背包容量: 8
	// 物品重量: [2 3 4 5]
	// 物品价值: [3 4 5 6]
	// 最大价值: 10
	// 优化版本最大价值: 10
}

Golang示例：斐波那契数列（动态规划）

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package main

import "fmt"

// 斐波那契数列：f(n) = f(n-1) + f(n-2)
// 使用动态规划避免重复计算

// 方法1：自底向上（迭代）
func fibonacciDP(n int) int {
	if n <= 1 {
		return n
	}
	
	// dp[i] 表示第i个斐波那契数
	dp := make([]int, n+1)
	dp[0], dp[1] = 0, 1
	
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	
	return dp[n]
}

// 方法2：空间优化（只保留前两个状态）
func fibonacciOptimized(n int) int {
	if n <= 1 {
		return n
	}
	
	prev, curr := 0, 1
	for i := 2; i <= n; i++ {
		prev, curr = curr, prev+curr
	}
	
	return curr
}

// 方法3：记忆化递归（自顶向下）
func fibonacciMemo(n int) int {
	memo := make(map[int]int)
	
	var fib func(int) int
	fib = func(n int) int {
		if n <= 1 {
			return n
		}
		
		if val, ok := memo[n]; ok {
			return val
		}
		
		memo[n] = fib(n-1) + fib(n-2)
		return memo[n]
	}
	
	return fib(n)
}

func main() {
	n := 10
	fmt.Printf("计算第 %d 个斐波那契数:\n", n)
	fmt.Printf("DP方法: %d\n", fibonacciDP(n))
	fmt.Printf("优化方法: %d\n", fibonacciOptimized(n))
	fmt.Printf("记忆化递归: %d\n", fibonacciMemo(n))
	
	// 输出前10个斐波那契数
	fmt.Println("\n前10个斐波那契数:")
	for i := 0; i < 10; i++ {
		fmt.Printf("%d ", fibonacciOptimized(i))
	}
	fmt.Println()
	
	// 输出:
	// 计算第 10 个斐波那契数:
	// DP方法: 55
	// 优化方法: 55
	// 记忆化递归: 55
	// 前10个斐波那契数: 0 1 1 2 3 5 8 13 21 34
}

注意事项

  • 动态规划的本质是记录和复用子问题结果，设计状态表示和转移方程是核心。
  • 空间优化可以考虑滚动数组或只保留必要的历史状态。
文章作者: djaigo
文章链接: https://blog.djaigo.com/algorithm/chang-jian-suan-fa-si-xiang.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 djaigo !
golang algorithm
赏
评论
  目录