算法：分治

2022-04-18 16:50:55 浏览数 (1)

分治

分治是一种将大问题分解成相同任务的小问题的方法，常见的分治思想之一就是归并排序(mergeSort)

归并排序

归并排序在之前的排序章节中有讲解过，这里再回顾一下：

给定一个无序列表：

从中间将其分为左右两个子列表，两个字列表之后再进行分开，直到都子列表只剩下一个元素时候，然后再进行合并排序；

伪代码如下：

代码语言：javascript复制
MERGE-SORT(A, p, r)
if p < r
 q = p   (r-p)/2
 MERGE-SORT(A, q 1, r)
 MERGE-SORT(A, p, q)
 MERGE(A, p, q, r)
  • 首先分成5,4,1,8和7,2,6,3
  • 5,4,1,8和7,2,6,3再分别分成5,4和1,8 以及 7,2和6,3
  • 5,4和1,8 以及 7,2和6,3再分别分成5和4, 1和8 以及 7和2，6和3
  • 进行合并排序，5和4变成4,5， 1和8 变成1,8， 7和2变成2,7， 6和3变成3,6
  • 再次进行合并排序，4,5和1,8变成1,4,5,8， 2,7和3,6变成2,3,6,7
  • 再次进行合并排序，1,4,5,8和2,3,6,7变成1,2,3,4,5,6,7,8
  • 排序完成

分治法一般用在规律比较明显的题目上，一般配合着递归完成；

例题

92 将有序数组转为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

img

代码语言：javascript复制
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

img

代码语言：javascript复制
输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 按 严格递增 顺序排列

解题思路：

由于是一颗高度平衡的二叉搜索树，则可以直接将列表的中间节点作为根节点，左右子列表也是有序列表，因此可以分治的基于左右有序列表构造左右子树；

代码实现：

  • python实现
代码语言：javascript复制
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        
        mid = int(len(nums)/2)
        return TreeNode(nums[mid], self.sortedArrayToBST(nums[:mid]), self.sortedArrayToBST(nums[mid 1:]))
  • c 实现
代码语言：javascript复制
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        if (n < 1)
        {
            return nullptr;
        }
        
        int mid = n / 2;
        vector<int> left;
        left.assign(nums.begin(), nums.begin() mid-1);
        vector<int> right;
        right.assign(nums.begin() mid, nums.end());
        return TreeNode(nums[mid], sortedArrayToBST(left), sortedArrayToBST(right));
    }
};
90 从中序与后续遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

img

代码语言：javascript复制
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

代码语言：javascript复制
输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

解题思路：

  • 中序遍历的顺序：先左子树->根节点->右子树
  • 后序遍历的顺序：先左子树->右子树->根节点

基于后续遍历可以知道，末尾就是根节点，然后在中序遍历中找到根节点，根节点的左边就是左子树，根节点的右边就是右子树。基于中序遍历的左子树，能够从后续遍历中找到左子树的后续遍历；基于中序遍历的右子树，能够从后续遍历中找到右子树的后续遍历；问题分解成了两个小的问题，方法一样，采用分治递归的思想解决，这里有个小技巧就是使用哈希表存储元素映射位置，这样能够比较快速的切分左右子树

代码实现：

  • python实现
代码语言：javascript复制
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        self.map = {j: i for i, j in enumerate(inorder)}  # 方便定位
        self.postorder = postorder
        return self.func(0, len(postorder)-1)
    
    def func(self, left, right):
        if left > right:
            return None
        
        root_val = self.postorder.pop()
        index = self.map[root_val]
        right_node = self.func(index 1, right)
        left_node = self.func(left, index-1)
        return TreeNode(root_val, left_node, right_node)
  • c 实现
代码语言：javascript复制
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
    
public:
    TreeNode* func(int left, int right, vector<int>& inorder, vector<int>& postorder)
    {
        if(left > right)
        {
            return nullptr;
        }
        
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);
        
        int index = idx_map[root_val];
        
        post_idx--;
        root->right = func(index 1, right, inorder, postorder);
        root->left = func(left, index-1, inorder, postorder);
        return root;
    }
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        post_idx = postorder.size()-1;
        
        int idx = 0;
        for(auto& val: inorder)
        {
            idx_map[val] = idx  ;
        }
        
        return func(0, inorder.size()-1, inorder, postorder);
    }
};
136 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

代码语言：javascript复制
输入：[3,2,3]
输出：3

示例 2：

代码语言：javascript复制
输入：[2,2,1,1,1,2,2]
输出：2

进阶：

  • 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

解题思路：

  • 哈希表：遍历一遍，统计每个数字出现的次数，然后再遍历一遍，如果该元素的次数超过长度的一半，则该元素就是最终答案
  • 排序法：如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 n/2 的元素（下标从 0 开始）一定是众数。
  • 分治法：如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。将数组分成左右两部分，分别求出左半部分的众数 a1 以及右半部分的众数 a2，随后在 a1 和 a2 中选出正确的众数。经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。
  • Boyer-Moore投票法：维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate可以为任意值，count 为 0；遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
    • 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
    • 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
    • 在遍历完成后，candidate 即为整个数组的众数。

代码实现：

分治法：

  • python实现
代码语言：javascript复制
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        def majority_element_rec(lo, hi):
            if lo == hi:
                return nums[lo]
            
            mid = lo   (hi-lo)//2
            left = majority_element_rec(lo, mid)
            right = majority_element_rec(mid 1, hi)
            
            if left == right:
                return left
            
            # 不相等的时候要进行比较
            left_count = sum(1 for i in range(lo, hi 1) if nums[i] == left)
            right_count = sum(1 for i in range(lo, hi 1) if nums[i]==right)
            return right if left_count < right_count else left
        return majority_element_rec(0, len(nums)-1)
  • c 实现
代码语言：javascript复制
class Solution {
    int count_in_range(vector<int>& nums, int target, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi;   i)
            if (nums[i] == target)
                  count;
        return count;
    }
    int majority_element_rec(vector<int>& nums, int lo, int hi) {
        if (lo == hi)
            return nums[lo];
        int mid = (lo   hi) / 2;
        int left_majority = majority_element_rec(nums, lo, mid);
        int right_majority = majority_element_rec(nums, mid   1, hi);
        if (count_in_range(nums, left_majority, lo, hi) > (hi - lo   1) / 2)
            return left_majority;
        if (count_in_range(nums, right_majority, lo, hi) > (hi - lo   1) / 2)
            return right_majority;
        return -1;
    }
public:
    int majorityElement(vector<int>& nums) {
        return majority_element_rec(nums, 0, nums.size() - 1);
    }
};

投票法可能更好理解一些：

  • python实现
代码语言：javascript复制
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None
        
        for num in nums:
            if count == 0:
                candidate = num
            count  = 1 if num == candidate else -1
        
        return candidate
  • c 实现
代码语言：javascript复制
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate = -1;
        for(int num: nums)
        {
            if(num == candidate)
            {
                  count;
            }
            else if(--count < 0)
            {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};
89 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

img

代码语言：javascript复制
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

代码语言：javascript复制
输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

解题思路：

与之前的中序遍历和后续遍历一样，先找到根节点，然后将其分为左子树和右子树，分治递归的构建左子树和右子树

  • 前序遍历的顺序：先根节点->左子树->右子树
  • 中序遍历的顺序：先左子树->右子树->根节点

基于前序遍历的第一个元素就是根节点，在中序遍历中使用哈希的方法定位根节点，区分左右子树

代码实现：

  • python实现
代码语言：javascript复制
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
            if preorder_left > preorder_right:
                return None
            
            # 前序遍历中的第一个节点就是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点
            inorder_root = index[preorder[preorder_root]]
            
            # 先把根节点建立出来
            root = TreeNode(preorder[preorder_root])
            # 得到左子树中的节点数目
            size_left_subtree = inorder_root - inorder_left
            # 递归地构造左子树，并连接到根节点
            # 先序遍历中「从 左边界 1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(preorder_left   1, preorder_left   size_left_subtree, inorder_left, inorder_root - 1)
            # 递归地构造右子树，并连接到根节点
            # 先序遍历中「从 左边界 1 左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位 1 到 右边界」的元素
            root.right = myBuildTree(preorder_left   size_left_subtree   1, preorder_right, inorder_root   1, inorder_right)
            return root
        
        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        return myBuildTree(0, n-1, 0, n-1)
  • c 实现
代码语言：javascript复制
class Solution {
private:
    unordered_map<int, int> index;

public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];
        
        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界 1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = myBuildTree(preorder, inorder, preorder_left   1, preorder_left   size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界 1 左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位 1 到 右边界」的元素
        root->right = myBuildTree(preorder, inorder, preorder_left   size_left_subtree   1, preorder_right, inorder_root   1, inorder_right);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i < n;   i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};
二叉树 python c++ 编程算法

0 人点赞