分治思想--python
分治
一、几个能用分治解决的判断依据：
- 问题可以分解：原问题可以分解为规模更小、类似的子问题，可以用同样方式递归进行划分。
- 子问题独立：子问题之间没有重叠互不重叠，可以独立解决。
- 子问题的解可以合并：原问题的解通过合并子问题的解得来。
分治可以有效的解决算法问题，可以提升算法的效率，因为分治的子问题相互独立，因此可以并行解决，也就是说分治不仅仅可以降低算法的时间复杂度，还有利于操作系统的并行优化。
二、常见的分治应用：
- 二分查找：将有序数组从中点索引处分为两个部分，然后根据目标值与中间元素值比较结果，决定排除哪一半区间，并在剩余区间执行相同的二分操作。
- 归并排序：把已经排好序的子序列进行合并，得到一个完整的有序序列，相对于先排序一片区域等排序完区域再拼接。
- 快速排序：从数列中选出一个元素，作为一个基准，重新排序，所有比基准小的放在数组左边，所有比基准大的数字放在数组右边，在这个分区结束后，这个基准数字就在数组的最中间，这个被称为分区操作，利用递归把小于基准的子序列和大于基准的子序列进行排序，最终得到一个完整的排序数组。
- 桶排序：设定一个定量的数组作为空桶，遍历数组，将数据放到对应的桶中，对每个不是空的桶进行排序，从每个非空桶中取出数据进行拼接，得到完整的排序数据。
- 树：二叉树，AVL树等
三、二分查找：
- 问题可以分解：二分查找递归的将原问题分解为子问题，这是通过比较中间元素和目标元素来实现。
- 子问题独立：在二分查找中，每轮只处理一个问题，它不受其他子问题的影响。
- 子问题的解不需要合并：二分查找是为了找到一个特定元素，因此不需要将子问题的解进行合并，当子问题得到解决时，原问题也会被解决。
def dfs(nums: list[int], target: int, left: int, right: int):# 终结条件，区间不存在后返回-1if left > right:return -1# 计算中间点midmid = (left + right) // 2# 如果目标值大于中间值if nums[mid] < target:# 继续递归return dfs(nums, target, mid + 1, right)# 如果目标值小于中间值elif nums[mid] > target:# 继续递归return dfs(nums, target. left. mid - 1)# 找到目标值else:# 返回目标索引return middef binary_search(nums: list[int], target: int):lenth = len(nums)return def(nums, target, 0, lenth - 1)
四、恢复二叉树：
从前序与中序遍历序列构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
从中序与后序遍历序列构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
- 问题可以分解：将问题分解为构建左子树，构建右子树。每次将树分解成更小的子树，直到达到空子树为止。
- 子问题独立：左子树和右子树相互独立，没有交集。构建左子树只需要关注中序遍历和前序遍历中与左子树对应的部分，右子树同理。
- 子问题的解可以合并：得到左子树和右子树后，我们将它们连接到根节点上，就可以得到问题的答案。
这里我们用前序遍历和中序遍历去获得目标树，
前序遍历：[根节点|左子树|右子树]
中序遍历：[左子树|根节点|右子树]
根据前序遍历得到根节点，再在中序遍历中获得到左子树和右子树。
| 根节点在前序遍历中的索引 | 子树在中序遍历的索引 | |
|---|---|---|
| 当前树 | i | [left , right] |
| 左子树 | i + 1 | [left , mid - 1] |
| 右子树 | i + 1 + (mid - left) | [mid + 1 , right] |
根据每次的索引，可以得到相对的根节点、左子树和右子树。
def dfs(preorder: list[int], inorder_map: dict[int, int], index: int, left: int, right: int):# 子树空了后终止if right - left < 0:return None# 初始化根节点root = TreeNode(preorder[i])# 查询mid，可以划分左右子树mid = inorder_map[preorder[index]]# 构建左子树root.left = dfs(preorder, inorder_map, index + 1, left, mid - 1)# 构建右子树root.right = def(preorder, inorder_map, index + 1 + mid - left, mid + 1, right)# 返回根节点return rootdef build_tree(preorder: list[int], inorder: list[int]):# 初始化哈希表inorder_map = {val: index for index, val in enumerate(inorder)}root = dfs(preorder, inorder_map, 0, 0, len(inorder) - 1)return root