分治算法
分治算法的思想
分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
分治算法和递归的区别
分治是处理问题的思想，递归是一种编程技巧。分治一般都比较适合用用递归来实现。
分治算法的实现中，每一层地递归都会涉及到下面三个操作：
分解：将原问题分解成一系列子问题；
解决：将子问题的结果合并成原问题。
使用分治算法需要满足的条件
1、原问题与分解成的小问题具有相同的模式；
2、原问题分解成的子问题可以独立求解，子问题之间没有相关性；
3、具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
4、可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。
经典题目
1、二分搜索
给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
题目链接：https://leetcode.cn/problems/binary-search
解题思路
1、满足分支算法的思想，将为题分解为规模较小的相同问题时，就比较容易求解；
2、找出中间的值和目标值进行比较，通过判断大小，来不断的缩小问题的求解范围；
3、这样每次的求解，总是能将问题的范围缩小一半，或者找出目标值。
时间复杂度：O(logn)
空间复杂度：O(1)
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := (right + left) / 2
if nums[mid] == target {
return mid
} else if nums[mid] > target {
right = mid - 1
} else if nums[mid] < target {
left = mid + 1
}
}
return -1
}
2、第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用bool isBadVersion(version)接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5)-> true
调用 isBadVersion(4)-> true
所以，4 是第一个错误的版本。
示例 2：
输入：n = 1, bad = 1
输出：1
链接：https://leetcode.cn/problems/first-bad-version
题解：
这道题目是二分查找的变种题目，找出最近的一个出错的版本，也就是出错版本的左边都是出错的版本；
所以利用二分查找，找出出错的又边界即可
/**
* Forward declaration of isBadVersion API.
* @param version your guess about first bad version
* @return true if current version is bad
* false if current version is good
* func isBadVersion(version int) bool;
*/
func firstBadVersion(n int) int {
left, right := 0, n
for left < right {
mid := (right + left) / 2
if isBadVersion(mid) {
right = mid
} else {
left = mid + 1
}
}
return right
}
// 测试函数
func isBadVersion(n int) bool {
return false
}
3、快速排序
快速排序在我们刚学习算法的时候就遇到了过了，其中它使用到的算法思想就是分治策略。
它的处理思路就是，会选中一个基准数，通过一趟排序，和当前的基准数进行比较，将数据分总成两部分，一部分大于基准数，另一部分小于基准数。
然后对这两部分数据在进行上面的操作，直到所有的数据都有序，整个排序的过程可以使用递归去实现。
快排的时间复杂度：平均情况下快速排序的时间复杂度是Θ(nlgn)，最坏情况是n2
空间复杂度：最好空间复杂度为 O(logn)，最坏空间复杂度为 O(n)
上代码
func QuickSort(arr []int) {
quickSort(arr, 0, len(arr)-1)
}
func quickSort(data []int, l, u int) {
if l < u {
m := partition(data, l, u)
quickSort(data, l, m-1)
quickSort(data, m, u)
}
}
func partition(data []int, l, u int) int {
quick := data[l]
left := l
for i := l + 1; i <= u; i++ {
if data[i] <= quick {
left++
data[left], data[i] = data[i], data[left]
}
}
data[l], data[left] = data[left], data[l]
return left + 1
}
4、归并排序
归并排序也是使用分治思想实现的一个比较经典的栗子，这里来分析下
归并排序的处理思路：
1、首先拆分子序列，使得子序列很容易排序，然后对子序列进行排序；
2、然后是合并的过程，将有序的子序列合并；
3、合并子序列的过程；
-
1、申请空间，大小为两个已经排好序的子序列大小之和，该空间用来存放合并后的序列；
-
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置；
-
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
-
4、重复步骤3直到某一指针超出序列尾；
-
5、将剩下的元素直接复制到合并序列尾部；
具体的动画细节
上代码
时间复杂度 O（nlogn）
空间复杂度 O（n）
func MergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
leftArr := MergeSort(arr[0:mid])
rightArr := MergeSort(arr[mid:])
return merge(leftArr, rightArr)
}
func merge(left, right []int) []int {
i, j := 0, 0
m, n := len(left), len(right)
var result []int
// 合并子序列
for {
// 任何一个区间遍历完成就退出
if i >= m || j >= n {
break
}
if left[i] > right[j] {
result = append(result, right[j])
j++
} else {
result = append(result, left[i])
i++
}
}
// 左边的子集没有遍历完成，将左侧的放入到结果集
if i < m {
result = append(result, left[i:]...)
}
// 右侧的子集没有遍历完成，将右侧的放入到结果集中
if j < n {
result = append(result, right[j:]...)
}
return result
}
直接在原数组上进行操作
func MergeSort(nums []int) []int {
mergeSort(nums, 0, len(nums)-1)
return nums
}
func mergeSort(nums []int, start, end int) {
if start >= end {
return
}
mid := start + (end-start)/2
mergeSort(nums, start, mid)
mergeSort(nums, mid+1, end)
var tmp []int
i, j := start, mid+1
for i <= mid && j <= end {
if nums[i] > nums[j] {
tmp = append(tmp, nums[j])
j++
} else {
tmp = append(tmp, nums[i])
i++
}
}
if i <= mid {
tmp = append(tmp, nums[i:mid+1]...)
}
if j <= end {
tmp = append(tmp, nums[j:end+1]...)
}
for i := start; i <= end; i++ {
nums[i] = tmp[i-start]
}
}
5、数组中的逆序对
题目地址：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
输入: [7,5,6,4]
输出: 5
解题思路
首先用到的是分治算法的思想
1、什么是逆序对，就是前面的数字大小，小于位于其后面的数字大小，那么这就是一个逆序对；
2、这里主要用到了分治的算法，只是在分治算法的基础之上，在进行数据的合并的时候，因为左边部分和右边部分都是已经排好序了，所以可以使用这种关系，来计算逆序对的个数；
3、具体的合并计算过程；
-
1、在左边和右边数组中，都从第一个下标，开始匹配；
-
2、如果左边当前下标的数大于右边数组当前下标的值，因为这两个数组都是从大到小排序的，所有左边从当前下标开始数，都大于右边当前匹配下标的数，
cnt += mid - i + 1，同时右边数组下标前移； -
3、如果左边当前下标的数小于右边数组当前下标的值，不满足，左边数组下标前移；
func reversePairs(nums []int) int {
return mergeSort(nums, 0, len(nums)-1)
}
func mergeSort(nums []int, start, end int) int {
if start >= end {
return 0
}
mid := start + (end-start)/2
cnt := mergeSort(nums, start, mid) + mergeSort(nums, mid+1, end)
tmp := []int{}
i, j := start, mid+1
for i <= mid && j <= end {
if nums[i] > nums[j] {
tmp = append(tmp, nums[j])
cnt += mid - i + 1
j++
} else {
tmp = append(tmp, nums[i])
i++
}
}
if i <= mid {
tmp = append(tmp, nums[i:mid+1]...)
}
if j <= end{
tmp = append(tmp, nums[j:end+1]...)
}
for i := start; i <= end; i++ {
nums[i] = tmp[i-start]
}
return cnt
}
6、汉诺塔
汉诺塔问题的描述：
假设有 A、B、C 三根柱子。其中在 A 柱子上，从下往上有 N 个从大到小叠放的盘子。我们的目标是，希望用尽可能少的移动次数，把所有的盘子由 A 柱移动到 C 柱。过程中，每次只能移动一个盘子，且在任何时候，大盘子都不可以在小盘子上面。
解题思路：
尝试把问题分解，使用分治的思想，将问题分解成一个个容易解决的子问题，然后一个个的去解决
我们把一个 N 层汉诺塔从 A 搬到 C，我们假定只有两层，首先把 N-1 层搬到 B,然后把下面的第 N 层搬到 C，然后再把 N-1 层从 B 搬到 C 。
如果存在多层，那我们就假定 N-1 层已经排好序了，只搬第 N 层，这样依次递归下去。
终止条件：
当只剩下最后一个的时候，我们只需要搬动一次就行了
var count int = 0
func main() {
beadNum := 5 // This is the initial number of beads
hanoi(beadNum, "A", "B", "C")
fmt.Println(count)
}
func hanoi(beadNum int, pillarA string, pillarB string, pillarC string) {
if beadNum == 1 {
// 最后一个了，可以结束了
move(beadNum, pillarA, pillarC)
} else {
// Step 2: 将 N-1 层从 A 移动到 B
hanoi(beadNum-1, pillarA, pillarC, pillarB)
// Step 2: 将第 N 层从 A 移动到 C
move(beadNum, pillarA, pillarC)
// Step 3: 将 B 中的 N-1 层移动到 C
hanoi(beadNum-1, pillarB, pillarA, pillarC)
}
}
func move(beadNum int, pillarFrom string, pillarTo string) {
count += 1
}
总结
1、分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
2、分治是处理问题的思想，递归是一种编程技巧。分治一般都比较适合用用递归来实现。
3、分治算法的实现中，每一层地递归都会涉及到下面三个操作：
-
分解：将原问题分解成一系列子问题；
-
解决：将子问题的结果合并成原问题。
参考
【数据结构与算法之美】https://time.geekbang.org/column/intro/100017301
【经典优化算法之分治法】https://zhuanlan.zhihu.com/p/45986027
【归并排序】https://zh.m.wikipedia.org/zh-hans/归并排序
【归并排序】https://geekr.dev/posts/go-sorting-algorithm-merge
【分治使用技巧】https://boilingfrog.github.io/2022/11/17/分治算法的思想/