分治法

汉诺塔问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
package main

import "fmt"

func main() {
    hanoi(3, "A", "B", "C")
}

func hanoi(n int, a, b, c string) {
    if n == 1 {
        fmt.Println(a, "-->", c)
    } else {
        hanoi(n-1, a, c, b)//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
        fmt.Println(a, "-->", c)
        hanoi(n-1, b, a, c)//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
    }
}

归并排序

归并排序中的分治法

算法分析

若子序列的长度为1，则划分结束，否则继续执行划分结果有: 具有[n]个元素的序列

将序列划分为两个具有[n/2]个元素(长度为2)的子序列
得到[n/4]个长度为4的子序列
直到得到长度为n的有序子序列

对数组r[n]进行升序排序

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

import (
	"fmt"
)

// mergeSort 函数用于执行归并排序算法
func mergeSort(arr []int) []int {
	// 如果数组长度小于等于1，已经是有序的，直接返回
	if len(arr) <= 1 {
		return arr
	}

	// 分割数组
	middle := len(arr) / 2
	left := mergeSort(arr[:middle])
	right := mergeSort(arr[middle:])

	// 合并排序后的子数组
	return merge(left, right)
}

// merge 函数用于将两个有序的子数组合并成一个有序的数组
func merge(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))

	// 当左右子数组都非空时，比较它们的第一个元素，选择较小的元素放入结果数组
	for len(left) > 0 || len(right) > 0 {
		if len(left) == 0 {
			// 如果左子数组为空，将右子数组的剩余部分添加到结果数组
			return append(result, right...)
		}
		if len(right) == 0 {
			// 如果右子数组为空，将左子数组的剩余部分添加到结果数组
			return append(result, left...)
		}

		// 比较左右子数组的第一个元素
		if left[0] <= right[0] {
			// 如果左子数组的第一个元素小于等于右子数组的第一个元素，将左子数组的第一个元素添加到结果数组
			result = append(result, left[0])
			// 左子数组指针向后移动
			left = left[1:]
		} else {
			// 如果右子数组的第一个元素小于左子数组的第一个元素，将右子数组的第一个元素添加到结果数组
			result = append(result, right[0])
			// 右子数组指针向后移动
			right = right[1:]
		}
	}

	return result
}

func main() {
	// 示例输入
	arr := []int{38, 27, 43, 3, 9, 82, 10}

	// 调用归并排序函数
	sortedArr := mergeSort(arr)

	// 打印排序后的数组
	fmt.Println("Sorted Array:", sortedArr)
}

 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
#include <stdio.h>

// 合并两个有序子数组
void Merge(int r[], int s, int m, int t) {
  int r1[t + 1];  // 临时数组用于存储合并后的结果
  int i = s, j = m + 1, k = s;

  // 比较两个子数组的元素，将较小的元素放入临时数组
  while (i <= m && j <= t) {
    if (r[i] <= r[j])
      r1[k++] = r[i++];
    else
      r1[k++] = r[j++];
  }

  // 处理剩余的元素，如果左右子数组长度不一致
  while (i <= m)
    r1[k++] = r[i++];
  while (j <= t)
    r1[k++] = r[j++];

  // 将合并后的结果拷贝回原数组
  for (i = s; i <= t; i++)
    r[i] = r1[i];
}

// 归并排序
void MergeSort(int r[], int s, int t) {
  if (s == t)
    return;  // 当前子数组只有一个元素，已经是有序的

  // 计算中间位置
  int m = (s + t) / 2;

  // 递归地对左右两个子数组进行排序
  MergeSort(r, s, m);
  MergeSort(r, m + 1, t);

  // 合并两个有序子数组
  Merge(r, s, m, t);
}

int main() {
  // 示例输入
  int arr[] = {38, 27, 43, 3, 9, 82, 10};
  int n = sizeof(arr) / sizeof(arr[0]);

  // 调用归并排序函数
  MergeSort(arr, 0, n - 1);

  // 打印排序后的数组
  printf("Sorted Array: ");
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

最大子段和问题

Karatsuba算法

Karatsuba算法是一种快速乘法算法，用于计算两个大整数的乘积。它的基本思想是将两个大整数分别拆分成两部分，然后通过递归地计算乘积，最后将结果合并得到最终的乘积。

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

import "fmt"

//TODO:
/* x = 1234
  y = 5678
  a=12
  b=34
  c=56
  d=78

  r1=a*c=12*56=672
  r2=b*d=34*78=2652
  r3=(a+b)*(c+d)=(12+34)*(56+78)=46*134=6164

  result=r1*10^4+(r3-r1-r2)*10^2+r2
*/

// Karatsuba 函数用于执行Karatsuba算法
func Karatsuba(x, y int) int {
  if x < 10 || y < 10 {
    return x * y
  }

  // 计算x和y的位数
  m := 1
  for x/m > 10 {
    m *= 10
  }
  m /= 10
  n := 1
  for y/n > 10 {
    n *= 10
  }
  n /= 10

  // 拆分x和y
  a, b := x/m, x%m
  c, d := y/n, y%n

  // 递归地计算乘积
  ac := Karatsuba(a, c)
  bd := Karatsuba(b, d)
  abcd := Karatsuba(a+b, c+d) - ac - bd

  // 合并结果
  return ac*m*m + abcd*m + bd
}

 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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 定义一个函数，用于计算两个大整数的乘积
long long karatsuba(long long x, long long y, int n) {
    if (n == 1) {
        return x * y;
    }

    int m = n / 2;

    // 将x和y分解为a, b, c, d
    long long a = x / (long long)pow(10, m);
    long long b = x % (long long)pow(10, m);
    long long c = y / (long long)pow(10, m);
    long long d = y % (long long)pow(10, m);


    //12 34 56 78
    //
    // 计算三个中间乘积
    long long ac = karatsuba(a, c, m);
    long long bd = karatsuba(b, d, m);
    long long ad_bc = karatsuba(a + b, c + d, m) - ac - bd;

    // 计算最终结果
    return ac * (long long)pow(10, 2 * m) + ad_bc * (long long)pow(10, m) + bd;
}

int main() {
    long long x, y;

    // 输入两个整数
    printf("Enter the first integer: ");
    scanf("%lld", &x);
    printf("Enter the second integer: ");
    scanf("%lld", &y);

    // 计算乘积并输出结果
    int n = log10(x) + 1;  // 计算整数的位数
    long long result = karatsuba(x, y, n);
    printf("The product is: %lld\n", result);

    getchar();
    
    return 0;
}

最大子段和(子数组)

方法一:动态规划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 定义一个函数，参数为整数数组和数组的大小
int maxSubArray(int* nums, int numsSize) {
    // pre 表示当前子数组的累加和，maxAns 表示当前最大的子数组和
    int pre = 0, maxAns = nums[0];
    
    // 遍历整个数组
    for (int i = 0; i < numsSize; i++) {
        // 更新当前子数组的累加和，如果累加和变得小于当前元素，则从当前元素重新开始累加 //fmax用于返回两个浮点数中的较大值
        pre = fmax(pre + nums[i], nums[i]);
        
        // 更新当前最大的子数组和
        maxAns = fmax(maxAns, pre);
    }
    
    // 返回最终计算得到的最大子数组和
    return maxAns;
}

思路和算法

假设 nums\textit{nums}nums 数组的长度是 nnn，下标从 000 到 n−1n-1n−1。

我们用 f(i)f(i)f(i) 代表以第 iii 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：

max⁡0≤i≤n−1{f(i)}\max_{0 \leq i \leq n-1} { f(i) }max 0≤i≤n−1 {f(i)}

因此我们只需要求出每个位置的 f(i)f(i)f(i)，然后返回 fff 数组中的最大值即可。那么我们如何求 f(i)f(i)f(i) 呢？我们可以考虑 nums[i]\textit{nums}[i]nums[i] 单独成为一段还是加入 f(i−1)f(i-1)f(i−1) 对应的那一段，这取决于 nums[i]\textit{nums}[i]nums[i] 和 f(i−1)+nums[i]f(i-1) + \textit{nums}[i]f(i−1)+nums[i] 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：

f(i)=max⁡{f(i−1)+nums[i],nums[i]}f(i) = \max { f(i-1) + \textit{nums}[i], \textit{nums}[i] }f(i)=max{f(i−1)+nums[i],nums[i]}

不难给出一个时间复杂度 O(n)O(n)O(n)、空间复杂度 O(n)O(n)O(n) 的实现，即用一个 fff 数组来保存 f(i)f(i)f(i) 的值，用一个循环求出所有 f(i)f(i)f(i)。考虑到 f(i)f(i)f(i) 只和 f(i−1)f(i-1)f(i−1) 相关，于是我们可以只用一个变量 pre\textit{pre}pre 来维护对于当前 f(i)f(i)f(i) 的 f(i−1)f(i-1)f(i−1) 的值是多少，从而让空间复杂度降低到 O(1)O(1)O(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
class Solution {
public:
    // 定义一个结构体 Status，表示某个区间的四个值：左侧和、右侧和、跨越中点的和、区间总和
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    // 定义一个辅助函数 pushUp，用于合并左右子区间的信息
    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum; // 区间总和
        int lSum = max(l.lSum, l.iSum + r.lSum); // 左侧和
        int rSum = max(r.rSum, r.iSum + l.rSum); // 右侧和
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum); // 跨越中点的和
        return (Status) {lSum, rSum, mSum, iSum};
    };

    // 定义递归函数 get，用于分治求解最大子数组和
    Status get(vector<int> &a, int l, int r) {
        // 当区间只有一个元素时，返回该元素构成的 Status 结构
        if (l == r) {
            return (Status) {a[l], a[l], a[l], a[l]};
        }

        // 计算中点
        int m = (l + r) >> 1;

        // 递归求解左右子区间的信息
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);

        // 合并左右子区间的信息
        return pushUp(lSub, rSub);
    }

    // 主函数 maxSubArray，调用 get 函数得到最大子数组和的结果
    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

动态规划法

最长公共子序列(LCS)

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:## s和t获取长度
        n, m = len(s), len(t)

        @cache  # 使用Python的functools.cache装饰器进行记忆化
        def dfs(i, j):
            if i < 0 or j < 0:
                return 0
            if s[i] == t[j]:
                return dfs(i - 1, j - 1) + 1
            return max(dfs(i - 1, j), dfs(i, j - 1))
           ## abcde ace
           ## 输出3
           ## 

        return dfs(n - 1, m - 1)

1
2
3
4
5
6
7
8
9
class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int: #翻译成递推
        n, m = len(s), len(t)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(s):
            for j, y in enumerate(t):
                f[i + 1][j + 1] = f[i][j] + 1 if x == y else \
                                  max(f[i][j + 1], f[i + 1][j])
        return f[n][m]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:  #空间优化成一个数组
        f = [0] * (len(t) + 1)
        for x in s:
            pre = 0  # f[0]
            for j, y in enumerate(t):
                tmp = f[j + 1]
                f[j + 1] = pre + 1 if x == y else max(f[j + 1], f[j])
                pre = tmp
        return f[-1]

0/1 背包

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

＃ capacity：背包容量
＃ w［i］：第i个物品的体积＃ v［i］：第i个物品的价值
＃ 返回：所选物品体积和不超过capacity的前提下，所能得到的最大价值和
def zero_one_knapsack(capacity: int, w: List[int], v: List[int]) -> int
  n = 1en(w)
  @cache
  def dfs(i, c): if i < 0: return ø if c < w[i]:
    return dfs(i-1,c)
  return max(dfs(i-1,c), dfs(i-1, c-w[i]) + v[i]) return dfs(n-1, capacity)

return dfs(n-1,capacity)

从尾部回溯到开头，并且把每次的c都加上

贪心算法

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：

输入：height = [1,1] 输出：1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func maxArea(height []int) (ans int) {
    left, right := 0, len(height)-1
    for left < right {
        area := (right - left) * min(height[left], height[right])
        ans = max(ans, area)
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return
}

func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }

不同面额的钞票，看看目前的局部最优解，贪心在局部，不看全局

回溯法

减治法

堆排序

最小堆：所有父亲节点不比其孩子节点的值大的完全二叉树。最大堆：所有父亲节点不比其孩子节点的值小的完全二叉树。

堆排序：建立最大堆，弹出头，放到尾，直到堆空

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

import (
    "fmt"
)

// 调整堆，使其满足最大堆的性质
func heapify(arr []int, n, i int) {
    largest := i // 假设最大值索引为i
    left := 2*i + 1
    right := 2*i + 2

    // 如果左子节点比根节点大，则更新最大值索引为左子节点
    if left < n && arr[left] > arr[largest] {
        largest = left
    }

    // 如果右子节点比根节点大，则更新最大值索引为右子节点
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    // 如果最大值不是根节点，则交换根节点和最大值节点，并继续调整堆
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

// 堆排序函数
func heapSort(arr []int) {
    n := len(arr)

    // 构建最大堆
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }

    // 从最大堆中一个个取出元素并调整堆
    for i := n - 1; i >= 0; i-- {
        // 将当前根节点（最大值）与最后一个元素交换
        arr[0], arr[i] = arr[i], arr[0]
        // 调整剩余堆
        heapify(arr, i, 0)
    }
}

func main() {
    arr := []int{12, 11, 13, 5, 6, 7}
    fmt.Println("Unsorted array is:", arr)
    heapSort(arr)
    fmt.Println("Sorted array is:", arr)
}

深度优先算法

素数环问题

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

import (
	"fmt"
)

// 判断一个数是否为素数
func isPrime(num int) bool {
	if num <= 1 {
		return false
	}
	for i := 2; i*i <= num; i++ {
		if num%i == 0 {
			return false
		}
	}
	return true
}

// 检查当前数字是否满足条件
func isValid(current, pos int, visited []bool) bool {
	if visited[current] {
		return false
	}
	if pos == 1 {
		return true // 第一个数字不需要检查
	}
	// 检查当前数字与前一个数字的和是否为素数
	sum := current + pos - 1
	return isPrime(sum)
}

// 回溯法搜索素数环
func backtracking(n, pos int, visited []bool, result []int) {
	if pos == n+1 {
		// 判断最后一个数和第一个数的和是否为素数
		if isPrime(result[n]+result[1]) {
			fmt.Println(result)
		}
		return
	}
	for i := 2; i <= n; i++ {
		if isValid(i, pos, visited) {
			visited[i] = true
			result[pos] = i
			backtracking(n, pos+1, visited, result)
			visited[i] = false
		}
	}
}

func main() {
	n := 6 // 例如，假设环的大小为6
	visited := make([]bool, n+1)
	result := make([]int, n+1)
	backtracking(n, 1, visited, result)
}

图

最小生成树

转载自

https://writings.sh/post/data-structure-heap-and-common-problems

分治法#

汉诺塔问题#

归并排序#

最大子段和问题#

Karatsuba算法#

最大子段和(子数组)#

动态规划法#

最长公共子序列(LCS)#

0/1 背包#

贪心算法#

回溯法#

减治法#

堆排序#

深度优先算法#

素数环问题#

图#

最小生成树#

转载自#

分治法